Retrocesso em Erlang

Question

Antes de tudo desculpe pelo meu Inglês.

Eu gostaria de usar um algoritmo de retrocesso em Erlang. Ele serviria como um adivinhando para resolver sudokus parcialmente preenchido. Um sudoku 9x9 é armazenado como uma lista de 81 elementos, onde cada elemento armazena o possível número que pode ir para essa célula.

Para um 4x4 sudoku minha aparência de solução inicial como esta: [[1], [3], [2], [4], [4], [2], [3], [1], [2,3], [4], [1], [2, 3], [2,3], [1], [4], [2,3]]

Este sudoku tem 2 soluções. Eu tenho que escrever para fora ambos. Depois que a solução inicial alcançado, Eu preciso implementar um algoritmo de retrocesso, mas eu não sei como fazê-lo.

Meu pensamento é escrever os elementos fixos em uma nova lista chamada fixedlist que irá alterar as células de várias soluções para [].

Para os acima exemplo mencionado os olhares fixedlist como este: [[1], [3], [2], [4], [4], [2], [3], [1], [], [4], [1], [], [], [1], [4], []]

A partir daqui eu tenho uma "amostra", eu olho para o menor comprimento no solutionlist que não é igual a 1, e eu tento o primeiro número possível desta célula e eu colocá-lo para que fixedlist. Aqui eu tenho um algoritmo para atualizar as células e verifica se ele ainda é um sudoku solucionável ou não. Se não, eu não sei como dar um passo atrás um e tente um novo. Eu sei o código pseudo dele e eu posso usá-lo para linguagens imperativas mas não para erlang. (Prólogo realmente implementado algoritmo de retorno, mas erlang não)

Qualquer idéia?

Answer 1

Re:. Minhas funções bactracking

Estas são as funções gerais que proporcionam um quadro para o tratamento back-rastreamento e variáveis ??lógicas semelhante a um motor de prólogo. Você deve fornecer as funções (predicados) que descrevem a lógica do programa. Se você escrevê-los como faria no prólogo eu posso mostrar-lhe como traduzi-los em erlang. Muito resumidamente você traduzir algo como:

p :- q, r, s.

no prólogo em algo como

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

Aqui eu estou ignorando todas outros argumentos, exceto as continuações.

Espero que este dá alguma ajuda. Como eu disse, se você descrever seus algoritmos que posso ajudá-lo a traduzi-los, eu fui à procura de um bom exemplo. Você pode, é claro, muito bem fazê-lo por si mesmo, mas isso proporciona alguma ajuda.

Answer 2

Confira estes artigos no blog de Robert Virding:

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