C) Sudoku Solver
In diesem Kapitel lernen Sie einen Algorithmus kennen, der ein Standard 9×9 Sudoku-Feld lösen kann. Dabei wird eine Brute-Force-Methode zum Lösen des Problems verwendet.
Zu Beginn erhalten Sie den kompletten Quelltext. Dieser wird anschließend analysiert.
import java.util.ArrayList;
import java.util.Arrays;
public class SudoSolver {
/*
* Löst ein 9x9 Sudoku
*/
public boolean solve(int[][] field) {
if (!checkSudo(field)) {
finishSudo(field);
return false;
}
boolean solved = solve(field, 0, 0);
finishSudo(field);
return solved;
}
/*
* Testet, ob die Vorgabe Fehler enthält und verändert ein Sudoku so, dass
* später erkannt werden kann, welche Zahlen vorgegeben waren und welche
* vom Solver gesetzt wurden. Dazu werden alle bereits gefüllten Felder negiert.
*/
private boolean checkSudo(int[][] field) {
for (int i = 0; i < field.length; i++) {
for (int j = 0; j < field.length; j++) {
if (field[i][j] > 0) {
int temp = field[i][j];
field[i][j] = 0;
if (Arrays.binarySearch(getPossible(field, j, i), temp) < 0) {
field[i][j] = temp;
return false;
}
field[i][j] = temp * -1;
}
}
}
return true;
}
/*
* Rekursive Methode um ein Sudoku zu lösen
*/
private boolean solve(int[][] field, int y, int x) {
int[] poss = null;
int x2 = x + 1;
int y2 = y;
if (field[x][y] == 0) {
poss = getPossible(field, y, x);
if (poss.length == 0) {
return false;
}
field[x][y] = poss[0];
}
if (x2 >= field.length) {
x2 = 0;
y2++;
}
if (y2 >= field[x].length) {
return true;
}
while (!solve(field, y2, x2)) {
if (poss == null) {
return false;
}
else {
poss = remove(field[x][y], poss);
if (poss.length == 0) {
field[x][y] = 0;
return false;
}
field[x][y] = poss[0];
}
}
return true;
}
/*
* Entfernt eine Zahl aus einem int-Array
*/
private int[] remove(int number, int[] arr) {
int[] array = new int[arr.length - 1];
for (int i = 0, j = 0; i < arr.length; i++, j++) {
if (arr[i] != number) {
array[j] = arr[i];
}
else {
j--;
}
}
return array;
}
/*
* Gibt alle möglichen Zahlen für das übergebene Feld an der übergebenen
* Position zurück
*/
private int[] getPossible(int[][] field, int y, int x) {
ArrayList<Integer> poss = new ArrayList<Integer>();
int quadStartX = (int) (x / 3) * 3;
int quadStartY = (int) (y / 3) * 3;
for (int i = 1; i < 10; i++) {
poss.add(i);
}
for (int i = 0; i < field.length; i++) {
poss.remove(new Integer(Math.abs(field[x][i])));
poss.remove(new Integer(Math.abs(field[i][y])));
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
poss.remove(new Integer(Math.abs(field[i + quadStartX][j + quadStartY])));
}
}
int[] val = new int[poss.size()];
for (int i = 0; i < val.length; i++) {
val[i] = poss.get(i);
}
return val;
}
/*
* Macht die Änderungen von checkSudo wieder Rückgängig
*/
private void finishSudo(int[][] field) {
for (int i = 0; i < field.length; i++) {
for (int j = 0; j < field.length; j++) {
if (field[i][j] < 0) {
field[i][j] = field[i][j] * -1;
}
}
}
}
}
Die Klasse könnte z. B. so getestet werden:
int[][] sudo = {{1, 0, 0, 6, 0, 0, 0, 0, 0},
{0, 2, 0, 0, 0, 0, 9, 0, 0},
{0, 0, 3, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 4, 0, 0, 0, 1, 0},
{0, 4, 0, 0, 5, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 6, 0, 9, 0},
{0, 0, 2, 0, 0, 0, 7, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 8, 0},
{3, 0, 0, 5, 0, 0, 0, 0, 9}};
for (int i = 0; i < sudo.length; i++) {
for (int j = 0; j < sudo[i].length; j++) {
System.out.print(sudo[i][j] + " ");
}
System.out.println();
}
System.out.println("------------------------");
boolean bool = new SudoSolver().solve(sudo);
if (bool) {
for (int i = 0; i < sudo.length; i++) {
for (int j = 0; j < sudo[i].length; j++) {
System.out.print(sudo[i][j] + " ");
}
System.out.println();
}
}
else {
System.out.println("Ungültige Vorgabe");
}
Wie Sie sicherlich schon festgestellt haben, wird der Methode solve der Klasse SudokuSolver ein 2D-Array vom Typ int übergeben. Alle noch nicht ausgefüllten Felder erhalten den Wert „0“.
private int[] remove(int, int[])
Diese Methode entfernt eine Zahl aus einem int-Array. Sie wird benötigt, falls eine mögliche Zahl für ein Feld im Nachhinein wegfällt. Dabei wird ein neues Array, welches um den Faktor eins kleiner ist als das übergebene, erstellt, und alle Werte – bis auf die zu entfernende Zahl – in dieses neue Array übertragen.
private boolean checkSudo(int[][])
Negiert alle bereits eingetragenen Felder des Sudokus, so dass später unterschieden werden kann, welche Felder vorgegeben waren und welche nicht. Außerdem wird gleichzeitig überprüft, ob das übergebene Sudoku überhaupt gültig ist.
Um dies zu erreichen wird jedes Feld des Sudokus betrachtet und falls es größer als 0 ist negiert. Parallel dazu wird getestet, ob sich die aktuelle Zahl an dieser Stelle befinden darf. Dies geschieht mit der Methode getPossible und der statischen Methode binarySearch der Klasse java.util.Arrays. Sollte ein ungültiges Sudoku vorliegen, wird false zurück gegeben. Ansonsten true.
private void finishSudo(int[][])
Kehrt die Änderungen der Methode checkSudo auf ähnliche Weise wieder um.
private int[] getPossible(int[][], int, int)
Erstellt ein int-Array, welches alle möglichen Zahlen für ein bestimmtes Feld speichert. Vorgehensweise:
- Anlegen der Variablen
quadStartXundquadStartY, welche auf den ersten Punkt des Quadrats zeigen, in dem sich unser aktuelles Feld befindet - Füllen einer ArrayList mit den Werten 1-9
- Alle Zahlen aus der ArrayList entfernen, die bereits in der aktuellen Reihe horizontal oder vertikal vorkommen
- Alle Zahlen aus der ArrayList entfernen, die sich bereits im aktuellem Quadrat befinden
- Die ArrayList in ein Array umwandeln und zurückgeben
private boolean solve(int[][], int, int)
Diese Methode ist das Herzstück unserer Klasse und löst für uns das Sudoku. Sie wählt für ein bestimmtes Feld eine Zahl aus und ruft sich selbst (rekursiv) auf. Falls ein solcher Aufruf keine mögliche Zahl mehr findet, macht die Methode selbstständig „einen Schritt zurück“ und wählt für das vorhergehende Feld (sofern es sich nicht um ein Vorgegebenes handelt) eine andere Zahl aus. Ist dies nicht möglich wird ein weiteres Feld zurück „gegangen“, bis eine mögliche Lösung gefunden wurde.
Betrachten wir solve etwas genauer:
- Zeile 1: Methodenkopf, erwartet das Sudoku-Feld und die aktuelle Position
- Zeile 3: Anlegen eines Arrays, welches (falls es sich beim aktuellen Feld um keine vorgegebene Zahl handelt) später alle möglichen Zahlen für das aktuelle Feld speichert
- Zeilen 4 und 5: Anlegen von Variablen, die die Position des nächsten Feldes speichern
- Zeile 6: Falls das Feld gefüllt werden soll …
- Zeile 7: … Mögliche Zahlen für dieses Feld auslesen
- Zeilen 8-10: … Falls es keine möglichen Zahlen gibt, einen Schritt zurück gehen (
falsezurück geben) - Zeile 11: … Dem aktuellen Feld die erste, mögliche Zahl zuweisen
- Zeilen 13-19: Manipulation der Variablen für die Position des nächsten Feldes. Falls es kein weiteres Feld mehr geben sollte, wird
truezurückgegeben - Zeile 20: Solange eine Schleife durchlaufen, bis der rekursive Aufruf
truezurückliefert … - Zeilen 21-23: … Falls es sich um ein vorgegebenes Feld handelt, muss ein Schritt zurück gemacht werden (Rückgabe von
false) - Zeilen 24-31: … Falls es sich um kein vorgegebenes Feld handelt, wird der Wert des aktuellen Feldes aus der Liste der möglichen Zahlen gelöscht und die nächste mögliche Zahl ausgewählt. Gibt es keine weiteren möglichen Zahlen mehr, muss ein Schritt zurück gegangen werden
- Zeile 33: Ist die Methode fehlerfrei durchgelaufen, wird
truezurückgegeben
public boolean solve(int[][])
Diese Methode darf als einzige von außen aufgerufen werden und löst ein 9×9 Sudoku-Feld. Um diese Lösung zu erzielen, werden ausschließlich die bereits bekannten, anderen Methoden dieser Klasse verwendet.