Tehtävänä olisi värittää shakkilaudan 8x8 ruutua siten, että yhdelläkään ruudulla ei ole kahta samanväristä naapuria (pää- ja väli-ilmansuunnat huomioiden).
Helposti todetaan, että tehtävän ratkaisemiseen tarvitaan ainakin 9 eri väriä.
Kysymys kuuluukin, montako erilaista ratkaisua tehtävälle löydetään näitä 9 väriä käyttäen?
Helposti todetaan, että tehtävän ratkaisemiseen tarvitaan ainakin 9 eri väriä.
Kysymys kuuluukin, montako erilaista ratkaisua tehtävälle löydetään näitä 9 väriä käyttäen?
Vastaukset 1
Vanhimmat
Tarkastellaan vasemman yläkulman 3x3 ruudun aluetta. Helposti todetaan, että näiden ruutujen pitää kaikkien olla eri värisiä. Yleisyyttä rajoittamatta voimme olettaa, että näiden värien numerot ovat
123
456
789
Kaikkien mahdollisten ratkaisujen lukumäärä tulee sitten olemaan 9! kertaa tällä tavalla saatavien ratkaisujen lukumäärä.
Seuraavaksi lähdetään täyttämään kolmen ylimmän rivin muita sarakkeita. 4. sarakkeeseen voidaan valita vapautuneet ensimmäisen sarakkeen kolme ylintä numeroa missä tahansa järjestyksessä. Näitä järjestyksiä on 3!=6 kappaletta. Vastaavalla tavalla todetaan, että kussakin seuraavassa sarakkeessa kolme ylintä väriä voidaan valita 3!=6 eri tavalla.
Kolme ylintä riviä voidaan siis tehtävän ehdoilla täyttää 9!*(3!)^5=2821754880 eri tavalla.
Tämän jälkeen lähdetäänkin täyttämään ylhäältä lukien 4.-8. riviä. Kaikkia vaihtoehtoja ei tietenkään tarvitse käydä läpi, koska ratkaisuja jokaisella vasemman yläkulman 3x3 ruudun täytöllä ratkaisuja on yhtä paljon.
Tästä voi tehdä pienen tietokoneprojektin. Oletetaan esimerkiksi, että vasemman yläkulman värit ovat edellämainitussa järjestyksessä. Jokaisella muiden sarakkeiden kolmen ensimmäisen alkion valintatavalla ((3!)^5=7776 vaihtoehtoa) käydään läpi kaikki mahdolliset 4.-8. rivin alkioiden valinnat takaisinpaluumenetelmällä. Nykyisten tietokoneiden laskentakapasiteetti riittänee tähän.
Tsemppiä, softagurut