Retour en arrière en Erlang

Question

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

Je voudrais utiliser un algorithme de retours en arrière dans Erlang. Il servirait à deviner pour résoudre les sudokus partiellement remplies. Un 9x9 est sudoku stockée sous la forme d'une liste de 81 éléments, où chaque élément stocke le nombre possible, ce qui peut aller dans cette cellule.

Pour un 4x4 ma solution initiale sudoku ressemble à ceci: [[1], [3], [2], [4], [4], [2], [3], [1], [2,3], [4], [1], [2, 3], [2,3], [1], [4], [2,3]]

a 2 solutions sudoku. Je dois écrire tous les deux. Après cette solution initiale a atteint, je dois mettre en œuvre un algorithme de retours en 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 fixedlist qui va changer les cellules multiples solutions à [].

Pour l'exemple ci-dessus mentionné le fixedlist ressemble à ceci: [[1], [3], [2], [4], [4], [2], [3], [1], [], [4], [1], [], [], [1], [4], []]

D'ici, j'ai un « échantillon », je cherche la longueur la plus faible dans le solutionlist qui ne soit pas égal à 1, et je tente le premier nombre possible de cette cellule et je l'ai mis à cette fixedlist. Ici, j'ai un algorithme pour mettre à jour les cellules et vérifie si elle est encore solvable ou non sudoku. Sinon, je ne sais pas comment un pas en arrière et essayer une nouvelle. Je sais que le code pseudo de celui-ci et je peux l'utiliser pour les langues impératives, mais pas pour Erlang. (Prolog effectivement mis en œuvre l'algorithme de BackTrack, mais Erlang n'a pas)

Toute idée?

Answer 1

Re:. Mes fonctions bactracking

Ce sont les fonctions générales qui fournissent un cadre pour le traitement des retours en arrière et variables logiques similaires à un moteur Prolog. Vous devez fournir la fonction (prédicats) qui décrivent la logique du programme. Si vous les écrivez comme vous le feriez dans Prolog je peux vous montrer comment les traduire en Erlang. Très brièvement vous traduisez quelque chose comme:

p :- q, r, s.

Prolog dans quelque chose comme

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

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

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

Answer 2

Consultez ces articles sur le blog de Robert Virding:

http: //rvirding.blogspot .com / 2009/03 / retours en arrière en Erlang-partie-1-control.html http://rvirding.blogspot.com/ 2009/04 / retours en arrière en Erlang-partie-2-passing.html