Paikkojaan vaihtavat kuninkaat

[Seppo Savikko]

Laudalla on vain kuninkaat. Seitsemällä siirrolla ne vaihtavat paikkojaan.
Mikä on erilaisten siirtoyhdistelmien lukumäärä ?

[Seppo Savikko]

Kuninkaat voivat vaihtaa paikkojaan seitsemällä siirrolla 28 985 eri tavalla.

[Martti Hamina]

Tämä tehtävä on mainittu kirjassa Bonsdorff, Fabel, Riihimaa: Schach und Zahl.
Sain kirjan taannoin synttärilahjaksi. Joosen vinkkien perusteella katselin kirjan lukua: Wanderungen von Schachfiguren. Sieltä se löytyi yhteen pötköön, pienellä kirjasimella ladotun saksankielisen tekstin seasta (1971 painos, sivu 43, 1966 painoksessa myös sivu 43).

Kirjoitan tähän kahden virkkeen verran lainausta kirjasta:
"Eine weitere bekannte Aufgabe, die sich mit Königwanderungen befasst, betritt die Frage nach der Anzahl der möglichen Wege, wenn der auf e1 stehende weisse König und der auf e8 stehende schwarze König abwechselnd Ziehen und in 7 Zügen ihre Plätze tauschen. Die von T. R. Dawson veröffentliche lösung lautet 28 008."

Sepon vastaus on 28 985. Erotus on 977. Tässä olisi hiukan tutkittavaa.

T. MH

[Martti Hamina]

Lähetin edellisen postaukseni melkein kaksi kuukautta sitten. Vastauksia ei ole tullut liikaa.
Tein koodin ja sen perusteella annan ääneni Bonsdorffin kirjassa mainitulle T.R. Dawsonin vastaukselle. Oikea lukumäärä on 28008.
Ohjelmakoodini laskee paikkojaan vaihtaville kuninkaille siirtosarjoja hiukan yleisemmin.

Tehtävää voi yleistää monella tavalla. Eräs mahdollinen yleistys on nxn-laudan tapaus, jossa paikkojaan vaihtavat kuninkaat ovat laudan vastakkaisilla puolilla samalla linjalla. Saadaan seuraava taulukko.


Laudan .siirto-
koko.... .sarjat ......( .1. ).... .......( .2. )..
.....2x2 ........1 ...............0 ..............0
.....3x3 ........3 ...............6 ..............0
.....4x4 ........7 .............32 ..............2 (kynällä ja paperilla tarkistettu)
.....5x5 ......19 ...........246 ............26
.....6x6 ......51 .........1854 .........294
.....7x7 ....141 .......14724 ........2904
.....8x8 ....393 .....116496 ......28008
.....9x9 ..1107 .....943542(*) .?????? (Näitä ei saa laskettua minun Android-tabletilla)
.10x10 ..3139 ...7690310(*) .??????
.11x11 ..8950 .63467256(*) .??????

Taulukon toisessa sarakkeessa on niiden siirtosarjojen lukumäärä, joilla ruudussa e1 oleva kuningas pääsee lyhintä reittiä pitkin ruutuun e2, e3, e4, ...., e8, e9. Tämä löytyy kirjoista: Gik, J, Shakki ja matematiikka, sivu 82 ja hiukan yleisemmin esitettynä kirjasta, Bonsdorff, Fabel, Riihimaa: Schach und Zahl, sivut 40-42.
Kolmannessa sarakkeessa on esitettynä kuninkaiden paikan vaihtoon kelvollisten siirtosarjojen lukumäärä, kun kuninkaat ovat "ystävällisiä" eli kielletään ainoastaan yhtäaikainen samassa ruudussa oleminen. Neljännessä sarakkeessa on siirtosarjojen lukumäärä valkean ja mustan kuninkaan tapauksessa. Taulukkoon olen laittanut ainoastaan varmana pitämäni lukuarvot. Olen laskenut ne lukuarvot, joissa on #-merkkejä saamaani kokonaislukuarvoa vastaava määrä. En ole vakuuttunut tulokseni oikeellisuudesta, joten jätin lukuarvot pois.
** EDIT 31.1.2021. Sain uudelleen koodin muutosten jälkeen samat tulokset, joten päätin laittaa ne ehdolle. **
**EDIT 3.2.2021. Laajensin taulukkoa kokoon 11x11 saakka. Sarakkeen 2 luvuille on laskentamenetelmä. Jos kuninkaat voivat vaihtaa paikkaa ilman rajoitteita (saavat jopa olla samassa ruudussa) niin paikkojen vaihtoon kelvollisten siirtosarjojen lukumäärä on sarakkeen 2 luvun neliö. Löysin kaavan (oikeastaan aika helppo juttu), jolla saadaan sarakkeen 3 tapauksen törmäykset vähennettyä. Kaava antoi samat luvut, kuin ohjelma. Tähdellä merkityt sarakkeen 3 luvut laskin löytämälläni kaavalla. Sarakkeen 4 tapauksessa törmäyksiä on enemmän ja tältä osin ongelma on avoin. Luultavasti jääkin avoimeksi.**
Olisi vielä mahdollista laskea neljäs (ja useampikin) sarake ottaen vaatimukseksi isompi turvaväli.
Miksi epäilen ohjelmani tuloksia?
Siksi, että saan tulokseksi kaksi lukujonoa, joista kumpikaan ei ole Sloanen, lukujonojen tietokannassa (https://oeis.org/search?q=1%2C3%2C7%2C1 ... &go=Search).
Tehtävään liittyvät graafit (tai verkot) ovat rakenteeltaan aika erikoisia ja olettaisin, että laskujen tuloksina saatavat lukujonot löytyisivät lukujonojen tietokannasta. Toinen asia on koodauksen liittyvät tekniset yksityiskohdat (esim. laudan koon parillisuus/parittomuus).