Ejercicio de Universidad..

[$Edu$]

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

[]_HQH_[]

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

[$Edu$]

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

[Ragnarok]

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.

Código [Seleccionar] Expandir

module MyBacktrac (backtracking) where
import List

backtracking::
     (tsolucionParcial -> tsolucionParcial -> Ordering) -- Ordenar para A*
     -> (tsolucionParcial -> Bool)                   -- EsSolucionFinal?
     -> (tsolucionParcial -> tsolucion)              -- Convertir
     -> (tsolucionParcial -> [tsolucionParcial])     -- Ampliar
     -> (tsolucionParcial -> Bool)                   -- EsValida?
     -> [tsolucionParcial]                           -- Estado inicial
     -> Maybe tsolucion

backtracking _ _ _ _ _ [] = Nothing
backtracking orden essolucion convertir ampliar esvalida (sp:sps)
     | essolucion sp = Just (convertir sp)
     | otherwise = (backtracking orden essolucion convertir ampliar esvalida)
           (sortBy orden ((filter esvalida (ampliar sp)) ++ sps))

[$Edu$]

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

[farresito]

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

[$Edu$]

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

[farresito]

He juntado varios links que aparentemente me parecieron útiles.

http://vpdesai.tripod.com/ktour.htm
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 →Para los que quieran practicar un poquitín

Un abrazo!