Page 26 - Encantador
P. 26
Problema de la ruta del cavall
Una ruta de cavall és una seqüència de moviments de cavall en un
escaquer tal que el cavall passi per cada casella exactament un cop. Si
el cavall acaba el seu recorregut en una casella que es trobi a un
moviment de cavall de la casella des d'on ha començat, de manera que
podria començar la mateixa ruta de nou de forma immediata, llavors es
diu que la ruta és tancada; en cas contrari és oberta. El nombre exacte
de rutes obertes en un escaquer de 8x8 roman encara avui desconegut.
El problema de la ruta del cavall és un problema matemàtic basat a
buscar una ruta de cavall. Crear un programa que trobi una ruta de
cavall és un problema comú plantejat a estudiants de ciència
computacional. Hi ha variacions del problema que impliquen escaquers
de diferents mides a les usuals 8x8 caselles, així com taulers irregulars
(no rectangulars).
