Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Movimento del cavallo

Precedente
SUPERIORE
Successiva
F. Scheid - Calcolatore e programmazione - Etas

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

8 1       3      
7     2          
6 3 2     3      
5   3   3     4  
4                
3               5
2   8       6    
1       7        
a b c d e f g h

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

8 1              
7     2          
6   32     3      
5 34     27     4  
4 31 10 33     26 23  
3 18 35 28 11 24 21 14 5
2 9 30 19 16 7 12 25 22
1 36 17 8 29 20 15 6 13
a b c d e f g h

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)

8 1 42 13 28 3 44 15 30
7 24 27 2 43 14 29 4 45
6 41 12 25 60 53 64 31 16
5 26 23 52 63 56 59 46 5
4 11 40 61 58 51 54 17 32
3 22 37 50 55 62 57 6 47
2 39 10 35 20 49 8 33 18
1 36 21 38 9 34 19 48 7
a b c d e f g h

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

Movimento del cavallo - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Precedente
SUPERIORE
Successiva