----- 4/6/05 -----

> Ho scritto del codice per risolvere il problema del percorso del cavallo
> [...] ma non ho nessun dato per confrontare i risultati prodotti dal mio
> algoritmo [...]

Si tratta di un problema con un'elevatissima complessita' combinatoria.
Per esempio, fissando la posizione iniziale del cavallo sul quadrato in alto
a sinistra della scacchiera, il numero di soluzioni diverse e' zero per una
scacchiera 4 x 4,  304 nel caso 5 x 5,  524.486 nel caso 6 x 6 (che richiede
di attendere con pazienza il risultato).

> Calcolare un risultato "a mano" e' un po' dispersivo visto che ci sono
> al piu' otto possibilita' per ogni movimento e n*n caselle da riempire
> (se la scacchiera ha lato = n).

Come si capisce dai dati sopra riportati, e' inutile cimentarsi in una
verifica manuale.

Oltre a contare le soluzioni nel caso 5 x 5, per verificare almeno se un
programma trova soluzioni sensate si puo' visualizzare le configurazioni
della scacchiera numerando i quadrati secondo l'ordine del cammino del
cavallo.

A questo scopo si puo' fare riferimento a uno dei problemi proposti nelle
pagine del corso, voce "alcuni esempi" (dopo quelli discussi in classe).

----- 10/6/05 -----

> [C'e'] qualche dato disponibile sul numero di soluzioni del giro del
> cavallo per una scacchiera 5x5 [? ...]

Per una scacchiera 5 x 5 si rilevano i seguenti numeri di soluzioni,
cambiando il quadrato di partenza (identificato dalle coordinate di
riga e colonna:

      < 1, 1 >  -->  304
      < 1, 2 >  -->    0
      < 1, 3 >  -->   56
      < 2, 2 >  -->   56
      < 2, 3 >  -->    0
      < 3, 3 >  -->   64

Gli altri casi si evincono per simmetria.

Per inciso, ragionando sulla base di opportuni invarianti e' facile
dimostrare che a partire dai quadrati <1,2>, <2,3> e simmetrici non
e' possibile trovare soluzioni.

> Sulla scacchiera 6x6 dalla posizione (1,1) [il computer] e' ancora che
> calcola dopo [diverse] ore in background [...]

E' questo il fenomeno a cui ci si riferisce quando si parla di algoritmi
con complessita' di calcolo (a crescita) esponenziale: basta aumentare di
poco la dimensione dei dati di input e non si riesce piu' a pervenire al
risultato in tempi praticabili (non bastano ore o giorni!).

----- * -----