Ratsun kierto
Ratsun kierto on matemaattinen ongelma, johon liittyy shakissa käytettävä ratsu ja shakkilauta. Tarkoituksena on liikuttaa ratsua laudalla niin, että se käy jokaisessa ruudussa kerran ja vain kerran. Ongelmalle on useita ratkaisuja. Normaalilla shakkilaudalla (8 x 8) on tasan 26 534 728 821 064 sellaista ratkaisua, joissa ratsu lopettaa ruudulle, jota se uhkaa alussa. Tällöin kyseessä on silmukka jossa lopetusruudusta pääsee takaisin alkuun.[1] On olemassa myös ratkaisuja, joissa viimeisestä ruudusta ei ole mahdollista päästä takaisin aloitusruutuun. Lukuun on laskettu mukaan myös ratkaisujen käänteiset muodot (siirrot takaperin).
Sisällysluettelo
Ominaisuuksia[muokkaa | muokkaa wikitekstiä]
Monista ratkaisuista on löydettävissä taikaneliön ominaisuuksia. Taikaneliössä jokaisen vaaka-, pysty- ja vinorivin summa on sama. Tällaista taikaneliötä, jossa luvut vastaavat ratsun kierron siirron järjestyslukua ei ole mahdollista luoda[2], vaikkakin lähellä olevia ratkaisuja on löydetty. Tämä matemaattinen ongelma ratkaistiin tietokoneen avulla vuonna 2003.
Olemassaolo[muokkaa | muokkaa wikitekstiä]
Ratsun kierto on aina mahdollista toteuttaa m * n kokoisella laudalla, jossa m pienempi tai yhtäsuuri kuin n, jos yksi tai useampi seuraavista ehdoista ei täyty:
- m ja n ovat molemmat parillisia
- m on 1, 2 tai 4
- m on 3 ja n on 4,6, tai 8
Pienin mahdollinen neliönmuotoinen lauta, jolla sen voi suorittaa on 5 x 5 -lauta.[3]
Ratsun kiertoa voi myös pelata eräänlaisena kaksinpelinä. Tällöin molemmat siirtävät vuorotellen ratsujaan, kunnes jompikumpi ei voi enää liikuttaa ratsuaan uudelle ruudulle. Tällöin toinen pelaaja on voittanut.
Lähteet[muokkaa | muokkaa wikitekstiä]
Viitteet[muokkaa | muokkaa wikitekstiä]
- ↑ Wegener, I. (January 1, 1987). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-898-71458-3.
- ↑ There Are No Magic Knight's Tours on the Chessboard
- ↑ Gunno Törnberg: Warnsdorff's rule results 2005. Viitattu 27.1.2009. (suomeksi)
Aiheesta muualla[muokkaa | muokkaa wikitekstiä]
- - A Knight of Egodeth: Zen Raptured Quietude 240 Solutions to the Knights Tour in form of Game Book, published by Dr. Eugene "Roger" Apodaca
- Warnsdorff's rule II - Efficiency of Warnsdorff´s Rule
- Warnsdorff's Rule Web Page
- The ultimate Knight's Tour page of Links
- The knight's tour
- Knight's tour notes
- A Simple backtracking implementation in C++
- Sloane's Integer Sequence A001230
- 8 by 8 Knight's Tour strategy
- Playable 8 by 8 Knight's Tour
- The Knight's Tour
- Knight's Tours Using a Neural Network
