Stelle das rekursive Ablaufschema der Funktion is_solvable für BOARD_SIZE = 4 verkürzt dar, wie im Kapitel Rekursion beschrieben. Die verkürzte Darstellung sollte nur den Ablauf bis zur ersten Abbruchsituation und den Pfad bis zur Ausgabe der Lösung enthalten.
Wandeln Sie das Programm zur Lösung des Damenproblems so ab,
dass es nicht nach der ersten Lösung abbricht,
sondern die Anzahl aller Lösungen als Ergebnis zurückliefert.
Implementieren Sie dazu analog zu is_solvable
eine leicht abgewandelte Funktion solution_count,
die diese Anzahl zurück liefert.
Wie viele Lösungen hat das Damenproblem für acht Damen?
Bis zu wievielen Damen können Sie die Anzahl aller Lösungen des Damenproblems in annehmbarer Zeit berechnen?
Schreiben Sie ein Python-Programm, das Backtracking verwendet, um nach einer Lösung für ein Sudoku-Puzzle zu suchen. Testen Sie es zum Beispiel mit der folgenden Vorbelegung, bei der freie Felder als 0 dargestellt sind:
PUZZLE = [
[0, 0, 0, 0, 7, 3, 0, 1, 2],
[0, 1, 0, 2, 0, 6, 4, 0, 0],
[0, 0, 2, 0, 0, 0, 5, 0, 8],
[0, 0, 3, 0, 0, 4, 0, 0, 0],
[4, 9, 8, 0, 0, 1, 0, 0, 0],
[0, 0, 6, 0, 0, 5, 0, 0, 0],
[0, 0, 4, 0, 0, 0, 6, 0, 1],
[0, 6, 0, 3, 0, 7, 2, 0, 0],
[0, 0, 0, 0, 6, 8, 0, 4, 5],
]
Zur Implementierung der Gültigkeitsbedingung ist die vordefinierte Funktion set hilfreich, die (nicht mutierend) Duplikate aus einem Array entfernt. Zum Beispiel ist len(entries) == len(set(entries)) genau dann True, wenn alle Elemente von entries verschieden sind.