Un famoso problema che riguarda gli scacchi è quello del cavallo che deve visitare tutta la scacchiera.
Il cavallo è il pezzo degli scacchi che salta.
Nella figura sono evidenziate 8 mosse successive del cavallo e in particolare sono presentate le mosse disponibili dopo la seconda mossa.
Si può muovere dalla posizione i alla posizione i+1 se lo spostamento comprende uno spostamento di due righe e di una colonna o viceversa.
Algoritmo
Un algoritmo di backtracking puro (cioè che tenta tutte le mosse senza alcuna tecnica euristica) costringerà a tempi d’attesa lunghissimi perché dopo pochi passi si finirà ripetutamente in vicoli ciechi.
Nella figura, alla 36° mossa il cavallo è finito in a1 dove non ci sono mosse disponibili.
Euristica: ad ogni passo il cavallo deve scegliere la cella più isolata, o più vicina al bordo, prima che diventi troppo isolata…
Il problema delle 100 caselle
Se si cambiano le regole per il movimento da una casella all’altra della scacchiera si ottengono nuove varianti del problema
il cavallo (forse è un brocco…) deve visitare tutta la scacchiera (di dimensioni qualsiasi…) e si può muovere dalla posizione i alla posizione i+1 se lo spostamento comprende un salto di
- due righe
- due colonne
- due righe e due colonne.
Nella figura sono evidenziate le possibili mosse al 3° e al 7° passo.