Retroceder en Erlang

Question

Antes que nada, lo siento por mi inglés.

Me gustaría utilizar un algoritmo de retroceso en Erlang. Serviría como una adivinanza para resolver el sudokus parcialmente lleno. Un sudoku de 9x9 se almacena como una lista de 81 elementos, donde cada elemento almacena el número posible que puede entrar en esa celda. Para una sudoku 4x4 mi solución inicial se ve así: [[1], [3], [2], [4], [4], [2], [3], [1], [4] 2,3], [4], [1], [2,3], [2,3], [1], [4], [2,3]]

Este sudoku tiene 2 soluciones. Tengo que escribirlos a los dos. Después de alcanzar esa solución inicial, necesito implementar un algoritmo de retroceso, pero no sé cómo hacerlo.

Mi idea es escribir los elementos fijos en una nueva lista llamada lista fija que cambiará las celdas de solución múltiple a []. Para el ejemplo mencionado anteriormente, la lista fija se ve así: [[1], [3], [2], [4], [4], [2], [3], [1], [ ], [4], [1], [], [], [1], [4], []]

Desde aquí tengo una "muestra", busco la menor longitud en la lista de soluciones que no es igual a 1, y pruebo el primer número posible de esta celda y lo pongo en esa lista fija. Aquí tengo un algoritmo para actualizar las celdas y verifica si todavía es un sudoku resoluble o no. Si no, no sé cómo retroceder uno y probar uno nuevo. Conozco el pseudo código y puedo usarlo para idiomas imperativos pero no para erlang. (prólogo realmente implementó el algoritmo de retroceso, pero erlang no)

¿Alguna idea?

Answer 1

Re: Mis funciones bactracking.

Estas son las funciones generales que proporcionan un marco para manejar el seguimiento posterior y las variables lógicas similares a un motor de prólogo. Debe proporcionar la función (predicados) que describe la lógica del programa. Si los escribe como lo haría en Prolog, puedo mostrarle cómo traducirlos a Erlang. Muy brevemente a traducir algo así como:

p :- q, r, s. 

en prólogo en algo así como

p(Next0) -> 
    Next1 = fun() -> s(Next0) end, 
    Next2 = fun() -> r(Next1) end, 
    q(Next2). 

Aquí estoy haciendo caso omiso de todos los demás argumentos excepto las continuaciones.

Espero que esto ayude. Como dije, si describes tus algoritmos puedo ayudarte a traducirlos, he estado buscando un buen ejemplo. Por supuesto, puede hacerlo usted mismo, pero esto proporciona cierta ayuda.

Answer 2

Salida estos artículos en el blog de Robert Virding:

http://rvirding.blogspot.com/2009/03/backtracking-in-erlang-part-1-control.html http://rvirding.blogspot.com/2009/04/backtracking-in-erlang-part-2-passing.html