Un cavallo in una scacchiera

[vncnz]

Salve a tutti! Voglio creare un programma che calcola le mosse che deve fare un cavallo in una scacchiera (libera) per coprire tutte le caselle senza mai passare due volte sulla stessa... So usare (ehm... sono agli inizi, però!) c, c++ e python... Mi dareste le linee guida per realizzarlo? Ho analizzato il movimento in base agli assi x e y... Stavo pensando di salvare le caselle già "calpestate" in un array, ma boh... Non ho avuto idee che mi convincano, finora! Qualcuno mi sa dare un suggerimento?

[71104]

è un problema che può essere risolto in maniera banale (cioè algoritmo cagoso non ottimizzato) tramite backtracking: ogni volta che non hai più mosse torni indietro sui tuoi passi finché non trovi un altro percorso e continui da lì. trattandosi di backtracking io tanto per cominciare mi organizzerei con uno stack (anziché un array).

[vncnz]

Ehm... Cos'è il backtracking? Cioè, cos'è posso immaginarlo dal nome, ma materialmente parlando? Poi per l'ottimizzazione vedo dopo...

[stdecden]

É come dire: entrare in un labirinto e svoltare sempre a destra...
se entro in un vicolo cieco torno indietro e vado a sinistra...
e cosí via....

[D4rkAng3l]

Originariamente inviato da 71104

è un problema che può essere risolto in maniera banale (cioè algoritmo cagoso non ottimizzato) tramite backtracking: ogni volta che non hai più mosse torni indietro sui tuoi passi finché non trovi un altro percorso e continui da lì. trattandosi di backtracking io tanto per cominciare mi organizzerei con uno stack (anziché un array).

si però computazionalmente parlando credo diventi pesante se la scacchiera è grossa...cmq è un bell'esercizietto da fare con il PROLOG che implementa nativamente il backtracking anzi il backtracking è parte integrale del paradigma logico del prolog...

Un'altra idea magari sarebbe usare gli algoritmi basati sugli animali come le formiche...abbiamo trattato l'argomento all'ultima lezione di intelligenza artificiale.