Backtracking in Erlang

Question

Vor allem Entschuldigung für mein Englisch.

Ich möchte einen Backtracking-Algorithmus in Erlang verwenden. Es würde als ein Rätsel dienen, um teilweise gefüllte Sudokus zu lösen. Ein 9x9-Sudoku wird als eine Liste von 81 Elementen gespeichert, wobei jedes Element die mögliche Anzahl speichert, die in diese Zelle gehen kann.

Für ein 4x4 Sudoku sieht meine ursprüngliche Lösung so 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 muss beide aufschreiben. Nachdem diese anfängliche Lösung erreicht ist, muss ich einen Backtracking-Algorithmus implementieren, aber ich weiß nicht, wie ich es machen soll.

Mein Gedanke ist, die festen Elemente in eine neue Liste namens "fixedlist" zu schreiben, die die Zellen für mehrere Lösungen in [] ändert.

Für das oben genannte Beispiel sieht die feste Liste folgendermaßen aus: [[1], [3], [2], [4], [4], [2], [3], [1], [ ], [4], [1], [], [], [1], [4], []]

Von hier habe ich eine "Probe", ich suche die niedrigste Länge in der Lösungsliste welche ist nicht gleich 1, und ich versuche die erste mögliche Anzahl dieser Zelle und ich lege es auf diese feste Liste. Hier habe ich einen Algorithmus, um die Zellen zu aktualisieren und zu prüfen, ob es immer noch ein lösbares Sudoku ist oder nicht. Wenn nicht, weiß ich nicht, wie ich einen Schritt zurücktreten und einen neuen versuchen soll. Ich kenne den Pseudo-Code davon und ich kann es für Imperativ-Sprachen verwenden, aber nicht für Erlang. (Prolog tatsächlich Backtrack-Algorithmus implementiert, aber erlang nicht)

Irgendeine Idee?

Answer 1

Re: Meine bactracking Funktionen.

Dies sind die allgemeinen Funktionen, die einen Rahmen für die Behandlung von Rückverfolgungs-und logischen Variablen ähnlich einer Prolog-Engine bieten. Sie müssen die Funktion (Prädikate) angeben, die die Programmlogik beschreibt. Wenn du sie so schreibst wie in Prolog, kann ich dir zeigen, wie man sie in Erlang übersetzt. 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). 

Here I alle anderen Argumente mit Ausnahme der Fortsetzungen bin ignorieren.

Ich hoffe, das gibt Hilfe. Wie gesagt, wenn Sie Ihre Algorithmen beschreiben, kann ich Ihnen helfen, sie zu übersetzen, ich habe nach einem guten Beispiel gesucht. Sie können das natürlich auch selbst machen, aber das hilft Ihnen.

Answer 2

Schauen Sie sich diese Artikel in Robert Virding Blog aus:

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