Hai un cavallo degli scacchi, una piccola scacchiera e una missione che sembra innocente: visitare ogni casella una sola volta e ritornare al punto di partenza con un’ultima mossa di cavallo. Non devi catturare pezzi, non ci sono avversari e puoi scegliere da dove iniziare.
Il cavallo non cammina sulle righe e sulle colonne: salta di due caselle in una direzione e di una in quella perpendicolare. Su una scacchiera 5 × 5 il problema si trasforma subito in un labirinto di tentativi. Ma siamo sicuri che cercare a lungo sia il modo giusto per risolverlo?
Questa volta la sorpresa è una dimostrazione di impossibilità che non richiede di esaminare tutte le mosse. Basta accorgersi di una proprietà che ogni salto conserva e ogni ritorno deve rispettare: l’alternanza dei colori.
PROBLEMA 1729 #051
Tempo: 10–15 minuti
Difficoltà: Medio
Categoria: Combinatoria e teoria dei grafi
Il problema
Considera una scacchiera composta da 5 righe e 5 colonne, con tutte le 25 caselle disponibili. Un cavallo parte da una casella a tua scelta. A ogni passo si muove come negli scacchi: due caselle lungo una coordinata e una lungo l’altra, purché la destinazione rimanga sulla scacchiera. Può esistere un percorso chiuso che attraversi tutte le 25 caselle esattamente una volta e dal quale, dopo la venticinquesima casella, sia possibile tornare alla prima con un unico salto legale?
Attenzione alla parola chiuso: un percorso che visita tutte le caselle senza poter tornare al punto iniziale non risolve la domanda. Prima di scoprire la soluzione, prova a colorare alternativamente di chiaro e scuro le caselle.
💡 Mostra un indizio
Non guardare tutte le destinazioni: osserva soltanto il colore della casella raggiunta dopo ciascun salto.
Se assegni al quadrato di coordinate (x,y) il colore in base alla parità di x + y, che cosa succede alla parità dopo una mossa (±1,±2) o (±2,±1)?
💡 Mostra un indizio
Ogni salto passa da un colore all’altro. Immagina ora di seguire il percorso e di aggiungere anche l’ultimo salto che riporta al punto iniziale.
Può un ciclo con un numero dispari di lati alternare due colori e chiudersi senza che due caselle consecutive abbiano lo stesso colore?
✅ Mostra la soluzione
Il salto del cavallo cambia sempre colore
Numeriamo le colonne e le righe con 1, 2, 3, 4, 5. Coloriamo una casella in modo che il suo colore dipenda dalla parità di x + y. Un salto del cavallo modifica una coordinata di 1 e l’altra di 2, con segni eventualmente diversi. La somma delle coordinate varia dunque di ±1 ± 2: può cambiare di 1, 3, −1 oppure −3. È sempre un numero dispari. Quindi ogni mossa porta inevitabilmente a una casella di colore opposto.
Perché 25 è un ostacolo
Supponiamo per assurdo che esista il percorso chiuso richiesto. Il cavallo passa per 25 caselle distinte; aggiungiamo anche la mossa finale dall’ultima casella alla prima. Avremmo così un ciclo di 25 salti, tutti fra colori opposti.
Partendo da una casella chiara, dopo il primo salto siamo su una scura, dopo il secondo di nuovo su una chiara e, in generale, dopo un numero dispari di salti siamo su una scura. Ma il venticinquesimo salto dovrebbe farci ritornare alla casella iniziale, che è chiara. Contraddizione. Non esiste un giro chiuso del cavallo su una scacchiera 5 × 5.
La stessa dimostrazione come grafo
Rappresentiamo ogni casella con un vertice e ogni salto legale con uno spigolo. Il grafo del cavallo è bipartito: i vertici chiari formano una parte, quelli scuri l’altra, e nessuno spigolo collega due vertici della stessa parte. Qualsiasi ciclo in un grafo bipartito ha lunghezza pari. Un ciclo che passa una volta per ciascuno dei 25 vertici avrebbe invece lunghezza 25, dispari. Il tour chiuso è quindi impossibile.
Un percorso aperto, invece, esiste
La conclusione non dice che il cavallo non possa visitare tutte le caselle. Ecco una sequenza verificabile di 25 caselle, usando le colonne a–e e le righe 1–5:
a1 → c2 → e1 → d3 → e5 → c4 → a5 → b3 → c1 → a2 → b4 → d5 → e3 → d1 → b2 → a4 → c5 → e4 → d2 → b1 → a3 → b5 → c3 → e2 → d4.
Ogni coppia consecutiva differisce di una e due unità nelle coordinate e non vi sono caselle ripetute. Puoi seguire l’ordine sulla griglia numerata qui sotto, in cui la riga 5 compare in alto:
a b c d e 5 7 22 17 12 5 4 16 11 6 25 18 3 21 8 23 4 13 2 10 15 2 19 24 1 1 20 9 14 3
L’ultimo punto d4 non è raggiungibile da a1 con un singolo salto: le differenze fra coordinate sono 3 e 3. Non possiamo chiudere il percorso, come il teorema aveva già stabilito.
Conclusione: 25 caselle possono essere percorse una sola volta in un cammino aperto, ma non possono formare un ciclo di mosse del cavallo.
La matematica dentro al gioco
Quello che abbiamo usato è un invariante di parità. Un invariante è una proprietà che resta controllabile lungo le mosse: il cavallo cambia colore obbligatoriamente, e proprio questa regola impedisce un ritorno dopo un numero dispari di salti.
È anche un esempio naturale della differenza fra un cammino hamiltoniano, che visita tutti i vertici una sola volta, e un ciclo hamiltoniano, che in più torna al vertice iniziale. Sulla scacchiera 5 × 5 il primo esiste, il secondo no.
Questo metodo va oltre gli scacchi: si usa in giochi di tassellatura, problemi di percorso, algoritmi e dimostrazioni di impossibilità. Prima di cercare una configurazione, conviene chiedersi se il problema ammette una soluzione in linea di principio.
Un riferimento per il linguaggio dei percorsi è Wolfram MathWorld, Knight’s Tour.
Una variante per te
Che cosa puoi dedurre per una scacchiera 7 × 7, oppure 9 × 9? Ripeti la dimostrazione: tutte hanno un numero dispari di caselle. La parità vieta anche lì un tour chiuso, senza bisogno di conoscere se esistano tour aperti.
Domanda più difficile: una scacchiera con un numero pari di caselle ammette sempre un percorso chiuso? No. La parità è una condizione necessaria, non sufficiente: per esempio su una scacchiera 2 × 4 il cavallo non può collegare tutte le caselle in un ciclo, perché la struttura dei salti è troppo povera.
Prova a disegnare il grafo delle mosse legali per il rettangolo 2 × 4: quali caselle hanno un solo possibile vicino? Una casella di grado 1 non può appartenere a un ciclo hamiltoniano, che richiede due spigoli incidenti per ogni vertice.
Lo sapevi?
Il giro del cavallo è un classico della matematica ricreativa, studiato attraverso costruzioni, simmetrie e metodi di ricerca. È strettamente collegato ai problemi di esistenza di cammini e cicli hamiltoniani sui grafi.
Gli algoritmi di ricerca possono trovare molti cammini aperti; una prova di parità, tuttavia, esclude tutti i cicli chiusi su scacchiere quadrate di lato dispari in una sola volta. È una differenza essenziale fra esibire un esempio e dimostrare un’impossibilità universale.
Per orientarsi tra i problemi combinatori, nella biblioteca del blog è disponibile Calcolo discreto. Metodi per contare di Carlo Mariconda e Alberto Tonolo, utile per sviluppare metodi sistematici di conteggio.
Problema 1729
#051 — Il cavallo sulla scacchiera: un giro impossibile?
Giochi, enigmi e idee matematiche per menti curiose.