Il giro del cavallo | Regola di Warnsdorff, giri aperti e chiusi

Un rompicapo antico

Nel Kavyalankara, scritto dal poeta indiano Rudrata nel IX secolo, un verso è disposto su mezza scacchiera in modo da poter essere letto lungo il percorso di un cavallo. Leonhard Euler scrisse il primo studio matematico del giro del cavallo nel 1759, con metodi per costruire giri e trasformarli in giri chiusi.

Un cammino in un grafo

Immagina ogni casella come un punto e ogni mossa di cavallo come una linea tra due punti. Un giro del cavallo è allora un cammino che visita ogni punto esattamente una volta, che i matematici chiamano cammino hamiltoniano; un giro chiuso è un ciclo hamiltoniano. Nella maggior parte delle reti un cammino così è molto difficile da trovare. La rete del cavallo è generosa: ha così tanti giri che una buona regola ne trova uno in fretta.

La regola di Warnsdorff

H. C. von Warnsdorff descrisse la sua regola nel 1823: saltare sempre sulla casella che lascia meno mosse successive. Le caselle lungo il bordo hanno pochi vicini, quindi la regola le visita presto invece di lasciarle isolate. Quando due caselle sono alla pari serve una scelta, e una scelta sfortunata può comunque bloccare il cavallo. Nell’app, i numeri dorati indicano le caselle che la regola sceglierebbe.

Ricerca con backtracking

Risolvi segue l’ordine di Warnsdorff ma non si fida ciecamente. Cerca in profondità, e appena una casella non visitata non è più raggiungibile abbandona quel ramo e prova la mossa successiva. Sulle scacchiere fino a 10×10 di solito trova subito un giro. Quando il tuo percorso ha intrappolato il cavallo, prima torna indietro di qualche mossa.

Colori e giri chiusi

Ogni mossa di cavallo cambia il colore della casella. Su una scacchiera di lato dispari come la 5×5 c’è una casella in più del colore degli angoli rispetto all’altro, quindi un giro deve iniziare e finire sul colore degli angoli. Lì un giro chiuso è impossibile, perché un anello che alterna i colori ha tante caselle di un colore quante dell’altro. Sulle scacchiere di lato pari i giri chiusi esistono a partire da 6×6.

Provalo in PictorX

Apri Giro del cavallo e fai clic su una casella per iniziare. Le caselle evidenziate sono i salti consentiti, il numero dorato è la scelta di Warnsdorff, e la scacchiera conserva l’ordine delle tue mosse. Dimensione imposta la scacchiera da 5×5 a 10×10, «Giro chiuso» chiede a Risolvi un anello, e Annulla ritira qualsiasi mossa. Salva il percorso finito come PNG.

Domande frequenti

Chi ha studiato per primo il giro del cavallo?

I giri erano noti molto prima che qualcuno li studiasse matematicamente. Leonhard Euler scrisse la prima trattazione matematica nel 1759, e Warnsdorff formulò la sua regola nel 1823.

Esiste un giro su ogni scacchiera?

Le scacchiere quadrate a partire da 5×5 hanno giri aperti, e quelle di lato pari a partire da 6×6 hanno anche giri chiusi. Le scacchiere 2×2, 3×3 e 4×4 non hanno alcun giro.

Quanti giri ha una scacchiera?

Ci sono 26.534.728.821.064 giri chiusi, se un giro e lo stesso giro percorso all’indietro si contano separatamente. Il numero di giri aperti è di circa 19,6 biliardi.

PictorX carica qualcosa?

No. La scacchiera è disegnata su una tela nel browser. Salva scarica un PNG, e Modifica apre quell’immagine nell’editor di PictorX.