Monellako tavalla 8 kuningatarta voidaan asettaa tavalliselle shakkilaudalle siten, ettei yjsikään kuningatar uhkaa toista. Kuningattaret ovat keskenään samanlaisia, ja ruudut on numeroitu.
Kombinatorinen kysymys
sakkitunari
1092
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 10
Vanhimmat
Vastaan, että 92 tavalla, jos peilisymmetriset asemat ja laudan kierto lasketaan eri asemiksi.
Miten tuohon päädytään?
Vaikka käymällä kaikki tapaukset läpi. Koska joka sarakkeella on yksi kuningatar ja millään rivillä ei ole kahta, on tarkasteltavia tapauksia korkeintaan 8!. Nopea tietokoneajo toteaa, että tapauksia on 92 kpl.
http://code.activestate.com/recipes/475145-a-general-solution-of-eight-queens/
Jos tehtävässä varta vasten sanotaan, että ruudut on numeroitu, niin mikkä ihmeen kierrot ja peilisymmetriset asemat. Kyllä A1 ruutu pysyy A1 ruutuna vääntelet tai kääntelet sitä lautaa miten hyvänsä, tai vaikka vahtaisit sitä mistä suunnasta tahansa.
Lisäksi sanotaan myös, että kuningattaret ovat samanlaisia, eli saman värisiä, ja saman väriset kuningattaret ei toisiaan uhkaa.
Onko tässä nyt luettu tehtävää ollenkaan, vastattu vaan mutuna?
Toisia ehkä kiinnostaa se matematiikka enemmän kuin pilkunnussinta.
On melko helposti nähtävissä, että 8 tornia voidaan asettaa 8! eri tavalla. Esim 8x8 identtinen matriisi on yksi näistä:
{1,0,...,0}
{0,1,0,...0}
...
{0,0,...,1}
Aika helposti myös nähtävissä että jokaiseen näistä matriiseista sijoittamalla tornien paikalle kuningattaret jokin kuningatar uhkaa toista. Koska toisiaan uhkaamattomat tornit ovat toisiaan uhkaamattomien kuningattarien osajoukko ei muita mahdollisia kombinaatioita ole ja vastaus on 0.
Näin nopeasti ajateltuna.
>Aika helposti myös nähtävissä että jokaiseen näistä matriiseista
>sijoittamalla tornien paikalle kuningattaret jokin kuningatar uhkaa toista.
Jos osaat todistaa tuon, kun se mielestäsi on aika helposti nähtävissä, niin saat kaiken kunnioitukseni, ja sitten minä julkisesti häpeän. Mutta jäänet sitä ilman, koska väite ei pidä paikkaansa, minkä osaan kyllä todistaa.
Ekana tulisi mieleen kirjoittaa algoritmi joka tarkastaa kaikki tapaukset läpi ja poimii sieltä ne joissa kuningattareit eivät leikkaa. Ajattelin kuitenkin että joku ehtii sitä ennen postata tänne vastaesimerkkejä niin en jaksanut alkaa tuollaista kirjoittamaan.
Jos kuningattaret ovat keskenään samanlaisia, niin ne ei koskaan uhkaa toisiaan.
Eka voidaan laittaa 64 :ään paikkaan , toka 63:een, jne...
https://en.wikipedia.org/wiki/Eight_queens_puzzle
Tuolta löytyy ratkaisu. Eli kuten vastaus täällä jo tulikin, niin se on 92. Jos kierrolla ja heijastuksella toisistaan eroavia ratkaisuja ei lasketa eri ratkaisuiksi, niin sitten niitä on 12.
Mielenkiintoinen ongelma myös kun annetaan laudan koon vaihdella nxn-laudaksi (myös monia muita yleistyksiä ongelmalle löytyy).
Tuolta wikipedia artikkelista: "There is currently no known formula for the exact number of solutions, or even for its asymptotic behaviour." Joten eipä taida olla mitään kaavaa tiedossa, jolla tämän ratkaisujen määrän saisi.
Täältä löytyy tuon jonon alku: https://oeis.org/A000170/list
Ihan huvikseni laskin mitä tapahtuisi, jos nuo ratkaisut "laskee yhteen" eli laskee yhteen matriisit, jotka kuvastavat ratkaisuja (ykkönen kuningattaren paikalla, muualla nolla, nämähän ovat permutaatiomatriiseja).
Kaikki ratkaisut
[04, 08, 16, 18, 18, 16, 08, 04]
[08, 16, 14, 08, 08, 14, 16, 08]
[16, 14, 04, 12, 12, 04, 14, 16]
[18, 08, 12, 08, 08, 12, 08, 18]
[18, 08, 12, 08, 08, 12, 08, 18]
[16, 14, 04, 12, 12, 04, 14, 16]
[08, 16, 14, 08, 08, 14, 16, 08]
[04, 08, 16, 18, 18, 16, 08, 04]
Ratkaisut/(kierrot, heijastukset). Tämähän tietysti riippuu minkä ottaa kutakin ratkaisua edustamaan, joten tässä ei taida olla mitään järkeä...
[2, 0, 1, 1, 5, 2, 1, 0]
[7, 0, 2, 0, 0, 0, 3, 0]
[3, 0, 1, 2, 3, 0, 1, 2]
[0, 1, 0, 2, 1, 3, 1, 4]
[0, 5, 1, 1, 0, 1, 0, 4]
[0, 4, 1, 2, 0, 0, 3, 2]
[0, 2, 2, 1, 1, 3, 3, 0]
[0, 0, 4, 3, 2, 3, 0, 0]
Täällä ei kuitenkaan tule nuo sarakkeet suoraan (vaikka yritin tuonne etunollia ekaan sitä varten lisätäkin) mutta notepadissa voi katella. Eipä oikein taida mitään kaavaa näkyä paitsi kaikkien ratkaisujen tapauksessa tietysti tuo kierroista ja heijastuksista tuleva symmetria :D.