Resolver Sokoban

propuesto por josejuan

Resolver de forma automática un sokoban. Sugiero tomar como base la solución escrita para el problema "Kata TDD. Sokoban (el juego) en Haskell" propuesto por Javier.

Enunciado
Resolver de forma automática un sokoban. Sugiero tomar como base la solución escrita para el problema "Kata TDD. Sokoban (el juego) en Haskell" propuesto por Javier.
Preguntas sobre el desafío
  • JoseJuan, gracias por la propuesta. En mi opinión es muy interesante, pero no es nada fácil, al menos no en otros lenguajes como Java. No se si en Haskell se plantea ese dilema, pero ¿como consigues que no entre en un bucle infinito por repetir siempre la misma secuencia de movimientos? Pisar una casilla solo una vez no me parece una opción viable. Un saludo.

    "¿como consigues que no entre en un bucle infinito..."

    Eso forma parte del problema XD, existen varias formas, pero la más habitual es backtraking.

  • Perdona si no me he explicado bien. Si haces backtracking no permites que se pise una casilla que ya se haya pisado, con lo que creo que puedes no encontrar una solución que exista (de hecho puedes quedarte encerrado si solo puedes moverte por un camino que ya has andado). Pero si permites que una casilla se pise más de una vez, entonces puedes entrar en bucles infinitos. No veo como el backtracking resuelve este problema concreto. Gracias y perdón por el tocho.

    "Si haces backtracking no permites que se pise una casilla que ya se haya pisado..."

    ¿Porqué no lo permites?, no hay problema en pisar una celda que ya has pisado, al menos (pista), en ciertos casos...

Plantea tu pregunta

1 Solución

0votos
Resolver Sokoban en Haskell
por

josejuan

hace 6 años

El problema es NP-hard, por tanto hay que usar heurísticas para obtener rendimientos aceptables. Haciendo uso de la implementación del problema original y aplicando backtracking directo, la solución en Haskell que pongo no es eficiente (hace falta heurística).

Dar mi solución