Uno dei più famosi problemi di scacchi è quello del movimento del cavallo (knight). Il cavallo è quel pezzo degli scacchi che "salta". Come si vede in figura, si può muovere dalla posizione i alla posizione i+1, con ogni movimento che comprende uno spostamento di due righe e una colonna o viceversa (in colore alcune mosse alternative).

I movimenti del cavallo consistono in una sequenza di mosse che passano esattamente una volta su ogni posizione.

Progettare un algoritmo per partire da una posizione data e fare eseguire al cavallo le mosse per effettuare un giro completo. Saranno richieste 63 mosse.

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 a sinistra, alla 36° mossa il cavallo è finito in a1 dove non ci sono mosse disponibili)

Bisogna favorire le celle più isolate prima che diventino troppo isolate.

Le scelte utili per la prossima prossima cella allora sono: la più vicina al bordo, quella con meno possibilità di movimento, ...