Problema de la ruta del cavall

Una ruta de cavall oberta en un escaquer de 8x8 caselles.

Animació d'una ruta de cavall en un tauler de 5 per 5 caselles.

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

Teoria

Graf de cavall que mostra tots els possibles camins per una ruta de cavall en un tauler estàndard de 8×8 cselles. Els nombres en cada nus indiquen el nombre de possibles moviments que es poden fer des de la casella que correspon al nus.

El problema de la ruta del cavall és un cas específic del més general problema del cicle Hamiltonià en teoria de grafs. El problema de trobar una ruta tancada de cavall és similar a un cas del problema del cicle Hamiltonià. Cal notar, de tota manera, que a diferència del problema del cicle hamiltonià, el problema de la ruta del cavall es pot solucionar en un temps raonable.

Història

La ruta del cavall tal com fou solucionada per El Turc, una falsa màquina de jugar als escacs. Aquesta solució en particular és tancada (circular), i es pot completar des de qualsevol punt del tauler.

La referència coneguda més antiga al problema de la ruta del cavall data del segle ix. Al Kavyalankara de Rudraṭa (5.15), una obra poètica en sànscrit, l'esquema d'una ruta de cavall en un mig-escaquer hi és presentat com una figura poètica elaborada ("citra-alaṅkāra") anomenada "turagapadabandha" o 'assaig sobre els passos d'un cavall.' El mateix vers en quatre línies de vuit síl·labes cadascuna es pot llegir d'esquerra a dreta, o tot seguint el camí del cavall en la seva ruta. Com que els sistemes d'escriptura indis usats pel sànscrit eren sil·làbics, cada síl·laba pot ser vista com a la representació d'una casella del tauler d'escacs. L'exemple de Rudrata és el següent:

से ना ली ली ली ना ना ना ली

ली ना ना ना ना ली ली ली ली

न ली ना ली ली ले ना ली ना

ली ली ली ना ना ना ना ना ली

se nā lī lī lī nā nā lī

lī nā nā nā nā lī lī lī

na lī nā lī le nā lī nā

lī lī lī nā nā nā nā lī

Per exemple, la primera línia es pot llegir d'esquerra a dreta o bé movent-se des de la primera casella a la tercera síl·laba de la segona línia (2.3) i després a 1.5 a 2.7 a 4.8 a 3.6 a 4.4 a 3.2.

Un dels primers matemàtics a investigar la ruta del cavall fou Leonhard Euler. El primer procediment establert per completar la ruta del cavall fou la regla de Warnsdorff, descrita per primer cop el 1823 per H. C. von Warnsdorff.

Al segle xx el grup Oulipo d'escriptors la van usar, entre d'altres. L'exemple més notable és la ruta del cavall en un tauler de 10 × 10 que estableix l'ordre dels capítols a la novel·la La vie, mode d'emploi de Georges Perec. A la sisena partida del Campionat del món de 2010 entre Viswanathan Anand i Vesselín Topàlov s'hi va veure com Anand feia 13 moviments consecutius de cavall (tot i que fent servir els dos cavalls) -– els comentaristes en línia feien broma pretenent que Anand estava intentant de solucionar el problema de la ruta del cavall durant la partida.

Nombre de rutes tancades

En un tauler de 8 × 8, hi ha exactament 26,534,728,821,064 possibles rutes tancades (considerant que dues rutes pel mateix camí però en direccions oposades es compten separadament, així com les rotacions i reflexions). El nombre de rutes de cavall indirectes és la meitat del nombre anterior, ja que cada ruta pot ser realitzada a l'inrevés. Hi ha 9,862 rutes tancades indirectes en un tauler de 6 × 6.

Quins taulers tenen rutes possibles

Schwenk va demostrar que per qualsevol tauler m × n amb m menor o igual que n, sempre serà possible una ruta del cavall tancada llevat que es donin una o més de les tres condicions següents:

1. m i n són ambdós imparells; n no és 1
2. m = 1, 2, o 4; n no és 1
3. m = 3 i n = 4, 6, o 8.

Cull i de Curtins varen demostrar que en qualsevol escaquer rectangular la banda més petita del qual sigui almenys 5, hi ha una (possiblement oberta) ruta del cavall.

Trobant rutes amb ordinadors

Hi ha un bon nombre de maneres de trobar una ruta del cavall en un tauler donat, amb un ordinador. Alguns d'aquests mètodes són algorismes, mentre que altres són heurístics.

Algorismes de força bruta

Una recerca amb força bruta per una ruta del cavall és impracticable, llevat de per taulers molt petits; per exemple, en un tauler de 8x8 hi hauria aproximadament 4×10⁵¹ possibles seqüències de moviments, i és bastant per damunt la capacitat dels ordinadors moderns (o xarxes d'ordinadors) de fer operacions amb unes dades tan grans.

Algorismes de divisió i conquesta

Tot dividint l'escaquer en parts més petites, construint rutes amb cada peça, i després posant les peces juntes, hom pot construir rutes en la majoria de taulers rectangulars en temps polinòmic.

Solucions de xarxa neuronal

Una possible solució al problema de la ruta del cavall passa per la implementació d'una xarxa neuronal. La xarxa queda definida pel fet que cada moviment legal de cavall és representat per una neurona, i cada neurona és definida aleatòriament i inicial per ser "activa" o "inactiva" (amb valor d'1 o 0), amb l'1 que implica que la neurona és part de la solució final. Cada neurona té també una funció estàtica (descrita més avall) que inicialment és 0.

Quan la xarxa funciona, cada neurona pot canviar el seu estat i el seu resultat basant-se en els resultats de les seves veïnes (aquelles que estiguin exactament a un moviment de cavall de distància) d'acord amb les següents regles de transacció:

$U_{t+1}(N_{i,j})=U_{t}(N_{i,j})+2-\sum _{N\in G(N_{i,j})}V_{t}(N)$

$V_{t+1}(N_{i,j})=\left\{{\begin{array}{ll}1&{\mbox{if}}\,\,U_{t+1}(N_{i,j})>3\\0&{\mbox{if}}\,\,U_{t+1}(N_{i,j})<0\\V_{t}(N_{i,j})&{\mbox{en altre cas}},\end{array}}\right.$

on $t$ representa intervals discrets de temps, $U(N_{i,j})$ és l'estat de la casella de connexió neuronal $i$ amb la casella $j$, $V(N_{i,j})$ és el resultat de la neurona des de $i$ a $j$, i $G(N_{i,j})$ és el conjunt de veïns de la neurona.

Tot i que són possibles casos divergents, la xarxa hauria d'acabar convergint, cosa que passa quan cap neurona canviï el seu estat entre el temps $t$ i el $t+1$. Quan la xarxa convergeix, o bé la xarxa codifica una ruta de cavall, o bé una sèrie de dos o més circuits independents al mateix tauler.

Regla de Warnsdorff

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Una representació gràfica de la regla de Warnsdorff's. Cada casella conté un enter que mostre el nombre de moviments que el cavall podria fer des d'aquella casella. La regla ens indica que cal moure a la casella amb el nombre enter més petit, en aquest cas 2.

La regla de Warnsdorff és un procediment heurístic per trobar una ruta de cavall. Es tracta de moure el cavall de tal manera que sempre vagi a la casella des de la qual el cavall sempre tingui el menor nombre de possibilitats de moure novament. En calcular el nombre de possibles moviments per cada casella candidata, no hi hem d'incloure moviments que revisitin una casella ja visitada anteriorment. És possible, naturalment, de tenir dues o més opcions per les quals el nombre de moviments possibles sigui igual; hi ha diversos mètodes per trencar aquesta mena d'empats, un d'ells dissenyat per Pohl i un altre per Squirrel i Cull.

Aquesta regla és aplicable de forma generalista a qualsevol graf. En termes de teoria de grafs, cada moviment es fa al vèrtex adjacent amb el mínim grau. Tot i que el problema del cicle Hamiltonià és NP-hard en general, en molts grafs que ocorren en la pràctica, aquest procediment heurístic és capaç de trobar satisfactòriament una solució en temps raonable. El problema del cavall és un cas especial.

La regla heurística fou descrita per primer cop a "Des Rösselsprungs einfachste und allgemeinste Lösung" per H. C. von Warnsdorff el 1823.

Vegeu també

• Abu-Bakr Muhammad ben Yahya as-Suli
• George Koltanowski
• Problema de la ruta de cavall més llarga sense creuaments
• Vuit reines

Enllaços externs

• Notes sobre la ruta del cavall