El dar marcha atrás en Erlang

Question

En primer lugar lo siento por mi Inglés.

Me gustaría utilizar un algoritmo de retroceso en Erlang. Que serviría como adivinanzas para resolver sudokus parcialmente llenos. Un sudoku 9x9 se almacena como una lista de 81 elementos, donde cada elemento almacena el número posible que puede entrar en esa celda.

En un sudoku 4x4 mi solución inicial tiene el siguiente aspecto: [[1], [3], [2], [4], [4], [2], [3], [1], [2,3], [4], [1], [2, 3], [2,3], [1], [4], [2,3]]

Esta sudoku tiene 2 soluciones. Tengo que escribir a cabo tanto de ellos. Después de llegar a esa solución inicial, que necesito para implementar un algoritmo de retroceso, pero no sé cómo hacerlo.

Mi idea es escribir los elementos fijos en una nueva lista llamada fixedlist que cambiarán las células en soluciones múltiples a [].

En el ejemplo mencionado anteriormente, el fixedlist se parece a esto: [[1], [3], [2], [4], [4], [2], [3], [1], [], [4], [1], [], [], [1], [4], []]

A partir de aquí tengo una "muestra", busco la longitud más bajo en el solutionlist que no es igual a 1, y trato el primer número posible de esta célula y lo puse a la fixedlist. Aquí tengo un algoritmo para actualizar las células y comprueba si todavía es un sudoku soluble o no. Si no es así, no sé cómo dar un paso atrás y tratar uno por uno nuevo. Sé que el pseudo código de él y lo puedo usar para lenguajes imperativos, pero no para Erlang. (Prólogo de hecho implementó el algoritmo de retroceso, pero no lo hizo Erlang)

¿Alguna idea?

Answer 1

Re:. Mis funciones bactracking

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

p :- q, r, s.

en el prólogo en algo así como

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

Aquí estoy ignorando todos otros argumentos, excepto las continuaciones.

Espero que esto da un poco de ayuda. Como ya he dicho, si usted describe sus algoritmos que puedo ayudarle a traducir, he estado buscando un buen ejemplo. Puede, por supuesto, al igual que también lo haga por sí mismo, pero esto proporciona un poco de ayuda.

Answer 2

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

http: //rvirding.blogspot .com / 2009/03 / retroceso-en-Erlang-parte-1-control.html http://rvirding.blogspot.com/ 2009/04 / retroceso-en-Erlang-parte-2-passing.html