Sudoku Solver

Ich kann mich noch an ein Gespräch erinnern, welches aufkam als ich mit meinem Studium angefangen habe. Einer meiner Kommilitonen meinte, dass sein Freund einen Algorithmus entwickelt hat, der Sudoku-Rätsel löst. Als junger Student hört sich das enorm aufwendig an. Wie so viele Probleme in der Informatik ist die Lösung dann jedoch super simpel. Ein funktionierendes Java-Beispiel gibt es in meinem Git-Repo.

Die Regeln von Sudoku sind simpel: Ein Spielfeld aus 9 mal 9 Elementen muss mit Zahlen von 1-9 gefüllt werden. Eine richtige Lösung des Rätsels ist unter drei Bedingungen gegeben.

• Jede Zahl darf nur einmal in jeder Reihe vorkommen.
• Jede Zahl darf nur einmal in jeder Spalte vorkommen.
• Jede Zahl darf nur einmal in einem Block aus 3 mal 3 Elementen vorkommen. Das Spielfeld wird dazu in 3 mal 3 Blocke zu je 3 mal 3 Elementen aufgeteilt.

Sobald alle drei Bedingungen eingehalten werden und in jedem Element eine Zahl steht ist das Rätsel gelöst. Ein Algorithmus muss letztendlich nichts weiter tun als alle Möglichkeiten durchzuprobieren und zu schauen ob alle Bedingungen eingehalten werden.

Solche Aufgaben, bei der es eine bestimmte Anzahl an Variablen gibt, welche verschiedenen Bedingungen unterliegen werden in der Informatik als Constraint Satisfaction Problem oder kurz CSP bezeichnet.

Formel gesehen besteht ein CSP aus einer Reihe von Variablen.

In dem Fall von Sudoku stellen diese die 81 Elemente dar. Hinzu kommen Domänen, wobei jede Domäne eine mögliche Lösung des Rätsels darstellt bei der alle Elemente mit Zahlen befüllt wurden.

Die Bedingungen werden als Constraints bezeichnet. Sudoku besitzt somit drei Constraints.

Um nun eine passende Domäne für die Constraints zu finden können CSP-Libraries eingesetzt werden. Sudoku ist jedoch so simpel, dass dies überhaupt nicht nötig ist.

package com.florianbuchner.sudoku;

public final class SudokuSolver {

	public static int[][] backtrackingSearch(int[][] field) {
		return recursiveBacktrackingSearch(field, 0);
	}

	private static int[][] recursiveBacktrackingSearch(int[][] field, int pos) {
		// Ende erreicht.
		if (pos == 9 * 9)
			return field;
		// Vordefinierte Zahl wird übersprungen.
		if (field[pos / 9][pos % 9] != 0)
			return recursiveBacktrackingSearch(field, pos + 1);
		// Alle Zahlen von 1-9 durchprobieren und auf Konsistenz testen.
		for (int i = 1; i <= 9; i++) {
			if (isConsistent(field, pos, i)) {
				// Gefundene Zahl in Lösung eintragen.
				field[pos / 9][pos % 9] = i;
				// Nächste Zahl suchen
				int[][] returnvalue = recursiveBacktrackingSearch(field, pos + 1);
				if (returnvalue != null)
					return returnvalue;
				// Keine Lösungsmöglichkeit. Invalidiere Lösung und starte Teilabschnitt mit nächster Zahl.
				field[pos / 9][pos % 9] = 0;
			}
		}
		return null;
	}

	private static boolean isConsistent(int[][] field, int pos, int val) {
		// Prüfe Reihe
		for (int i = 0; i < 9; i++) {
			if (field[pos / 9][i] == val)
				return false;
		}
		// Prüfe Spalte
		for (int i = 0; i < 9; i++) {
			if (field[i][pos % 9] == val)
				return false;
		}
		// Prüfe Block
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (field[((pos / 9) / 3) * 3 + i][((pos % 9) / 3) * 3 + j] == val)
					return false;
			}
		}
		return true;
	}
}