Enigma del cavallo sulla scacchiera :)

Salve a tutti. Mi stavo allenando a fare algoritmi sfruttando degli esercizi carini trovati su un libro per linguaggio C. Mi sono imbattuto in un enigma proposto dal libro che ho risolto, più o meno, in una mezza giornata abbondante.

L'enigma è il seguente: può un cavallo, posizionato in un punto qualsiasi della scacchiera, percorrere tutte le caselle della scacchiera senza mai calpestare 2 volte la stessa casella?

Su internet ho trovato che è possibile ma i miei programmi "intelligenti" non sono riusciti a trovare una combinazione superiore di 57 passi prima di bloccarsi inesorabilmente in un tappo.
Il mio secondo approccio è stato bruteforce. Cioè, non ho provato tutte le possibili combinazioni xD Quello che ho fatto è un bruteforce randomico. Il cavallo percorreva a caso una strada, c'era un contatore che verificava se questo nuovo percorso era migliore dei precedenti e se la risposta era affermativa stampava a video il percorso fatto altrimenti ricominciava da zero.
Con questo approccio (che ho chiamato "ignorante") sono arrivato a trovare un percorso di 62 caselle però dopo circa 1 ora e mezza.

Senza scoraggiarmi ho ripreso oggi il problema e ho tentato il tutto e per tutto per trovare questa maledetta strada di 64 caselle. L'idea era di fare qualcosa di drastico.
Per prima cosa ho abbandonato C e preso Java poiché mi veniva in mente solo un algoritmo facilmente implementabile con quest'ultimo. Poi ho creato un algoritmo ricorsivo che richiama se stesso 8 volte, una per ogni percorso disponibile. Se questo percorso fa cadere il cavallo su una casella già calpestata o se esce fuori dalla scacchiera allora il metodo ricorsivo semplicemente finisce con un return vuoto, altrimenti controlla se sono state fatte tutte e 64 le caselle e in questo caso stampa a video il percorso e finisce con un return. Altrimenti ciò che fa è tentare tutte le 8 possibili combinazioni che un cavallo può effettuare con una chiamata ricorsiva.

Inserisco il codice (premetto che è un po' pasticciato. Non ricordavo alcune cose perché non uso java da diversi mesi quindi ho inserito alcune cose che per molti sembreranno ridondanti ):

import com.horstmann.ccj.ConsoleReader;

public class Scacchiera
{
    static int orizzontale[] = new int[8], verticale[] = new int[8];
    static int contatore = 0;
    static int record = 0;
    
    public static void main(String[] args)
    {
        ConsoleReader input = new ConsoleReader(System.in);
        int tavola[][] = new int[8][8];
        int mossa = 0, riga, colonna;
        
        orizzontale[0] = 2; orizzontale[1] = 1; orizzontale[2] = -1;
        orizzontale[3] = -2; orizzontale[4] = -2; orizzontale[5] = -1;
        orizzontale[6] = 1; orizzontale[7] = 2;
        verticale[0] = -1; verticale[1] = -2; verticale[2] = -2;
        verticale[3] = -1; verticale[4] = 1; verticale[5] = 2;
        verticale[6] = 2; verticale[7] = 1;
        
        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            {
                tavola[i][j] = 0;
            }
        }
        
        System.out.println("Inserire la posizione di partenza");
        
        System.out.println("Riga: ");
        riga = input.readInt();
        while(riga < 0 && riga >= 8)
        {
            System.out.println("Riga:(tra 0 e 7) ");
            riga = input.readInt();
        }
        
        System.out.println("Colonna: ");
        colonna = input.readInt();
        while(colonna < 0 && colonna >= 8)
        {
            System.out.println("Colonna:(tra 0 e 7) ");
            colonna = input.readInt();
        }
        
        tavola[riga][colonna] = ++mossa;
        
            int i = 0;
            int q,w,e,r,t,y,u,o;
            q=w=e=r=t=y=u=o=++mossa;
            int[][] aa,bb,cc,dd,nn,ff,gg,hh;
            aa=bb=cc=dd=nn=ff=gg=hh=tavola;
            scegliStradaRic(aa, riga+verticale[i], colonna+orizzontale[i], q); i++;
            scegliStradaRic(bb, riga+verticale[i], colonna+orizzontale[i], w); i++;
            scegliStradaRic(cc, riga+verticale[i], colonna+orizzontale[i], e); i++;
            scegliStradaRic(dd, riga+verticale[i], colonna+orizzontale[i], r); i++;
            scegliStradaRic(nn, riga+verticale[i], colonna+orizzontale[i], t); i++;
            scegliStradaRic(ff, riga+verticale[i], colonna+orizzontale[i], y); i++;
            scegliStradaRic(gg, riga+verticale[i], colonna+orizzontale[i], u); i++;
            scegliStradaRic(hh, riga+verticale[i], colonna+orizzontale[i], o); i++;
        
    }
    
    static void scegliStradaRic(int[][]tavola, int riga, int colonna, int mossa)
    {
//tiene conto del numero di chiamate ricorsive effettuate
        contatore++; 

//verifica se questo percorso è legale, cioè se il cavallo non è uscito dalla scacchiera o se è finito su un percorso già calpestato
        if(riga < 0 || riga >= 8 || colonna < 0 || colonna >= 8 || tavola[riga][colonna] != 0)
            return;

//un else ridondante, lo so. Volevo andare sul sicuro :)
        else {
            tavola[riga][colonna] = mossa;

// se la mossa è migliore delle precedenti stampa a video la scacchiera
            if(mossa > record) {
                record = mossa;
                System.out.println("Chiamata ricorsiva: RECORD #"+record+". Chiamata #"+contatore+" per riga "+riga+" e colonna "+colonna+" mossa #"+mossa);
                visualizza(tavola);
            }
            
        if(mossa == 64)
        {
            System.out.println("Percorso completato! Stampa del percorso...");
            visualizza(tavola);
            return;
        }
            
            
//avevo paura che il numero di mosse o che la scacchiera stessa venisse aggiornata attraverso le chiamate a metodo, quindi per precauzione ho creato delle copie :)            
            int i = 0;
            int q,w,e,r,t,y,u,o;
            q=w=e=r=t=y=u=o=++mossa;
            int[][] aa,bb,cc,dd,nn,ff,gg,hh;
            aa=bb=cc=dd=nn=ff=gg=hh=tavola;

//chiamate a metodo per ogni possibile combinazione di passi che può fare il cavallo
            scegliStradaRic(aa, riga+verticale[i], colonna+orizzontale[i], q); i++;
            scegliStradaRic(bb, riga+verticale[i], colonna+orizzontale[i], w); i++;
            scegliStradaRic(cc, riga+verticale[i], colonna+orizzontale[i], e); i++;
            scegliStradaRic(dd, riga+verticale[i], colonna+orizzontale[i], r); i++;
            scegliStradaRic(nn, riga+verticale[i], colonna+orizzontale[i], t); i++;
            scegliStradaRic(ff, riga+verticale[i], colonna+orizzontale[i], y); i++;
            scegliStradaRic(gg, riga+verticale[i], colonna+orizzontale[i], u); i++;
            scegliStradaRic(hh, riga+verticale[i], colonna+orizzontale[i], o); i++;
                }
    }
    
//metodo per visualizzare lo stato della scacchiera
    static void visualizza(int[][]tavola)
    {
        System.out.println("");
        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            {
                if(tavola[i][j] <10) System.out.print("[ " +tavola[i][j]+ "]");
                else System.out.print("[" +tavola[i][j]+ "]");
            }
            System.out.println("");
        }
        System.out.println("");
    }
}

Anche con questo metodo che dovrebbe funzionare per forza non riesco a trovare questa maledetta combinazione di passi. Sapreste dirmi dove ho sbagliato? :S Sicuramente è un errore stupido messo da qualche parte che mi sfugge :S