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.[1] Hi ha variacions del problema que impliquen escaquers de diferents mides a les usuals 8x8 caselles, així com taulers irregulars (no rectangulars).
Teoria
modificaEl 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
modificaLa 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 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
modificaEn 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 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.[7]
Quins taulers tenen rutes possibles
modificaSchwenk[8] 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:
- m i n són ambdós imparells; n no és 1
- m = 1, 2, o 4; n no és 1
- 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
modificaHi 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
modificaUna 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
modificaTot 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.[11][12]
Solucions de xarxa neuronal
modificaUna 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 amb les següents regles de transacció:
on representa intervals discrets de temps, és l'estat de la casella de connexió neuronal amb la casella , és el resultat de la neurona des de a , i é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 i el . 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
modificaa | 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 |
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[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é
modificaNotes i referències
modifica- ↑ H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." Prentice Hall, Upper Saddle River, New Jersey, pp. 326–328. 2003.
- ↑ 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.
- ↑ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhitraversal: Parimal Sanskrit Series No. 30.
- ↑ 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 nombre anunciat és incorrecte. D'acord amb el treball de McKay's el nombre correcte és 13,267,364,410,532 i aquest nombre és reflectit al llibre de Wegener de 2000.
- ↑ Brendan McKay «Knight's Tours on an 8x8 Chessboard». Technical Report TR-CS-97-03. Department of Computer Science, Australian National University, 1997. Arxivat de l'original el 2012-01-27 [Consulta: 6 abril 2013].
- ↑ Wegener, I.. Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics, 2000. ISBN 0-89871-458-3.
- ↑ Weisstein, Eric W., «Knight's Tour» a MathWorld (en anglès).
- ↑ Allen J. Schwenk «Which Rectangular Chessboards Have a Knight’s Tour?». Mathematics Magazine, 1991, pàg. 325–332.
- ↑ Cull, Paul. «Knight's Tour Revisited». Fibonacci Quarterly. [Consulta: 5 agost 2012].
- ↑ «Enumerating the Knight's Tour».
- ↑ Cull, P.; DeCurtins, J. «Knight's Tour Revisited». Fibonacci Quarterly, 16, juny 1978, pàg. 276–285.
- ↑ Parberry, Ian «An Efficient Algorithm for the Knight's Tour Problem». Discrete Applied Mathematics, 73, 1997, pàg. 251–260. Arxivat de l'original el 2013-09-27. DOI: 10.1016/S0166-218X(96)00010-8 [Consulta: 9 abril 2013].
- ↑ Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.
- ↑ 14,0 14,1 Pohl, Ira «A method for finding Hamilton paths and Knight's tours». Communications of the ACM, 10, 7, juliol 1967, pàg. 446–449. DOI: 10.1145/363427.363463.
- ↑ Squirrel, Douglas; Cull, P. «A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards», 1996. [Consulta: 21 agost 2011].
- ↑ 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 [Consulta: 2008]