Crea sito

Salto del cavallo

Si tratta di visitare una volta sola tutte le case della scacchiera utilizzando le mosse del cavallo.

Ogni casa della scacchiera sarà rappresentata da un numero intero, zero per le case non visitate ed il numero di mossa per le altre.

L’algoritmo di backtracking sarà implementato con un metodo statico cui passeremo:

  • la scacchiera, ovvero lo stato della ricerca
  • la mossa candidata
  • il numero della mossa da giocare

pseudocodifica:

  • segniamo la mossa sulla scacchiera
  • se abbiamo visitato tutte le case: mostriamo la scacchiera
  • per ogni mossa possibile: proseguiamo ricorsivamente la ricerca

nota bene: quando si richiama ricorsivamente il metodo backtracking

  • la scacchiera deve essere copiata con un costruttore di copia
  • il numero di mossa deve essere incrementato

Il codice PHP può essere eseguito a questo indirizzo.