Estaba intentando hacer hace unas semanas un ejercicio que dicen que son comunes en las universidades, talvez me pueden explicar como se hacen estos ejercicios asi.
El ejercicio es hacer un programa que muestre la solucion del juego del Caballo del Rey algo asi. Para jugar se hace asi: En un papel creas una zona de 5 x 5 casillas ( un total de 25 casillas xD) y empiezas donde quieres escribiendo el numero 1 dentro de la casilla que quieras comenzar; luego haces movimientos del caballo como en el ajedrez y donde termine el "salto" del caballo, que es formando una L siempre, ahi pones el numero 2, y todo asi hasta poner el numero 25, pero que pasa? si un movimiento cae donde habia un numero ya escrito no se puede, y si intentan hacerlo como digo, en un papel y lapicera, veran que esta dificil xD

La idea del programa es hacer que el usuario indique el numero de casillas que habra y luego la posicion donde empezara el caballo, y el programa tendra que generar la solucion, mostrando todos los numeros.

Yo ya hice una matriz de 2 dimensiones para manejarme con X e Y para las posiciones de las casillas donde me voy posicionando.
Tambien hice otras cosas y por ahora funciona de modo que juega como si lo hariamos nosotros en un papel y lapicera, es decir, pierde xD

Pero lo que pido es que me digan como se hacen estos ejercicios, no hablemos de codigos ni nada, solo hablando que me expliquen como se hacen, ya que lei que estos ejercicios son los de "volver un paso atras y repetir" algo asi, asique un metodo hay y por lo que entiendo creo que ejercicios como ese se solucionan de la misma forma como si quisieras hallar un camino, por ejemplo:


Si la solucion es 2 b, lo que tendriamos que hacer es que verifique 1 a, y si no es que vuelva hacia atras y verifique 1 b, despues lo mismo y 1 c, y despues volver mas todavia atras para probar con 2 a y todo asi, pero a ver que me dicen y como lo aplicarian con el reto del caballo.

pd: Por las dudas me faltan 2 años para la universidad.. no es una tarea, solo que partiendo de ese metodo, hare el reto del caballo para verificar y luego resolvere un juego de mesa que tengo en casa xD

Espero que me ayuden, nos vemos

Se llama el recorrido del caballo ( Knight's tour en inglés) y es un ejemplo clásico de un problema a resolver utilizando backtracking, también llamado búsqueda con retroceso.

BackTracking, gracias! buscare pero si quieres hacer el taller pajaras me gustaria, se ve que es algo facil entonces, solo me falta entender la idea, despues veo si es algo parecido a lo del diagrama de arbol que pensaba yo, muchas gracias a todos!

El de nombre raro, creo que es haxfox, si mi Japones no me falla.. xD .. como lo hiciste tan facil? Recursivamente y al azar? yo tengo ya el proyecto que lo que hace es eso mismo pero que pasa.. demora 1 min en conseguir la solucion y si el usuario pone de 8 x 8, mi programa demora como 5 o mas minutos en encontrar la solucion xD
Y depende de la posicion a veces no hay solucion creo, asique no se como hiciste xD

Si dices que lo hiciste pero con papel y lapicera, bueno.. yo lo hice tambien pero hasta me di cuenta de como se hace cuando es 5 x 5 u 8 x 8 pero en algunas posiciones no funciona mi metodo. Pero la idea del ejercicio este es usar lo de BackTracking, ya que para luego que entienda como se hace eso, hare un programa para que me diga la solucion a uno de esos juegos de que tenes que ir comiendo fichas hasta quedarte con una sola, pienso que seria usando backtracking tambien.

Gracias a todos!

Por ahi, en vez de backtracking, fijate si podes hacerlo con BFS, estoy casi seguro q se puede... El problema puede llegar a ser el consumo de Ram que puede realmente irse muy alto...

Lo agrego a favoritos y si mañana tengo tiempo subo el codigo para ver q onda.

EDIT: Me puse a pensar un poco mas como era el juego este, y la verdad es que hacer BFS no tiene ninguna ventaja, el grafo del juego tiene forma de arbol, hacer backtracking en este caso es igual a hacer DFS.

HaxFox, lo decia en broma a lo de japonés jaja.
Tu solucion esta por internet muy repetida, pero ves que lo hiciste sin pensar, ahora intenta hacer el de 8 x 8 xD
Hasta el 8 llegaste haciendo mi metodo y decirte que empezando por las puntas hay mas posibilidades de que ganes, intenta empezando por otro lado xD ( aunque en algunas posiciones no hay soluciones, o por lo menos usando mi metodo)

Lo que yo hago no es nada raro, solo me di cuenta despues de lograr hacerlo una vez y analizar como lo habia hecho.
Vos te tenes que poner a pensar que son 8 movimientos los posibles e intenta hacerlos para que afuera de la zona siempre algo asi:


Y con el de 8 x 8 lo haces asi tambien y listo xD

Pero repito, yo lo que queria saber era como se hacian esos ejercicios de volver hacia atras, porque algo habia leido sobre eso, y entonces luego con backtracking hare el otro juego que hablo, que para ese si que no hay metodo xD