Salts de cavall

El cavall dels escacs és una peça amb unes regles de moviment diferents a les altres, no fa un recorregut per la «superfície» del taules on podria ser interceptada per una altra peça amiga o enemiga, sinó que «salta»: des de qualsevol casella pot anar a qualsevol de les vuit que hi ha a distància de dues unitats en un sentit i una en el perpendicular. Això és el màxim, si és prop de la vora del tauler, alguns salts el durien fora i no compten, és el cas de les quatre cantonades on un cavall només té dos moviments possibles.

Un aspecte bàsic del salt de cavall és que a cada passa canvia el color de la casella on va a parar. Conseqüència d’això és que per anar a una casella del mateix color, sempre li calen un nombre parell de jugades. Per exemple, amb dues jugades un cavall pot anar a qualsevol casella del mateix color situada a tres o menys caselles de distància en sentit horitzontal o vertical, llevat de les situades exactament a dues caselles de distància en diagonal que requereixen quatre salts. Això ho saben bé tots els jugadors d’escacs, desplaçar el cavall dues caselles en diagonal consumeix massa moviments i en molt pocs casos passa amb jugades consecutives en una partida real.

Un cas concret de moviment entre dues caselles del mateix color és anar de punta a punta d’una diagonal. Aquí el mínim és de sis salts. I la pregunta que faig és:
—Per quants recorreguts diferents es pot fer?

Un dels possibles recorreguts d’un cavall de punta a punta de la diagonal en 6 salts.
Tots els possibles recorreguts en sis salts superposats, és difícil comptar-los aquí.

Si el tauler no fos de 8 × 8 caselles, també ens podem plantejar la pregunta.

En un tauler de mida 1 × 1 la resposta és «degenerada» zero salts ens porten «de punta a punta» d’una sola manera possible. El cas de dimensió dos no té solució, en un tauler tan petit el cavall no es pot moure i no arribaria mai a l’altre extrem del tauler. El cas 3 és peculiar en un cert sentit, es precisen 4 salts i hi ha dos camins possibles simètrics depenent del primer salt.

Amb taulers més grans la cosa es posa més interessant, pel cas quatre la fàcil solució també són 2 possibles recorreguts; pel cas cinc 8 recorreguts; pel tauler de 6 × 6 en tenim 4; pel de 7 × 7 hi ha 6 solucions. Pel tauler normal de vuit caselles de mida, és la pregunta que he posat més amunt. Afegeixo que el cas 9 té 40 recorreguts i el cas 10 en té 20.

Tinc la seqüència ben determinada i la fórmula —de fet en són tres— que genera el nombre de solucions al problema. Com a prova puc posar aquí que per un tauler de 47 × 47 hi ha 225494871090 solucions i pel de 48 × 48 1591091500.

Naturalment que la primera gràcia del problema és inventar un mètode per comptar les solucions. La segona és molt més difícil, trobar les formules empíriques. La tercera, demostrar que són correctes. És un cas de mètode heurístic aplicat a una qüestió numèrica. Naturalment el problema es podria resoldre de manera totalment deductiva, però em temo que hauria sigut molt més difícil, crec sincerament que jo no ho hauria sabut fer.

Aquesta entrada ha esta publicada en Ciència i pensament, Divulgació, Educació, Problemes. Afegeix a les adreces d'interès l'enllaç permanent.

Deixa un comentari

L'adreça electrònica no es publicarà. Els camps necessaris estan marcats amb *

*