Die Funktion solution_count gibt statt eines Wahrheitswertes die Anzahl der gültigen Lösungen zurück. Diese Anzahl erhalten wir, indem wir in der Schleife, die die Erweiterungen durchläuft, die Teilergebnisse der einzelnen Erweiterungen aufaddieren. Anders als das Programm aus der Vorlesung bricht die Schleife nicht bei der ersten gefundenen Lösung ab sondern durchläuft alle.
def solution_count(queens):
if not is_safe(queens):
return 0
if is_complete(queens):
return 1
exts = place_next(queens)
count = 0
for index in range(0, len(exts)):
count = count + solution_count(exts[index])
return count
Für größere Zahlen lohnt es sich, den in is_safe implementierten Test zu optimieren. Da wir Damen schrittweise hinzufügen, genügt es, nur für die zuletzt hinzugefügte Dame zu testen, ob sie eine der anderen bedroht:
# assumes that only the last queen may be unsafe
def is_safe(queens):
j = len(queens) - 1
# search all previous queens
for i in range(0, len(queens) - 1):
# queens in same column
if queens[i] == queens[j]:
return False
# row distance equals column distance: queens on same diagonal
if j - i == abs(queens[j] - queens[i]):
return False
# found no attack
return True
Eine weitere Interessante Optimierung ergibt sich aus der Reihenfolge, in der Erweiterungen gebildet werden. In der Praxis zeigt sich nämlich, dass die erste Lösung deutlich schneller gefunden wird, wenn die Erweiterungen in zufälliger Reihenfolge durchlaufen werden:
def place_next(queens):
extensions = [None] * BOARD_SIZE
for q in range(0, BOARD_SIZE):
extensions[q] = queens + [q]
shuffle(extensions)
return extensions
Die Prozedur shuffle vertauscht die Elemente eines Arrays in zufälliger Reihenfolge und kann mit der Anweisung from random import shuffle importiert werden.
Mit den gezeigten Änderung können wir eine Lösung für sehr große Schachbretter in akzeptabler Zeit berechnen.
Zum Beispiel wird eine Lösung für 100 Damen oft nach wenigen Sekunden angezeigt.
Die Suche nach allen Lösungen wird durch die Randomisierung nicht beschleunigt,
profitiert aber ebenfalls vom vereinfachten Gültigkeitstest is_safe.
Wir definieren zunächst eine Prozudur zur Ausgabe eines Sudoku-Puzzles.
def print_puzzle(puzzle):
for i in range(0, len(puzzle)):
line = ""
for j in range(0, len(puzzle[i])):
if puzzle[i][j] == 0:
line = line + " ."
else:
line = line + " " + str(puzzle[i][j])
print(line)
Um zu testen, ob ein Puzzle vollständig ausgefüllt wurde, suchen wir nach Nullen.
def is_complete(puzzle):
for i in range(0, len(puzzle)):
for j in range(0, len(puzzle[i])):
if puzzle[i][j] == 0:
return False
return True
Der Test der Gültigkeitsbedingung wendet eine Hilfsfunktion all_valid auf alle Zeilen, alle Spalten und alle Quadrate an.
def is_valid(puzzle):
if not all_valid(puzzle):
return False
if not all_valid(columns(puzzle)):
return False
if not all_valid(squares(puzzle)):
return False
return True
Die Hilfsfunktion all_valid erwartet ein geschachteltes Array von Zahlen und prüft, ob die enthaltenen Arrays Duplikate enthalten.
def all_valid(areas):
for i in range(0, len(areas)):
entries = non_zero_entries(areas[i])
# check for duplicates using the set function
if len(entries) != len(set(entries)):
return False
return True
Die hier verwendete Funktion non_zero_entries erwartet ein Array von Zahlen als Argument und liefert ein neues Array derjenigen Zahlen zurück, die ungleich Null sind.
def non_zero_entries(area):
result = []
for i in range(0, len(area)):
if area[i] != 0:
result.append(area[i])
return result
Spalten berechnen wir mit einer geschachtelten Zählschleife.
def columns(puzzle):
result = []
for j in range(0, len(puzzle[0])):
column = []
for i in range(0, len(puzzle)):
column.append(puzzle[i][j])
result.append(column)
return result
Die Berechnung der Quadrate ist etwas komplizierter, aber ebenfalls mit einer geschachtelten Zählschleife möglich.
def squares(puzzle):
result = []
row = 0
for i in range(0, 3):
col = 0
for j in range(0, 3):
result.append(
puzzle[row][col : col + 3]
+ puzzle[row + 1][col : col + 3]
+ puzzle[row + 2][col : col + 3]
)
col = col + 3
row = row + 3
return result
Um Erweiterungen einer Teillösung zu berechnen, suchen wir zunächst nach der Position eines freien Feldes und tragen dann neue Zahlen in Kopien der ursprünglichen Lösung ein. Wir erzeugen die Erweiterungen in zufälliger Reihenfolge.
def extensions(puzzle):
pos = zero_position(puzzle)
row = pos[0]
col = pos[1]
result = []
for number in range(1, 10):
extension = copy(puzzle)
extension[row][col] = number
result.append(extension)
shuffle(result)
return result
Die Position eines freien Feldes suchen wir wieder mit einer geschachtelten Zählschleife.
def zero_position(puzzle):
for i in range(0, len(puzzle)):
for j in range(0, len(puzzle[i])):
if puzzle[i][j] == 0:
return [i, j]
return None
Die folgende Funktion kopiert ein geschachteltes Array von Zahlen.
def copy(puzzle):
result = []
for i in range(0, len(puzzle)):
result.append(puzzle[i] + [])
return result
Schließlich implementieren wir den Backtracking-Algorithmus unter Verwendung der definierten Hilfsfunktionen.
def is_solvable(puzzle):
if not is_valid(puzzle):
return False
if is_complete(puzzle):
print_puzzle(puzzle)
return True
exts = extensions(puzzle)
for index in range(0, len(exts)):
if is_solvable(exts[index]):
return True
return False
Der Aufruf is_solvable(PUZZLE) liefert True zurück und erzeugt vorher die folgende Ausgabe.
6 4 5 8 7 3 9 1 2
8 1 9 2 5 6 4 3 7
7 3 2 4 1 9 5 6 8
2 5 3 7 8 4 1 9 6
4 9 8 6 2 1 7 5 3
1 7 6 9 3 5 8 2 4
3 8 4 5 9 2 6 7 1
5 6 1 3 4 7 2 8 9
9 2 7 1 6 8 3 4 5