Salto del cavallo

[ficus2002]

Supponiamo di avere una scacchiera 5x5 e un cavallo. Partendo dalla casella in alto a sinistra con 24 mosse si devono toccare una e una sola volta tutte le caselle.
Ecco un esempio:
$((1,6,11,18,23),(12,17,22,5,10),(7,2,13,24,19),(16,21,4,9,14),(3,8,15,20,25))$.
Quante soluzioni ha questo problema? Come si possono trovare esplicitamente tutte le soluzioni?

[codino75]

Quante soluzioni ha questo problema? Come si possono trovare esplicitamente tutte le soluzioni?

suggerisco di dotarsi di calcolatore... e un pochettino di ram

alex

[Cheguevilla]

Da qualche parte a casa dovrei avere un algoritmo che risolveva il problema su una scacchiera 10x10.
L'avevo fatto come esercitazione per l'esame di programmazione.
Il brute force è pesantuccio in termini di risorse...

[ficus2002]

"codino75":
suggerisco di dotarsi di calcolatore... e un pochettino di ram
alex

ci avevo pensato anch'io! Più che altro sono alla ricerca di qualche strategia che permette di trovare tutte le soluzioni. Per esempio, data una soluzione se ne possono trovare altre numerando al rovescio, oppure ruotando la scacchiera di 90 gradi.

Un modo che permette di trovare velocemente delle soluzioni è costrutire un grafo in cui i vertici sono le caselle della scacchiera e in cui due caselle sono connesse da uno spigolo se il cavallo può passare da una all'altra con una mossa. Con il linguaggio della teoria dei grafi, una soluzione del problema è una linea di Hamilton del grafo.

[codino75]

non ho capito la funzione dei numeri sulle celle della scacchiera
alex

[Fioravante Patrone1]

"codino75":non ho capito la funzione dei numeri sulle celle della scacchiera

"ficus2002":
Ecco un esempio:
$((1,6,11,18,23),(12,17,22,5,10),(7,2,13,24,19),(16,21,4,9,14),(3,8,15,20,25))$.

ciao

[Celine2]

[img]

Per codino 75
ho inserito solo i primi 5 salti del cavallo

[codino75]

ok ho capito. thanks