Foro de elhacker.net

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 ;)

joder facilisimo lo he hecho a la primera....

si quieres le hago una foto a la libreta y tal coloca el caballo abajo a la izquierda

metodo empleado: ninguno jajaja

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.

como dice akai es BACKTRACKING, googlea un poco, tambien puedes buscar ACCIONES I FUNCIONES RECURSIVAS, otro ejemplo tipico es el de poner 8 reinas en un tablero de ajedrez sin que se maten. Intentalo hacerlo a mano ya veras como es dificil, XD. Cuando acabe edamenes (poco queda :D ) te cuelgp mia apuntes de teoria de backtracking (recursividad) y haber si me animo a hacer un tutorial o taller.
Un saludo zero!

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!

La cosa sería usar backtracking o (creo que también valdría) ramificación y poda. En cualquier caso lo importante es recorrer el menor número de nodos del árbol de soluciones, para que así, el programa tarde el menor tiempo posible. Como dicen los demás, busca por Google algunos apuntes y a darle a la melondra xD. Saludos y suerte.

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.

Yo conseguir una solución, haciendo esto:

(http://img820.imageshack.us/img820/5594/caballov.jpg)


Al azar obviamente, yo no sé nada de Backtracking ni cosas de esas...

PD: no sabes japonés.. ハセヲ, = Haseo

Mi perfil es haxfox

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

Empeze a intentar ese ejercicio del caballo de nuevo, como ya habia dicho tenia todo creado para que juegue como lo hariamos nosotros con papel y lapicera, es decir, pierde el programa.
Ahora.. busque sobre backtracking pero o busque mal o no se, porque lo unico que entendi es lo que ya sabia, que hay que volver un paso atras, pero depende el ejercicio que sea va a ser de que forma vuelve atras asique no se.

Yo ahora lo que intente fue que cuando va poniendo numeros en la casilla con sus posiciones, esas posiciones se van guardando en 2 auxiliares antes de modificarse las posiciones originales, asi cuando ya no hay mas lugar pero porque perdi entonces cambia la posicion original por las auxiliares ( asi seria una posicion atras ) y borra la casilla que habia marcado ultimo. Luego intenta de nuevo los posibles movimientos que no sean el mismo de antes porque ya sabemos que no tendra solucion por ese lado.
Eso ultimo no se como hacerlo, y depurando el codigo me he dado cuenta que eso de las variables auxiliares funciona, pero va a ver una vez que hay que volver 2 pasos atras, asique tampoco se como hacerlo :/

No se si quieren que deje el codigo o me explican por arriba como lo podria hacer.

Gracias!

Pajaras, ahora que estas conectado.. cuando haras el tutorial que no he podido entender backtracking o no se que tengo mal xD

Este programa es tipico de ejemplo para quien se introduce en competiciones de programacion.

Recuerda siempre que el nombre lo dice, back-tracking es recorrer al reves... :) Y al recorrerlo, si un paso ha costado mas que el anterior, no lo hagas.

Aqui tienes información sobre algoritmica
 http://hispabyte.net/foro/index.php?board=92.0

Si me puedes dar una mano te agradezco mucho, mira.. yo lo que primero hice fue que mi programa haga movimientos en sentido del reloj hasta que no haya mas solucion, entonces ahi vuelve una posicion atras y anota el movimiento que hizo la ultima vez, para repetir eso pero con el movimiento anterior. Despues me di cuenta que tendria problemas con eso, ya que despues que avanza ese mov anterior no lo cambio y haria un paso menos.

Entonces hice una lista de los movimientos y usaba solo el ultimo, pero tampoco funciono, entonces yo ahora uso un array multidimensional que voy a ir anotando los movimientos para cada numero de paso en su posicion en el tablero y el movimiento que hizo.

Pero me acabo de dar cuenta que haciendo otros movimientos se puede llegar al mismo numero y la misma posicion, entonces otra vez me caga todo :S

Si no me entiendes pregunta, aunque como ves estoy perdido y si me explicas desde 0 es mejor, espero que me ayudes ya que entre al foro q pasas y sobre el ejercicio este no habla pero hay otras cosas si y me cuesta mucho entender mirando codigo simplemente

Lo más fácil es hacerlo con backtracking, como ya han dicho.
http://es.wikipedia.org/wiki/Backtracking

Es mucho más eficiente hacerlo con restricciones:
http://es.wikipedia.org/wiki/Programaci%C3%B3n_con_restricciones

Esto es el código del algoritmo de backtracking mejorado, hace BEP igual que bactracking, pero en cada bifurcación escoge el camino más prometedor dependiendo de la heurística que le pongas en lugar de escoger uno aleatoriamente.

Sigo sin entender :S, no podrias decirme con palabras los pasos a seguir, q yo despues veo como lo implemento, pero siendo mas puntual claro

Mira en links. Está en Python. Lo vas a poder pasar fácilmente
http://es.m.wikipedia.org/wiki/Problema_de_los_movimientos_de_un_caballo

Pero veo que usa Random y la idea es no usar random, porque con random ya lo tengo, pero bueno.. esperare hasta la universidad, gracias a todos

He juntado varios links que aparentemente me parecieron útiles.

http://vpdesai.tripod.com/ktour.htm (http://vpdesai.tripod.com/ktour.htm)
http://hurring.com/scott/code/java/knighttour/ (http://hurring.com/scott/code/java/knighttour/) →Según comenta el autor, está muy poco optimizado, así que deberás mejorarlo
http://www.brainbashers.com/knight.asp (http://www.brainbashers.com/knight.asp) →Para los que quieran practicar un poquitín ;)

Un abrazo!