In dieser Kata geht es darum, eine Anwendung zu schreiben, die mir das Lösen eines Sudokus ermöglicht und Falscheingaben überprüft.
Wenn ich beispielsweise das folgende Ausgangsbild habe:
#-------#-------#-------#
| 5 6 9 | 3 2 8 | 7 4 1 |
| 4 3 2 | 7 5 1 | 6 9 8 |
| 1 8 7 | 4 6 9 | 5 3 2 |
#-------#-------#-------#
| 9 1 8 | 2 7 5 | 4 6 3 |
| 7 5 3 | 6 0 4 | 2 1 9 |
| 2 4 6 | 1 9 3 | 8 7 5 |
#-------#-------#-------#
| 6 2 1 | 5 3 7 | 9 8 4 |
| 8 7 4 | 9 1 2 | 3 5 6 |
| 3 9 5 | 8 4 6 | 1 2 7 |
#-------#-------#-------#
soll ein Aufruf der Sudoku-Klasse möglich sein:
game.enterDigit(8, 5, 5);
Während hingegen die folgenden Aufrufe zu entsprechenden Exceptions führen:
game.enterDigit(-1,5,5) --> IllegalArgumentException mit Message "Only digits [1..9] are allowed."
game.enterDigit(10,5,5) --> IllegalArgumentException mit Message "Only digits [1..9] are allowed."
game.enterDigit(1,10,1) --> OutOfBoundsException mit Message "Only rows from [1..9] are allowed."
game.enterDigit(1,1,10) --> OutOfBoundsException mit Message "Only columns from [1..9] are allowed."
game.enterDigit(6,5,5) --> IllegalArgumentException mit Message "Same digit 6 in the same row 5."
game.enterDigit(9,5,5) --> IllegalArgumentException mit Message "Same digit 9 in the same column 5."
game.enterDigit(1,5,5) --> IllegalArgumentException mit Message "Same digit 1 in the same quadrant."
Es soll zusätzlich eine Methode status geben, die das aktuelle Board in der obigen Variante ausgibt, also unbesetzte Stellen beispielsweise mit 0 versieht.
new Sudoku().status
liefert also:
#-------#-------#-------# | 0 0 0 | 0 0 0 | 0 0 0 | | 0 0 0 | 0 0 0 | 0 0 0 | | 0 0 0 | 0 0 0 | 0 0 0 | #-------#-------#-------# | 0 0 0 | 0 0 0 | 0 0 0 | | 0 0 0 | 0 0 0 | 0 0 0 | | 0 0 0 | 0 0 0 | 0 0 0 | #-------#-------#-------# | 0 0 0 | 0 0 0 | 0 0 0 | | 0 0 0 | 0 0 0 | 0 0 0 | | 0 0 0 | 0 0 0 | 0 0 0 | #-------#-------#-------#
Die Klasse Sudoku hat folgenden Entwurf:
Erweiterungen
Vorausgefülltes Sudoku
Erweitere den Konstruktor so, dass ein vorgegebenes Sudoku-Feld initialisiert werden kann.
class Sudoku {
Sudoku(int[][] initialBoard) {
// setze feld
}
}
Anschließend kann direkt über die Methode status geprüft werden, ob das Feld korrekt gesetzt wurde.
Sudokus anderer Dimension
Schreibe Dein Programm so um, dass Du auch ein 2 * 2 Sudoku oder 4 * 4 ermöglichst.
Beachte dabei, neben der Anzahl der Zeilen und Spalten auch den Wertebereich der einzutragenden Zahlen.
class Sudoku {
Sudoku(int kantenlänge, int[][] initialBoard) {
// beachte Dimension
}
}
Sudoku lösen
Eine deutliche schwierigere Erweiterung wäre es, dass Sudoku komplett vom Programm lösen zu lassen. Das Stichwort hierfür ist Backtracking.
In jedem Fall kann ich für die Methode solve() hinterher prüfen, dass kein Feld mehr den initialen Wert 0 hat, also zum Beispiel isSolved() true zurückliefert.
Ein Hinweis, wie man dies in absehbarer Zeit lösen kann, ist die Idee, vorab für alle freien Felder mögliche Lösungsmengen zu finden und dann mit den Feldern, die die kleinste Lösungsmenge besitzen, beginnend das Backtracking zu implementieren.
Meine Lösung folgt… 😉
Mögliche Lösung
Im ersten Schritt erstelle ich folgenden Test:
package de.mike.kata.sudoku; import static org.hamcrest.Matchers.is; import static org.junit.Assert.assertThat; import org.junit.Test; public class SudokuTest { @Test public void testBeginningStatus() { Sudoku game = new Sudoku(); assertThat(game.status(), is( "#-------#-------#-------#\r\n" + "| 0 0 0 | 0 0 0 | 0 0 0 |\r\n" + "| 0 0 0 | 0 0 0 | 0 0 0 |\r\n" + "| 0 0 0 | 0 0 0 | 0 0 0 |\r\n" + "#-------#-------#-------#\r\n" + "| 0 0 0 | 0 0 0 | 0 0 0 |\r\n" + "| 0 0 0 | 0 0 0 | 0 0 0 |\r\n" + "| 0 0 0 | 0 0 0 | 0 0 0 |\r\n" + "#-------#-------#-------#\r\n" + "| 0 0 0 | 0 0 0 | 0 0 0 |\r\n" + "| 0 0 0 | 0 0 0 | 0 0 0 |\r\n" + "| 0 0 0 | 0 0 0 | 0 0 0 |\r\n" + "#-------#-------#-------#")); } }