Java-Programmieraufgaben - BacktrackingSchwierigkeit 1
Sudoku ist ein mathematisches Zahlenrätsel das auf einem 9 x 9 Felder grossem "Spielbrett" basiert. Dieses Spielbrett ist in weitere neun 3 x 3 grosse Quadrate unterteilt. Ziel ist es mit rekursivem Backtracking ein teilweise mit Zahlen ausgefülltes Spielbrett so zu vervollständigen, dass in jeder Zeile, in jeder Spalte und in jedem der 3 x 3 grossen Quadrate die Zahlen von 1 bis 9 jeweils genau einmal auftreten. Mit Backtracking kann man systematisch alle Kombinationen von Zahlen ausprobieren.
Um möglichst schnell entscheiden zu können, ob eine Zahl in einer Zeile, Spalte oder 3x3 Quadrat gesetzt wird, sollten Sie sich überlegen, wie mit einer geeigneten Datenstruktur für eine Zeile z und Spalte s und eine zu setzende Zahl x sehr schnell entschieden werden kann, ob in der Zeile z, Spalte s oder zugehörigem 3x3 Quadrat schon die selbe Zahl vorhanden ist. Die Datenstruktur ähnelt derjenigen, die der Backtracking-Lösung des Acht-Damen-Problems zum Einsatz kommt.
Schwierigkeit 2
Um diese Aufgabe geeignet zu bewältigen, sollten Sie vorher einen Java-Backtracking-Algorithmus zum Lösen von Sudokus implementiert haben.
Neue Sudokus lassen sich durch Vorgabe von n zufälligen Zahlen erstellen:
Es wird immer eine neue zufällige Zahl auf ein zufälliges Feld gesetzt (falls die Regeln es erlauben) bis n Zahlen
erfolgreich platziert sind.
Wenn der Backtracking-Lösungsalgorithmus das so erstellte Sudoku lösen kann, ist man fertig. Wenn nicht, dann wiederholt man die ganze Prozedur.
Dieses Zufallsverfahren kann mit einer gewissen Wahrscheinlichkeit pro Durchlauf ein falsches Ergebnis erzeugen. Man nennt derartige Algorithmen Monte-Carlo-Algorithmen. Sie können theoretisch (mit sehr geringer Wahrscheinlichkeit) unendlich lang laufen, ohne zu terminieren.
Sie können die Methode zum Erzeugen einer Sudoku-Lösung als Objektmethode zur vorhandenen Java-Klasse für den Backtracking-Algorithmus implementieren. Sie können dann bestehende Methoden, die die Gültigkeit eines Zuges überprüfen leicht wiederverwenden.
(Nur für einsame Programmierer)
Schwierigkeit 1
Solitär ist ein in mehreren Varianten vorkommendes Geduldsspiel. Wir betrachten die sogenannte Englische Variante. Das Spielfeld hat die Form eines Kreuzes und besteht aus 32 Spielfeldern. Von diesen sind 31 Spielfelder zu Beginn belegt (unten mit X markiert). Das Feld in der Mitte ist zu Anfangs frei (unten mit O markiert).
Die Regeln für das Spiel sind recht einfach: Ein gültiger Spielzug ist ein horizontaler oder vertikaler "Sprung" eines Spielsteins über einen anderen Spielstein in ein leeres Feld. Der übersprunge Stein wird weggenommen. Das Spiel ist erfolgreich gelöst, wenn sich am Ende der letzte Stein in der Mitte des Spielfeldes befindet. Am Anfang gibt es noch wenige Zugmöglichkeiten, in der Mitte des Spiels sehr viele und am Ende wieder weniger. Im folgenden ist links die Startsitutation, dann drei mögliche Spielzüge und die geforderte Endsituation gegeben.
|
--> |
|
--> |
|
--> |
|
weitere Züge ... --> |
|
Implementieren Sie einen Backtracking-Algorithmus in Java, welcher eine Lösung für dieses Spiel findet. Die Lösung kann als Folge der aus den Spielzügen resultierenden Spielfeldern gespeichert werden. Am besten implementiert man dazu eine eigene Java-Klasse für das Spielfeld. Das Spielfeld selbst kann mit einem 7x7 Feld repräsentiert werden. Mit Backtracking müssen alle Kombinationen möglicher Sprünge berechnet werden.
Auf einen 2,2 Ghz Athlon 64 wurde eine Lösung nach etwa 200 ms gefunden. Dazu waren keine Heuristiken oder Optimierungen nötig: eine Lösung läßt sich mit Backtracking durch systematisches Ausprobieren aller mögliche Sprünge finden.