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