Retour en arrière à Erlang

Question

Tout d'abord désolé pour mon anglais.

Je voudrais utiliser un algorithme de backtracking dans Erlang. Cela servirait de deviner pour résoudre des sudokus partiellement remplis. Un sudoku 9x9 est stocké comme une liste de 81 éléments, où chaque élément stocke le nombre possible qui peut aller dans cette cellule. Pour un sudoku 4x4, ma solution initiale ressemble à ceci: [[1], [3], [2], [4], [4], [2], [3], [1], [ 2,3], [4], [1], [2,3], [2,3], [1], [4], [2,3]]

Ce sudoku a 2 solutions. Je dois écrire les deux. Une fois cette solution initiale atteinte, je dois implémenter un algorithme de retour arrière, mais je ne sais pas comment le faire.

Ma pensée est d'écrire les éléments fixes dans une nouvelle liste appelée liste fixe qui va changer les cellules de solution multiple à []. Pour l'exemple ci-dessus, la liste fixe ressemble à ceci: [[1], [3], [2], [4], [4], [2], [3], [1], [ ], [4], [1], [], [1], [4], []]

D'ici j'ai un "échantillon", je cherche la plus petite longueur dans la liste de solutions qui n'est pas égal à 1, et j'essaye le premier nombre possible de cette cellule et je le mets à cette liste fixe. Ici j'ai un algorithme pour mettre à jour les cellules et vérifie si c'est encore un sudoku solvable ou non. Sinon, je ne sais pas comment revenir en arrière et en essayer un nouveau. Je connais le pseudo code de celui-ci et je peux l'utiliser pour les langages impératifs mais pas pour erlang. (prolog réellement implémenté backtrack algorithme, mais erlang n'a pas)

Une idée?

Answer 1

Re: Mes fonctions bactracking.

Ce sont les fonctions générales qui fournissent un cadre pour la gestion du back-tracking et des variables logiques similaires à un moteur prologue. Vous devez fournir la fonction (prédicats) décrivant la logique du programme. Si vous les écrivez comme vous le feriez en prologue, je peux vous montrer comment les traduire en erlang. Très brièvement vous traduisez quelque chose comme:

p :- q, r, s. 

en Prolog en quelque chose comme

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

Ici, je suis ignorant tous autres arguments, à l'exception des continuations.

J'espère que cela donne de l'aide. Comme je l'ai dit si vous décrivez vos algorithmes, je peux vous aider à les traduire, j'ai cherché un bon exemple. Vous pouvez, bien sûr, tout aussi bien le faire par vous-même, mais cela vous aide.

Answer 2

Découvrez ces articles sur le 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