Sudoku Solver
Ein Sudoku-Feld ist ein 9 × 9-Raster, das in neun 3 × 3-Blöcke unterteilt ist. In einem gelösten Feld enthält jede Zeile, jede Spalte und jeder Block jede Ziffer von 1 bis 9 genau einmal.
Das Rätsel besteht aus 9 Zeichenketten, eine pro Zeile von oben nach unten; ein . steht für ein leeres Feld. Fülle alle leeren Felder aus und gib das gelöste Feld in derselben Form zurück. Das Feld hat genau eine Lösung.
Funktion
- boardstring-array
- die 9 Zeilen des Rätsels, ein Punkt in jeder leeren Zelle
- Gibt zurückstring-array
- die 9 Reihen des gelösten Spielfelds
Einschränkungen
boardenthält 9 Zeichenketten der Länge 9.- Jedes Zeichen ist
.oder eine der Ziffern1bis9. - Die vorgegebenen Ziffern wiederholen sich nie innerhalb einer Zeile, einer Spalte oder eines Blocks.
- Das Brett hat genau eine Lösung.
Beispiele
- Eingabe
- board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
- Ausgabe
- ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
- Erklärung
- Die oberste Zeile
9.7.....6enthält bereits 9, 7 und 6, daher nehmen ihre sechs leeren Zellen die Zahlen 1, 2, 3, 4, 5 und 8 auf. Die Spalten und Kästchen bestimmen, wo jede Zahl hingehört, und die Zeile wird zu957214386.
Weiterführende Frage
Bei Killer-Sudoku müssen die Zellen in Käfigen ebenfalls die vorgegebenen Summen ergeben. Wie würdest du diese Regel in die Suche einbauen und damit frühzeitig Äste abschneiden?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Behalte im Blick, welche Ziffern bereits in jeder Zeile, jeder Spalte und jedem 3 × 3-Feld vorkommen. Dann kannst du in O(1) feststellen, ob eine Ziffer in eine leere Zelle passt.
Fülle die leeren Zellen nacheinander aus. Probiere jede Ziffer aus, die in die Zelle passt, gehe zur nächsten Zelle weiter und mache die Ziffer rückgängig, wenn sich das restliche Spielfeld damit nicht vervollständigen lässt.
Die Reihenfolge der Zellen ist wichtig. Fülle als Nächstes die leere Zelle mit den wenigsten verbleibenden Ziffern aus: Eine Zelle mit einer Option erfordert keine Verzweigung, und eine Zelle ohne Optionen sagt dir sofort, dass du zurückgehen musst.
Lösung
Löse es mit Backtracking: Setze eine passende Ziffer ein, fahre fort und mache den Zug rückgängig, wenn sich das Brett nicht vervollständigen lässt. Die Reihenfolge der Zellen bestimmt die Geschwindigkeit. Bei einem schwierigen Brett kann die zeilenweise Reihenfolge Hunderte Millionen unvollständige Bretter durchlaufen; zuerst die Zelle mit den wenigsten Möglichkeiten zu füllen, dauert etwa hundert.
Backtracking in Leserichtung
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Fülle die leeren Zellen in Leserichtung jeweils mit der kleinsten passenden Ziffer. Wenn für eine Zelle keine Ziffer mehr übrig ist, gehe zur vorherigen Zelle zurück und probiere die nächste Ziffer. Jede Kombination, die die Regeln einhält, wird der Reihe nach ausprobiert, sodass die Suche die Lösung findet.
Drei Tabellen machen jeden Passungstest zu O(1): rowUsed[r][d], colUsed[c][d] und boxUsed[b][d], wobei die Box b = (r / 3) * 3 + c / 3 ist. Beim Eintragen einer Ziffer werden drei Einträge gesetzt, beim Entfernen werden sie gelöscht.
Die feste Reihenfolge ist die Schwachstelle: Die Suche kann eine ganze Zeile mit lokal passenden Ziffern füllen und erst viele Zellen später feststellen, dass dadurch kein Platz mehr bleibt. Ein Brett, dessen obere Zeilen fast keine Vorgaben enthalten und dessen Lösungen hohe Ziffern sind, führt sie durch über 300 Millionen Teilbretter.
Algorithmus
- Lies das Brett als Gitter ein, wobei 0 für ein leeres Feld steht, fülle
rowUsed,colUsedundboxUsedund liste die leeren Felder in Leserichtung auf. backtrack(k): Wennkder Anzahl der leeren Felder entspricht, gib true zurück.- Gehe für jede Ziffer
dvon 1 bis 9, die in der Zeile, Spalte und Box von Feldknoch nicht verwendet wird, folgendermaßen vor: Trage sie ein, markiere sie und gib true zurück, wennbacktrack(k+1)true zurückgibt; andernfalls entferne die Markierung. - Wenn keine Ziffer funktioniert, leere das Feld und gib false zurück. Rufe
backtrack(0)auf und wandle das Gitter wieder in Zeichenfolgen um.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# row_used[r][d] is True when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
row_used = [[False] * 10 for _ in range(9)]
col_used = [[False] * 10 for _ in range(9)]
box_used = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
else:
empties.append((r, c))
def backtrack(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
grid[r][c] = d
row_used[r][d] = col_used[c][d] = box_used[b][d] = True
if backtrack(k + 1):
return True
row_used[r][d] = col_used[c][d] = box_used[b][d] = False
grid[r][c] = 0
return False
backtrack(0)
return ["".join(str(d) for d in row) for row in grid]Fülle zuerst die leerste Zelle aus
Idee
Die Lösung hängt nicht von der Füllreihenfolge ab. Wähle daher die Reihenfolge, die den Suchraum klein hält: Fülle bei jedem Schritt die leere Zelle, für die die wenigsten Ziffern infrage kommen. Eine Zelle, für die nur eine Ziffer infrage kommt, ist erzwungen und fügt keinen Suchzweig hinzu. Gibt es keine mögliche Ziffer, wird die Zelle sofort ausgewählt, sodass ein ungültiges Sudoku sofort erkannt wird.
Um die möglichen Ziffern für 81 Zellen pro Schritt effizient zu zählen, speichere jede Zeile, Spalte und jeden Block als Bitmaske: Das Bit d von rows[r] ist gesetzt, wenn sich die Ziffer d in Zeile r befindet. Für eine Zelle kommen ~(rows[r] | cols[c] | boxes[b]) & 0x3FE infrage, wobei 0x3FE die Bits 1 bis 9 beibehält. Die Anzahl entspricht der Zahl der gesetzten Bits. Wenn du d einsetzt, setzt du das Bit d in drei Masken; ein exklusives Oder entfernt es wieder.
Algorithmus
- Erstelle aus den vorgegebenen Ziffern das Raster und die Masken
rows,colsundboxes. backtrack(): Durchsuche alle Zellen, berechne für jede leere Zelle die zulässigen Ziffern und behalte die erste Zelle mit der geringsten Anzahl. Wenn keine Zelle leer ist, gib true zurück.- Setze für jede zulässige Ziffer dieser Zelle die Ziffer ein, setze ihr Bit in den drei Masken und gib true zurück, wenn
backtrack()true zurückgibt; andernfalls lösche die Bits. - Wenn keine Ziffer funktioniert, leere die Zelle und gib false zurück. Rufe
backtrack()auf und wandle das Raster wieder in Zeichenketten um.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# Bit d of rows[r] is set when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
rows[r] |= 1 << d
cols[c] |= 1 << d
boxes[(r // 3) * 3 + c // 3] |= 1 << d
def backtrack():
# Pick the empty cell with the fewest digits left (the first one on a tie).
best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
# Bits 1 to 9 of 0x3FE are the nine digits.
allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
count = bin(allowed).count("1")
if count < best_count:
best_r, best_c, best_allowed, best_count = r, c, allowed, count
if best_r == -1:
return True # no empty cell is left: the board is solved
r, c = best_r, best_c
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
bit = 1 << d
if best_allowed & bit:
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
if backtrack():
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
grid[r][c] = 0
return False
backtrack()
return ["".join(str(d) for d in row) for row in grid]
Stolperfallen und Grenzfälle
- Vergisst du, eine Ziffer aus den Aufzeichnungen für Zeile, Spalte und Kästchen zu entfernen, wenn du sie zurücknimmst, halten spätere Zellen die Ziffer für bereits verwendet und die Suche findet keine Lösung.
r / 3 + c / 3für das Kästchen zu verwenden. Die Zellen(0, 4)und(4, 0)ergeben beide 1, sodass zwei Kästchen denselben Eintrag verwenden und das Brett nie ausgefüllt werden kann. Verwende(r / 3) * 3 + c / 3mit ganzzahliger Division.- Nicht bei der ersten Lösung anzuhalten. Durch die anschließenden Rückgängigmach-Schritte wird das Brett wieder geleert, bevor du es ausliest.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität eines Sudoku-Lösers mit Backtracking?
Im schlimmsten Fall exponentiell, O(9^m) für m leere Zellen, da jede Zelle in bis zu 9 Ziffern verzweigen kann. Bei echten Rätseln beschneiden die Regeln für Zeilen, Spalten und Blöcke die meisten Verzweigungen, und wenn zuerst die leerste Zelle ausgefüllt wird, werden die meisten der übrigen Verzweigungen vermieden.
Wie überprüfst du, ob ein Sudoku genau eine Lösung hat?
Führe dieselbe Backtracking-Suche aus, zähle aber die Lösungen und brich ab, sobald die Anzahl 2 erreicht. Eine Anzahl von 1 bedeutet, dass das Rätsel eindeutig ist, 0 bedeutet, dass es keine Lösung hat. Rätselgeneratoren führen diese Prüfung nach dem Entfernen jedes Hinweises aus.
Gibt es eine schnellere Methode, Sudoku zu lösen, als Backtracking?
Die meisten schnellen Löser verwenden weiterhin Backtracking, leiten aber vor jedem Versuch mehr her. Die Constraint-Propagation füllt jede Zelle mit genau einer möglichen Option und jede Ziffer, die nur in eine Zelle ihrer Zeile, Spalte oder ihres Blocks passt, und wiederholt den Vorgang anschließend. Sudoku lässt sich auch als exaktes Überdeckungsproblem formulieren und mit Knuths Algorithmus X lösen.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def solveSudoku(board):
# Schreibe hier den CodeTest #1
Argument
board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
Erwartete Ausgabe
["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]