Enigma del cavallo sulla scacchiera :)

di il
1 risposte

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

1 Risposte

  • Re: Enigma del cavallo sulla scacchiera :)

    
                int[][] aa,bb,cc,dd,nn,ff,gg,hh;
                aa=bb=cc=dd=nn=ff=gg=hh=tavola;
    
    Non so perche', ho perso il post che stavo editando. Chiedo scusa se il post appare due volte.
    Con il codice di cui sopra, vai a creare dei "sinonimi" dello stesso oggetto: aa,bb,...hh,tavola puntano tutti allo stesso oggetto.
    In realta', ogni volta che sei ad un bivio, dovresti fornire una copia del percorso fino al punto raggiunto, una per ogni nuova strada che decidi di intraprendere. Capirai che la quantita' di memoria necessaria tendera' a crescere velocemente.

    Puoi controllare anche wikipedia per cercare piu' informazioni sul problema in questione:
    https://it.wikipedia.org/wiki/Percorso_del_cavall
Devi accedere o registrarti per scrivere nel forum
1 risposte