Problema de la ruta del cavall

De Viquipèdia
Dreceres ràpides: navegació, cerca
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.[1] Hi ha variacions del problema que impliquen escaquers de diferents mides a les usuals 8x8 caselles, així com taulers irregulars (no rectangulars).

Teoria[modifica | modifica el codi]

Graf de cavall que mostra tots els possibles camins per una ruta de cavall en un tauler estàndard de 8×8 cselles. Els números a 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.[2]

Història[modifica | modifica el codi]

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[3] (5.15), una obra poètica en sànscrit, l'esquema d'una ruta de cavall en un mig-escaquer hi és presentat com a 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'escacxs. 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 Veselin Topalov 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[modifica | modifica el codi]

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).[4][5][6] El nombre de rutes de cavall indirectes és la meitat del número 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.[7]

Quins taulers tenen rutes possibles[modifica | modifica el codi]

Schwenk[8] va demostrar que per qualsevol tauler m × n amb m menor o igual que n, sempre serà possible una ruta del cavall 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.[9]

Trobant rutes amb ordinadors[modifica | modifica el codi]

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[modifica | modifica el codi]

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×1051 possibles seqüències de moviments,[10] 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[modifica | modifica el codi]

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

Solucions de xarxa neuronal[modifica | modifica el codi]

Una possible solució al problema de la ruta del cavall passa per la implementació d'una xarxa neuronal.[13] 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 a 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[modifica | modifica el codi]

Chess zhor 26.png
Chess zver 26.png a8 b8 c8 d8 e8 f8 g8 h8 Chess zver 26.png
a7 b7 c7 d7 e7 f7 g7 h7
a6 x3 b6 c6 x7 d6 e6 f6 g6 h6
a5 b5 c5 d5 x7 e5 f5 g5 h5
a4 b4 nl c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 x7 e3 f3 g3 h3
a2 x2 b2 c2 x5 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zhor 26.png
Una representació gràfica de la regla de Warnsdorff's. Cada casella conté un enter que mostre el número 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 número 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 [14] i un altre per Squirrel i Cull.[15]

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.[14] El problema del cavall és un cas especial.[16]

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.[16]

Vegeu també[modifica | modifica el codi]

Notes i referències[modifica | modifica el codi]

  1. H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." Prentice Hall, Upper Saddle River, New Jersey, pp. 326–328. 2003.
  2. Conrad, A.; Hindrichs, T.; Morsy, H.; Wegener, I.. «Solution of the Knight's Hamiltonian Path Problem on Chessboards». Discrete Applied Mathematics, 50, 2, 1994, pàg. 125–134. DOI: 10.1016/0166-218X(92)00170-Q.
  3. Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhitraversal: Parimal Sanskrit Series No. 30. 
  4. Martin Loebbing; Ingo Wegener. «The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams». The Electronic Journal of Combinatorics, 3, 1, 1996, pàg. R5. Important: Els autors posteriorment varen admetre que el número anunciat és incorrecte. D'acord al treball de McKay's el número correcte és 13,267,364,410,532 i aquest número és reflectit al llibre de Wegener de 2000.
  5. Brendan McKay. «Knight's Tours on an 8x8 Chessboard». Technical Report TR-CS-97-03. Department of Computer Science, Australian National University, 1997.
  6. Wegener, I.. Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics, 2000. ISBN 0-89871-458-3. 
  7. Weisstein, Eric W., "Knight's Tour" a MathWorld (en anglès).
  8. Allen J. Schwenk. «Which Rectangular Chessboards Have a Knight’s Tour?». Mathematics Magazine, 1991, pàg. 325–332.
  9. Cull, Paul. «Knight's Tour Revisited». Fibonacci Quarterly. [Consulta: 5 d'agost de 2012].
  10. «Enumerating the Knight's Tour».
  11. Cull, P.. «Knight's Tour Revisited». Fibonacci Quarterly, 16, juny de 1978, pàg. 276–285.
  12. Parberry, Ian. «An Efficient Algorithm for the Knight's Tour Problem». Discrete Applied Mathematics, 73, 1997, pàg. 251–260. DOI: 10.1016/S0166-218X(96)00010-8.
  13. Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.
  14. 14,0 14,1 Pohl, Ira. «A method for finding Hamilton paths and Knight's tours». Communications of the ACM, 10, 7, juliol de 1967, pàg. 446–449. DOI: 10.1145/363427.363463.
  15. Squirrel, Douglas; Cull, P. «A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards», 1996. [Consulta: 21 d'agost de 2011].
  16. 16,0 16,1 Alwan, Karla; Waters, K. (1992). "Finding Re-entrant Knight's Tours on N-by-M Boards" (PDF) a ACM Southeast Regional Conference. : 377–382, New York, New York: ACM. DOI:10.1145/503720.503806. Data de consulta 2008.  

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Problema de la ruta del cavall

Implementacions[modifica | modifica el codi]