Ratsun kierto

Wikipedia
Loikkaa: valikkoon, hakuun
Yksi mahdollinen ratkaisu animaationa
Ratsun kierto sellaisena kuin Turkkilainen ratkaisi sen. Tässä tapauksessa lopetusruudusta pääsee aloitusruutuun.
Ratsun kierto 5x5-laudalla.

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 shakkillaudalla (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).

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:

  1. m ja n ovat molemmat parillisia
  2. m on 1, 2 tai 4
  3. 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ä]

  1. Wegener, I. (January 1, 1987). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-898-71458-3. 
  2. There Are No Magic Knight's Tours on the Chessboard
  3. Gunno Törnberg: Warnsdorff's rule results 2005. Viitattu 27.1.2009. (suomeksi)

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]