Ratsun kierto (knights tour)

Antti Lindvall
Viestit: 1
Liittynyt: 09 Tammi 2021 15:46
Paikkakunta: Hämeenlinna

Ratsun kierto (knights tour)

Lukematon viesti Kirjoittaja Antti Lindvall » 10 Tammi 2021 14:39

Tervehdys! Tämä on ensimmäinen postaukseni tänne Shakkifoorumille. En ole enää aikoihin pelannut shakkia aktiivisesti, mutta olen sitä edelleen jonkin verran seurannut. Olen viime aikoina innostunut ratkaisemaan nk. "ratsun kierto" ("knights tour") tehtävää koodaamani ohjelman avulla. Tarkoituksenahan tehtävässä on liikuttaa ratsua laudalla niin, että se käy jokaisessa ruudussa kerran ja vain kerran. Ohjelman avulla olen tutkinut kaikkien mahdollisten ratkaisuiden, siis myös osaratkaisuiden määrän aina 3x3 ruudun kokoisesta laudasta alkaen ja eri lähtöruudut huomioon ottaen. Olen edennyt 6x7 kokoisiin lautoihin asti, joissa erilaisia lähtöruutuja on 12, kun otetaan huomioon pysty- ja vaakatasojen symmetria. Tämän kokoisella laudalla täydellisen ratkaisun laskeminen yhdestä lähtöruudusta kestää yhtäjaksoisesti noin viikon verran, vaikka ohjelma laskee yli 2 miljoona variaatiota sekunnissa! Esimerkiksi lähtöruudusta a1 alkavia siirtovariaatioita on yhteensä 1 458 388 247 413 kappaletta. Näistä 57 968 982 kappaletta muodostaa täydellisen ratkaisun ja näistä taas 2 135 276 kappaletta on silmukoita, eli ratkaisun loppuruutu on ratsun siirron päässä lähtöruudusta. Täysikokoisen (64 ruutua) laudan täydellisten variaatioiden määrän laskemiseen ei ohjelmani resurssit tule riittämään, koska pelkästään silmukoita on supertietokone laskenut täysikokoisella laudalla 26 534 728 821 064 kappaletta!
Lauta_6x7_A1_SF75pros.jpg
Lauta_6x7_A1_SF75pros.jpg (112.97 KiB) Katsottu 160 kertaa

Paikallaolijat

Käyttäjiä lukemassa tätä aluetta: Ei rekisteröityneitä käyttäjiä ja 13 vierailijaa