Rückzieher in Erlang

Question

Zunächst einmal sorry für mein Englisch.

Ich möchte ein Backtracking-Algorithmus in Erlang verwenden. Es würde als ein teilweise gefüllten Sudokus zu lösen erraten. Ein 9x9 Sudoku ist als eine Liste von 81 Elementen gespeichert, wobei jedes Element der mögliche Anzahl speichert, die in diese Zelle gehen.

Für eine 4x4 Sudoku meine erste Lösung sieht wie folgt aus: [[1], [3], [2], [4], [4], [2], [3], [1], [2,3], [4], [1], [2, 3], [2,3], [1], [4], [2,3]]

Dieses Sudoku hat 2 Lösungen. Ich habe für beide von ihnen zu schreiben. Danach Ausgangslösung erreicht, ich brauche einen Backtracking-Algorithmus zu implementieren, aber ich weiß nicht, wie es zu machen.

Mein Gedanke ist, die festen Elemente in eine neue Liste fixedlist genannt zu schreiben, die die Multiple-Lösung Zellen [] ändern werden.

Für die oben genannten Beispiel sieht die fixedlist wie folgt aus: [[1], [3], [2], [4], [4], [2], [3], [1], [], [4], [1], [], [], [1], [4], []]

Von hier aus habe ich eine „Probe“, ich sehe für die niedrigste Länge in dem solutionlist, die nicht gleich 1 ist, und ich versuche, die erste mögliche Anzahl dieser Zelle und ich habe es zu diesem fixedlist. Hier habe ich einen Algorithmus, um die Zellen und Kontrollen zu aktualisieren, wenn es noch ein lösbares Sudoku ist oder nicht. Wenn nicht, weiß ich nicht, wie man einen Schritt zurück und versucht, einen neuen. Ich kenne den Pseudo-Code davon und ich kann es für imperative Sprachen verwenden, aber nicht für erlang. (Prolog tatsächlich umgesetzt Zurückverfolgungs-Algorithmus, aber erlang nicht)

Jede Idee?

Answer 1

Re:. Meine bactracking Funktionen

Dies sind die allgemeinen Funktionen, die für den Umgang mit Rückverfolgung und logische Variablen einen Rahmen ähnlich einem Prolog-Motor. Sie müssen die Funktion (Prädikate) bereitzustellen, die die Programmlogik zu beschreiben. Wenn Sie sie schreiben, wie Sie in Prolog würde ich können Sie zeigen, wie sie in erlang zu übersetzen. Ganz kurz übersetzen Sie so etwas wie:

p :- q, r, s.

in Prolog in so etwas wie

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

Hier bin ich zu ignorieren alle weitere Argumente mit Ausnahme der Fortsetzungen.

Ich hoffe, das etwas Hilfe gibt. Wie gesagt, wenn Sie Ihre Algorithmen beschreiben kann ich ihnen helfen, zu übersetzen, ich habe für ein gutes Beispiel gesucht. Sie können natürlich genauso gut tun, es selbst aber bietet etwas Hilfe.

Answer 2

Sehen Sie sich diese Artikel in Robert Virding Blog:

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