Doppelstunde 11: Sudoku – eine Anwendung von Sets [nur LF, optional]
Die letzte Doppelstunde der Einheit ist optional. Sie stellt eine interessante Anwendung von Sets dar, ist aber ggf. zu komplex. Daher kann das Projekt auch zur Differenzierung in anderen Stunden verwendet werden. Inhaltlich könnte das Projekt bereits nach Doppelstunde 3 (ADTs, darunter Set) eingefügt werden. Allerdings wird auch ein Backtracking-Ansatz verwendet, der erst nach Doppelstunde 9 sinnvoll wäre. Es wäre sinnvoll (aber nicht unbedingt nötig), wenn im Vorfeld bereits Lambda-Ausdrücke behandelt worden sind, da das Programm sich damit oft einfacher und eleganter implementieren lässt.
Das Ziel ist die Implementierung eines Sudoku-Lösungsprogramms. Mit dem Aufgabenblatt 13_sudoku.odt werden die Schülerinnen und Schüler durch die Implementation einer Lösungsstrategie geführt. Problematisch könnte es werden, wenn die Schülerinnen und Schüler nicht mit Sudoku-Rätseln vertraut sind. Daher wird der Algorithmus zur Bestimmung von Kandidatenmengen an einem Beispiel ausführlich erklärt und auf Mengenoperationen zurückgeführt. Ähnlich wie bei früheren Aufgabenblättern wird ausschließlich in einer Modellklasse (hier „SudokuGitter“) gearbeitet, die GUI-Klassen werden nicht angefasst.
Wenn die Strategie mit nackten und versteckten Einern nicht mehr weiterführt, muss eine Zahl geraten werden und überprüft werden, ob man damit zu einem Ende kommt. Der hier eigentlich nötige Rekursionsschritt wird über die GUI-Klasse SudokuFrame erledigt5 . Damit müssen die Schülerinnen und Schüler den Rekursionsschritt nicht selbst formulieren. Stattdessen kann man sehen, dass sich ein neues Fenster über das aktuelle legt und dort weitergearbeitet wird. Eventuell werden von dort aus noch weitere Backtracking-Schritte nötig sein usw.6 Erst wenn alle Möglichkeiten auf der untersten Stufe überprüft worden sind (und diese nicht zu einem gelösten Spiel führen), wird zurückgekehrt und es werden dort die anderen Möglichkeiten überprüft.
Falls einzelne Schülerinnen und Schüler der Meinung sind, dass komplexere Lösungsstrategien besser zum Ziel führen als Backtracking, können sie diese gerne als Erweiterung implementieren. „Nackte Zweier“ sind noch relativ leicht implementierbar, diese müssten nach dem Aufstellen der Kandidatenmengen gesucht werden, um die Kandidatenmengen ggf. zu reduzieren. Eine Überprüfung der schweren mitgelieferten Rätsel führte allerdings zum Ergebnis, dass diese nur in seltenen Fällen weiterhelfen. Andererseits führt das Überprüfen solcher komplexer Strategien zu einem zusätzlichen Rechenaufwand, der den Effizienzgewinn durch die Einsparung der Rekursionsschritte schnell zunichte macht.
5 Aufgrund der Funktionsweise der Java-Frames und der asynchronen Funktionsaufrufe muss die Rekursion in verschiedene Methoden der Klasse SudokuFrame ausgelagert werden.
6 Beim Testen war die maximale Rekursionstiefe, die vorkam, 6 Stufen.
Unterrichtsverlauf: Herunterladen [odt][187 KB]
Weiter zu Hintergrundinformationen