Problema del cavallo

scacchiUn 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.

Progettare un algoritmo per partire da una posizione data e fare eseguire al cavallo le mosse per effettuare un giro completo, passando esattamente una volta su ogni posizione. 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.

scacchi2Nella 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…

scacchi3

Soluzione linguaggio C

Il problema delle 100 caselle

broccoSe 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.

RISORSE ONLINE