Mostra la font per a Problema de la ruta del cavall

{{Hide in print|[[Fitxer:Knight's tour anim 2.gif|miniatura|Una ruta de cavall oberta en un escaquer de 8x8 caselles.]]}}{{Only in print|[[Fitxer:Knight's tour.svg|miniatura|Una ruta de cavall oberta en un escaquer de 8x8 caselles.]]}}
{{Hide in print|[[Fitxer:Knights-Tour-Animation.gif|miniatura|Animació d'una ruta de cavall en un tauler de 5 per 5 caselles.]]}}
{{TOC left}}

Una '''ruta de cavall''' és una seqüència de moviments de [[cavall (escacs)|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 d'escacs i matemàtica|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]].<ref>H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." ''Prentice Hall'', Upper Saddle River, New Jersey, pp. 326–328. 2003.</ref> Hi ha variacions del problema que impliquen escaquers de diferents mides a les usuals 8x8 caselles, així com taulers irregulars (no rectangulars).
{{clear}}

== Teoria ==
[[Fitxer:Knight's graph showing number of possible moves.svg|esquerra|miniatura|[[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.<ref>{{ref-publicació|nom=A. |cognom=Conrad |nom2=T. |cognom2=Hindrichs |nom3=H. |cognom3=Morsy |lastauthoramp=yes |nom4=I. |cognom4=Wegener |títol=Solution of the Knight's Hamiltonian Path Problem on Chessboards |publicació=Discrete Applied Mathematics |volum=50 |exemplar=2 |pàgines=125–134 |any=1994 |doi=10.1016/0166-218X(92)00170-Q}}</ref>
{{clear}}

== Història ==
[[Fitxer:Turk-knights-tour.svg|miniatura|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|s}}. Al ''[[Kavyalankara]]'' de Rudraṭa<ref>
{{ref-llibre|autor= Satyadev, Chaudhary
|títol= Kavyalankara of Rudrata (Sanskrit Text, with [[Hindi]] translation);
| editorial= Parimal Sanskrit Series No. 30
|lloc= Delhitraversal
}}
</ref> (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|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 {{nowrap|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 {{WCh|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 {{nowrap|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).<ref>{{ref-publicació|autor=Martin Loebbing; Ingo Wegener
 |títol=The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams
 |publicació=The Electronic Journal of Combinatorics
 |volum=3
 |exemplar=1
 |pàgines=R5
 |any=1996
 | url= http://www.combinatorics.org/Volume_3/Abstracts/v3i1r5.html
}} '''Important:''' Els autors posteriorment [http://www.combinatorics.org/Volume_3/Comments/v3i1r5.html 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.</ref><ref>{{ref-publicació
 |enllaçautor=Brendan McKay
 |autor=Brendan McKay
 |títol=Knight's Tours on an 8x8 Chessboard
 |publicació=Technical Report TR-CS-97-03
 |editorial=Department of Computer Science, Australian National University
 |any=1997
 |url=http://www.combinatorics.org/Volume_3/Comments/v3i1r5.01.ps
 |consulta=2013-04-06
 |arxiuurl=https://web.archive.org/web/20120127042807/http://www.combinatorics.org/Volume_3/Comments/v3i1r5.01.ps
 |arxiudata=2012-01-27
 }}</ref><ref>{{ref-llibre|autor= Wegener, I.
 |títol=Branching Programs and Binary Decision Diagrams
 | editorial=Society for Industrial & Applied Mathematics
 |any=2000
 | isbn=0-89871-458-3
 | url= http://books.google.cat/?id=-DZjVz9E4f8C&pg=PA369&dq=532}}</ref> 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 {{nowrap|6 × 6}}.<ref>{{MathWorld|urlname=KnightsTour|title=Knight's Tour}}</ref>

== Quins taulers tenen rutes possibles ==
Schwenk<ref>{{ref-publicació|autor=Allen J. Schwenk
 |títol=Which Rectangular Chessboards Have a Knight’s Tour?
 |publicació=Mathematics Magazine
 |any=1991
 |pàgines=325–332
}}</ref> va demostrar que per qualsevol tauler {{nowrap|''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.<ref>{{ref-web|cognom=Cull|nom=Paul|títol=Knight's Tour Revisited|url= http://www.fq.math.ca/Scanned/16-3/cull.pdf|obra=Fibonacci Quarterly| consulta=5 d'agost de 2012}}</ref>

== 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ística|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<sup>51</sup> possibles seqüències de moviments,<ref>{{ref-web|url= http://www.josiahland.com/?p=781 |títol= Enumerating the Knight's Tour}}</ref> 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 [[Complexitat del temps#Temps polinòmic|temps polinòmic]].<ref>{{ref-publicació|cognom= Cull|nom= P.|coautors=DeCurtins, J.|títol= Knight's Tour Revisited|publicació= Fibonacci Quarterly|volum= 16|data= juny de 1978|pàgines= 276–285}}</ref><ref>{{ref-publicació|cognom= Parberry|nom= Ian|títol= An Efficient Algorithm for the Knight's Tour Problem|publicació= Discrete Applied Mathematics|volum= 73|any= 1997|pàgines= 251–260|doi= 10.1016/S0166-218X(96)00010-8|url= http://larc.unt.edu/ian/pubs/algoknight.pdf|consulta= 2013-04-09|arxiuurl= https://web.archive.org/web/20130927194856/http://larc.unt.edu/ian/pubs/algoknight.pdf|arxiudata= 2013-09-27}}</ref>

=== Solucions de xarxa neuronal ===
<!-- [[Fitxer:knightstour24x24.png|miniatura|Closed Knight's Tour on a {{nowrap|24 × 24}} board solved by a neural network.]] -->
Una possible solució al problema de la ruta del cavall passa per la implementació d'una [[xarxa neuronal]].<ref>Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." ''Neurocomputing'', 4(5):249–254, 1992.</ref> La xarxa queda definida pel fet que cada moviment legal de cavall és representat per una [[Neurona artificial|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ó:

::<math>
U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 2 - \sum_{N \in G(N_{i,j})} V_t(N)
</math>

::<math>
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.
</math>

on <math>t</math> representa intervals discrets de temps, <math>U(N_{i,j})</math> és l'estat de la casella de connexió neuronal <math>i</math> amb la casella <math>j</math>, <math>V(N_{i,j})</math> és el resultat de la neurona des de <math>i</math> a <math>j</math>, i <math>G(N_{i,j})</math> é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 <math>t</math> i el <math>t+1</math>. 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 ===
{{Diagrama d'escacs
| tright
|
| | | | | | | | 
| | | | | | | | 
|x3| |x7| | | | | 
| | | |x7| | | | 
| |nl| | | | | | 
| | | |x7| | | | 
|x2| |x5| | | | | 
| | | | | | | | 

|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<ref name="pohl"/> i un altre per Squirrel i Cull.<ref>{{ref-web|url= https://github.com/douglassquirrel/warnsdorff/blob/master/5_Squirrel96.pdf?raw=true |títol=A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards | consulta=21 d'agost de 2011 |cognom=Squirrel |nom=Douglas |coautors=Cull, P. |any=1996}}</ref>

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 (teoria de grafs)|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.<ref name="pohl">{{ref-publicació|cognom= Pohl|nom= Ira|títol= A method for finding Hamilton paths and Knight's tours|publicació= Communications of the ACM|volum= 10|exemplar= 7|data= juliol de 1967|pàgines= 446–449|url =http://portal.acm.org/citation.cfm?id=363463|doi = 10.1145/363427.363463}}</ref> El problema del cavall és un cas especial.<ref name="alwan-waters">{{cite conference| first=Karla |last=Alwan| coauthors=Waters, K.| title=Finding Re-entrant Knight's Tours on N-by-M Boards|conference=ACM Southeast Regional Conference| publisher= [[Association for Computing Machinery|ACM]] | location=New York, New York| pages=377–382| year=1992| url= http://portal.acm.org/citation.cfm?id=503806| format= [[PDF]] | accessdate=2008| doi = 10.1145/503720.503806}}</ref>

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.<ref name="alwan-waters"/>

== Vegeu també ==
* [[Abu-Bakr Muhammad ben Yahya as-Suli]]
* [[George Koltanowski]]
* [[Problema de la ruta de cavall més llarga sense creuaments]]
* [[Vuit reines]]

== Notes i referències ==
{{Referències}}

== Enllaços externs ==
{{commonscat}}
* [http://www.mayhematics.com/t/t.htm Notes sobre la ruta del cavall]

[[Categoria:Problemes d'escacs i matemàtica]]
[[Categoria:Algorismes de grafs]]