El recorregut del Cavall en un tauler d’escacs

 

Les propietats del cavall en el tauler d’escacs han despertat sempre moltes inquietuds i admiració. De fet, es coneix una llegenda amb diverses variants i en molts idiomes sobre l’origen dels escacs que tracta precisament aquesta qüestió.

 

 

L’original forma de moure’s del cavall té la seva lectura matemàtica. Amb motiu de l’actuació d’un nen de 9 anys en un programa concurs de la televisió alemanya, Frederic Friedel ens desvetlla els misteris d’aquesta circumstància:

 

Això va succeir fa exactament 7 anys. El mes de febrer de 2003 un nen de 9 anys va causar sensació en el programa concurs de la televisió alemanya Wetten dass..?, que correspondria aproximadament amb el que en la televisió espanyola es coneixia com a ¿Qué apostamos? i el format del qual consisteix en que un grup de candidats proposen una sèrie de proves que asseguren ser capaces de superar en directe, davant de les càmeres.

 

El noi es diu Xaver Neuhäusler i procedeix de Bavaria. L’aposta era que podia completar un recorregut del cavall pel tauler d’escacs, completament de memòria, començant per qualsevol casella. El que es coneix com a recorregut del cavall (en anglès, knight’s tour) és una seqüència de 64 jugades amb el cavall executades de manera que només passi una vegada per cada casella del tauler. Se li van tapar els ulls a Xaver i la casella d’inici se li anava comunicant cada vegada. Sense massa esforç el noi anava dictant la seqüència de 64 caselles que servien per a completar el recorregut perfecte. La reacció del públic alemany després d’aquesta fita va ser aclaparadora: els diaris se’n van fer ressò, la gent ho discutia en trens i autobusos, en oficines i escoles. A tot arreu.

 

Per a intentar explicar-vos com ho va fer, primer fem un cop d’ull a la mecànica del recorregut del cavall. Hi ha algun llibre que ho explica: es tracta d’una seqüència de jugades efectuada amb aquesta peça de manera que es recorri tot el tauler, visitant cada casella només una vegada. Les preguntes formulades eren si el cavall podia efectivament caminar aquest camí i, en cas afirmatiu, quants recorreguts diferents són possibles. A la primera qüestió es va respondre ja en el segle IX, en un manuscrit àrab d’Abu Zakariya Yahya ben Ibrahim al-Hakim. L’autor esmenta dos recorreguts, un d’Ali C. Mani (que d’altra forma hagués estat un desconegut jugador d’escacs) i l’altre del-Adli ar-Rumi, que va tenir el seu moment més àlgid cap a l’any 840 i se sap que va escriure un llibre sobre el Shatranj, la forma d’escacs populars en aquells dies. Un recorregut tancat és aquell en el qual la casella final està a un salt de cavall de la casella inicial. El mestre de Shatranj, As-Suli, que va fonamentar els seus treballs en els del-Adli (al que va criticar), va publicar els següents dos recorreguts tancats: El primer exemple mostra una simetria axial perfecta en la meitat esquerra del tauler, mentre que el segon es compon de dos recorreguts de la meitat del tauler gairebé simètrics. El primer estudi matemàtic ampli del recorregut del cavall va ser presentat pel matemàtic del segle XVIII Leonhard Euler (1707?1783) a l’Acadèmia de les Ciències de Berlín, l’any 1759 . L’Acadèmia havia proposat un premi de 4000 francs per a la millor memòria sobre el problema, però la recompensa mai es va arribar a adjudicar, probablement perquè Euler era en aquella època el Director de Matemàtiques de l’Acadèmia de Berlín i suposem que com a tal no podia optar al guardó.

 

Aprendre un recorregut tancat té l’important avantatge de permetre-li començar per qualsevol casella del tauler i poder completar el recorregut des d’aquesta. Quants recorreguts hi ha? El nombre de recorreguts possibles és sorprenentment enorme. En realitat és tan gran que el seu compte està fora de l’abast humà, fins i tot emprant els més ràpids ordinadors existents en l’actualitat. El problema s’ha d’analitzar d’una altra manera.

 

L’any 1995 Martin Löbbing i Ingo Wegener van proclamar que el nombre total de recorreguts del cavall era 33.439.123.484.294 . Van obtenir aquest resultat després de fer treballar a 20 estacions de treball Sun durant 4 mesos. El 1997 Brendan McKay va emprar un altre mètode (dividint el tauler en dues meitats) i va obtenir com a resultat 13.267.364.410.532 . Perquè us pugueu adonar de la magnitud d’aquestes xifres, un ordinador investigant els recorreguts a la velocitat d’un milió de recorreguts per minut necessitaria més de 25 anys per a calcular el nombre de recorreguts donat per McKay.

 

Pel que fa al recorregut màgic, si vols saltar a la fama, no t’hauries d’aprendre només un dels recorreguts tancats, sinó que t’hauries de llançar per un recorregut màgic. Si es numeren els salts del cavall en un recorregut màgic resultarà un quadrat màgic. Es tracta d’una disposició dels nombres d’un a un en una matriu, en la qual cada nombre apareix només una vegada i en la qual la suma de les entrades en qualsevol fila, columna o diagonal és la mateixa. Els recorreguts completament màgics no són possibles en taulers de n x n caselles, amb nombres imparells i es creu que tampoc són possibles en el tauler d’escacs de 8×8 . El recorregut “més màgic” del cavall en un tauler d’escacs és el que les diagonals principals sumen 348 i 168 . Combinant dos mitjans recorreguts es pot obtenir un recorregut completament màgic, en el qual les diagonals sumen 260, però els punts 32 i 33 no estan units per un salt de cavall d’escacs.

 

En el segle XIX H. C. Warnsdorff va presentar un mètode pràctic de construir recorreguts del cavall (Donis Rösselsprungs einfachste und allgemeinste Lösung, Schmalkalden, 1823). L’objectiu és simplement evitar crear fins de trajecte, és a dir, caselles en les quals el cavall no pugui continuar, a l’haver de saltar a una casella ja visitada. Per aquesta raó, les possibles caselles han d’examinar-se abans de cada salt. Així dons, s’ha de comptar el nombre de possibilitats noves de salt que té cadascuna i es mou a la que tingui el nombre més baix de noves opcions de salt. Així de fàcil.