Löse Sudoku mit Algorithmus X.

In diesem Artikel betrachten wir Knuths „Algorithmus X“ und seine Anwendung zur Lösung von Sudoku. Das Schöne am Algorithmus ist, dass Sudoku schnell gelöst werden kann, ohne dass fortschrittliche Lösungstechniken programmiert werden müssen.

Alles begann mit den Aufgaben von Project Euler , bei denen Sie 50 Sudoku lösen müssen, um eine Antwort zu erhalten. Und es scheint, dass er eine Antwort darauf erhalten hat, indem er ein Programm zum Lösen einer ziemlich dummen Suche geschrieben hat, aber irgendwie gab es eine gewisse Unzufriedenheit mit der Geschwindigkeit der Lösung. Nachdem ich gesehen hatte, wie normale Menschen Sudoku lösen, stellte ich fest, dass der von Donald Knut erfundene Algorithmus X dafür verwendet wird.

Algorithmus X.

Dieser Algorithmus löst das Problem der genauen Abdeckung des Satzes. Wenn Sie möchten, wird auch ein "diskretes Puzzle" mit Informationen zur Form der verfügbaren Teile gesammelt. Formaler:

• Es gibt viele s
• Es gibt eine Menge von Teilmengen Y dieser Menge
• Die Aufgabe besteht darin, aus Y solche Elemente Y * auszuwählen, dass jedes Element aus S nur in einer der in Y * enthaltenen Mengen enthalten ist.
• Das heißt, die Vereinigung aller Mengen in Y * bildet (deckt) die Menge S ab , und gleichzeitig gibt es in Y * keine paarweise sich überschneidenden Mengen

Betrachten Sie zum Beispiel die Mengen
S = {1, 2, 3, 4, 5} und
Y = { A = {1, 2},
B = {2, 3},
C = {1, 5},
D = {1, 4},
E = {5}}
Die Mengen B , D und E bilden eine genaue Abdeckung der Menge S.

Für den X-Knuth-Algorithmus wird die Menge Y als eine binäre Matrix dargestellt, wobei die Zeilen den Elementen Y entsprechen und A _{i, j} = 1, wenn S _j in Y _{i ist} . Das heißt, für das obige Beispiel:

Der genaue Suchalgorithmus für die Abdeckung lautet wie folgt:

• Eingabedaten: setzt S und Y ; Stack Sets, die möglicherweise in der Abdeckung enthalten sind (möglicherweise anfangs leer oder bereits einige Elemente enthalten)
  
  1. Wenn der Satz S leer ist, befindet sich die gewünschte Abdeckung auf dem Stapel.
  2. Wenn die Menge Y leer ist, wurde die Abdeckung nicht gefunden.
  3. Wir suchen nach einem Element s in der Menge S , das in der Mindestanzahl von Mengen in Y enthalten ist.
  4. Wählen Sie aus Y alle Zeilen X mit s .
  5. Wiederholen Sie für jeden Satz X 6-9.
  6. Fügen Sie dem Stapel X als potenzielles Abdeckungselement hinzu.
  7. Wir bilden die Mengen S ' und Y' : S ' ist S , aus dem alle in X enthaltenen Elemente entfernt werden, Y' sind die Mengen aus Y , die sich nicht mit X schneiden.
  8. Wir nennen Algorithmus X für S ' , Y' und Stack .
  9. Wenn in Schritt 7 festgestellt wurde, dass keine Abdeckung möglich ist, entfernen Sie das Element von der Oberseite des Stack und fahren Sie mit dem nächsten X fort. Wenn eine Lösung gefunden wird, geben wir sie zurück.
  10. Wenn es für kein X eine Lösung gibt, wird die Aufgabe für diese Eingabe nicht gelöst.

Im Allgemeinen nichts besonders kompliziert. Im Wesentlichen - die übliche Suche in der Tiefe. Übrigens, wenn Sie den Stapel anfänglich als nicht leer festlegen, kann das Problem wie folgt formuliert werden: "Finden Sie die genaue Abdeckung, die Elemente enthält, die bereits auf dem Stapel liegen."

Die Subtilität besteht darin, dass dieser Algorithmus in der Praxis für Probleme verwendet wird, bei denen die Mengen in Y "klein" sind, d. H. Die Matrix ist sehr spärlich, weshalb beispielsweise die Suche nach Schnittpunkten zwischen Spalten während der Standardspeicherung in Form einer Matrix unannehmbar lange dauert.
Daher ergänzt Knut diesen Algorithmus mit einem "Dance Link" -Mechanismus . Die Matrix wird in Form einer zweidimensionalen doppelt verknüpften Liste dargestellt: Für jede Zeile in der Liste werden nur die Spaltennummern gespeichert, wobei diese Zeile Einheiten enthält. Die Liste enthält auch Links zum nächsten und vorherigen Element in einer Zeile und Spalte. Mit einer solchen Organisation können Sie Spalten und Zeilen während der O (1) -Zeit aus einer spärlichen Matrix entfernen, verglichen mit O ( m * n ), wenn sie in einem zweidimensionalen Array gespeichert sind.

Es ist interessant, dass Ali Assaf eine Alternative zum Mechanismus des Tanzens von Links mithilfe von assoziativen Listen bietet, mit der Sie den X-Algorithmus in buchstäblich mehreren Dutzend Zeilen in Hochsprachen implementieren können.

Die Idee ist, sowohl Spalten als auch Matrixzeilen in assoziativen Listen zu speichern. In Spalten speichern wir Zeilenindizes an dem Schnittpunkt, an dem sich Elemente ungleich Null befinden, in Zeilen bzw. Spaltenindizes. Darüber hinaus werden wir Indizes in Zeilen in geordneter Weise in einem Array speichern. Wir stellen fest, dass es in Knuths Algorithmus im Wesentlichen nicht erforderlich ist, Zeilen zu ändern, weshalb eine Optimierung zum schnellen Entfernen eines Elements aus einer Zeile nicht erforderlich ist. Aber die Spalten werden in Form von Mengen gesetzt, weil Wenn Sie eine Zeile aus einer Matrix löschen, müssen Sie ihren Bezeichner aus allen Spalten entfernen (und wenn Sie sie aus allen Spalten löschen, verschwindet die Zeile "von selbst").

Betrachten Sie die Implementierung des Algorithmus auf Julia.
Die Matrix aus dem Beispiel sieht nun folgendermaßen aus:

 Y = Dict( 'A' => [1, 2], 'B' => [2, 3], 'C' => [1, 5], 'D' => [1, 4], 'E' => [5] ) S = Dict( 1 => Set(['A', 'C', 'D']), 2 => Set(['A', 'B']), 3 => Set(['B']), 4 => Set(['D']), 5 => Set(['C', 'E']) ) 

Damit der Algorithmus funktioniert, benötigen Sie eine Funktion, die Linien aus der Matrix herausnimmt, die sich mit der angegebenen überschneiden, und eine Funktion, die diese Linien an ihren Platz zurückbringt.

 function extract_intersects!(rows, columns, base_row) buf = [] for elt in rows[base_row] #        push!(buf, pop!(columns, elt)) #         for intersecting_row in buf[end] for other_elt in rows[intersecting_row] if other_elt != elt delete!(columns[other_elt], intersecting_row) end end end end return buf end function restore_intersects!(rows, columns, base_row, buf) #       base_row  ,      for elt in Iterators.reverse(rows[base_row]) columns[elt] = pop!(buf) for added_row in columns[elt] for col in rows[added_row] push!(columns[col], added_row) end end end end 

Damit diese beiden Funktionen ordnungsgemäß funktionieren, war eine geordnete Speicherung der Elemente in den Zeilen der Matrix erforderlich. In der Funktion extract_intersects!() bei jeder Iteration der äußeren Schleife die Zeilen aus der Matrix entfernt, die sich mit base_row schneiden, aber keine Elemente enthalten, die in früheren Iterationen angezeigt wurden. Dies stellt sicher, dass beim Einfügen der Spalten in restore_intersects!() In umgekehrter Reihenfolge in der innersten Schleife zum Zeitpunkt des Aufrufs push!(columns[col], added_row) die columns[col] column columns[col] bereits in die Matrix zurückgegeben und alle gelöscht werden extract_intersects!() Elemente aus den Spalten werden an ihren ursprünglichen Platz zurückgesetzt.

Nun Algorithmus X selbst:

 function algorithm_x(rows, columns, cover = []) if isempty(columns) return cover else #       m, c = findmin(Dict(k => length(v) for (k, v) in columns)) for subset in collect(columns[c]) push!(cover, subset) #     #   subset  buf_cols = extract_intersects!(rows, columns, subset) s = algorithm_x(rows, columns, cover) #     - ,  s == nothing || return s restore_intersects!(rows, columns, subset, buf_cols) pop!(cover) end #      columns[c] , #        return nothing end end 

Sudoku

Es gibt einen Algorithmus, die Sache ist klein - Sudoku als eine Aufgabe zu präsentieren, um die genaue Abdeckung zu finden.

Wir formulieren die Anforderungen, die ein gelöstes Sudoku erfüllen muss:

1. In jeder Zelle gibt es eine Zahl von 1 bis 9 (oder bis zu n ^2, wenn Quadrate unterschiedlicher Größe gelöst werden).
2. In jeder Zeile kommt jede Nummer einmal vor.
3. In jeder Spalte kommt jede Zahl einmal vor.
4. In jedem Quadranten kommt jede Zahl einmal vor.

Jede dieser Anforderungen muss genau einmal erfüllt werden, d. H. Sie bilden das Set, das abgedeckt werden muss. Es hat genau 4 n ² Elemente (Spalten in der Matrix).

Die Teilmengen, die wir betrachten, werden durch Ersetzen einer bestimmten Zahl in einer bestimmten Zelle gebildet. Zum Beispiel "deckt" die Zahl 9 am Schnittpunkt von 1 Zeile und 4 Spalten "eine Teilmenge" in der Zelle (1,4) ab, es gibt eine Zahl, in 1 Zeile gibt es eine Zahl 9, in 4 Spalten gibt es eine Zahl 9, in 2 Quadranten gibt es eine Zahl 9 "(was das Übliche impliziert) Sudoku 9 × 9).

Danach wird der Lösungsalgorithmus trivial geschrieben.

 #    9×9,      #   -   (row, col, num) #  : # (0, row, col) -   row  col   # (1, row, num) -   row   num # (2, col, num) -   col   num # (3, q, num) -   q   num function xsudoku(puzzle::AbstractMatrix{Int}) rows = Dict() cols = Dict() #   for row in 1:9, col in 1:9, num in 1:9 r = [] quad = ((row-1)÷3)*3 + (col-1)÷3 + 1 push!(r, (0, row, col), (1, row, num), (2, col, num), (3, quad, num)) rows[(row, col, num)] = r end #   for type in 0:3, n1 in 1:9, n2 in 1:9 cols[(type, n1, n2)] = Set() end for (rk, rv) in rows for v in rv push!(cols[v], rk) end end # s -    #  ,     ,    s = [] for i in 1:9, j in 1:9 if puzzle[i, j] > 0 elt = (i, j, puzzle[i,j]) push!(s, elt) #    ,       extract_intersects!(rows, cols, elt) end end # ,   -   success = algorithm_x(rows, cols, s) success != nothing || return nothing #      ret = similar(puzzle) for (i, j, num) in s ret[i,j] = num end return ret end 

Schauen wir uns ein Beispiel an:

  julia> @time xsudoku([0 0 0 0 0 0 4 0 0; 3 0 6 0 0 0 0 0 0; 0 0 0 1 9 6 0 3 0; 0 7 0 0 0 0 0 1 0; 8 0 0 2 5 0 0 9 0; 0 4 0 0 0 0 8 0 0; 0 6 0 4 0 9 0 0 8; 0 0 5 0 0 0 0 2 0; 0 0 0 5 0 0 0 0 7]) 0.006326 seconds (54.91 k allocations: 3.321 MiB) 9×9 Array{Int64,2}: 1 5 7 8 3 2 4 6 9 3 9 6 7 4 5 2 8 1 2 8 4 1 9 6 7 3 5 6 7 2 9 8 4 5 1 3 8 3 1 2 5 7 6 9 4 5 4 9 6 1 3 8 7 2 7 6 3 4 2 9 1 5 8 4 1 5 3 7 8 9 2 6 9 2 8 5 6 1 3 4 7 

Es scheint zu funktionieren und die Geschwindigkeit ist akzeptabel.

Es sollte beachtet werden, dass keine Techniken speziell für Sudoku (wie hier oder hier ) in den Algorithmus gelegt wurden, außer einer spezifischen Darstellung des gewünschten Satzes und der Abdeckungselemente.