In meiner Freizeit löse ich gerne Sudoku-Rätsel und daher stammt die Idee ein Programm zu entwickeln, das diese Zahlenrätsel ausfüllen kann. Nach dem c’t Programmierwettbewerb hatte ich damit wieder eine neue Aufgabe gefunden, für die ich eine Lösung implementieren konnte.
Dieses Mal habe ich in Java programmiert und zunächst mit einem Konsolenprogramm begonnen, in dem ich die Regeln zum Ausfüllen eines Sudoku implementiert habe. Anschließend habe ich eine grafische Oberfläche zur Visualisierung des Sudoku geschrieben und später so erweitert, dass der Nutzer direkt Ziffern eingeben kann.
Leichte Sudokus lassen sich durch Anwendung des Ausschlussverfahrens lösen. Man findet Ziffern, die nur an einer Stelle innerhalb eines Blocks auftreten können. Durch die schrittweise Vervollständigung des Sudoku kann man weitere Schlussfolgerungen treffen, bis man das Rätsel gelöst hat. Dieses Ausschlussverfahren verwendet sog. analytisch-systematische Basismethoden. Bei schweren Sodukus findet man durch Anwendung dieses Verfahrens keine eindeutige Lösung, so dass man das Feld durch Ausprobieren vervollständigen muss.
Mit Papier und Stift kann ich schwere Sudokus nicht lösen, da mir das Ausprobieren zu aufwändig ist. Auch mein Sudoku-Programm konnte keine schweren Rätsel lösen, da es nur analytisch-systematische Methoden angewandt hat.
Zur Lösung von schweren Sudokus kann man rekursive Verfahren verwenden, die mit Hilfe von Backtracking alle möglichen Zahlenkombinationen systematisch durchgehen, bis sie eine Lösung gefunden haben. Im Netz habe ich eine Beschreibung eines solchen Verfahrens entdeckt und in mein Programm eingebaut, so dass jetzt alle Arten von Sudokus gelöst werden können.