El recorregut del Cavall

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

knight-vs-white-set

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

chess-graphics-5

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.

Deja un comentario