Datum: 08.10.2011, 18:22, Kategorie: Java, Aufrufe: 425, Kommentare: 0
Sudoku-Löser in Java
Dies hier ist ein Sudoku-Löser, den ich in Java geschrieben habe und der mit beliebigen (quadratischen) Gitter-Größen funktioniert. Er arbeitet vollständig nach dem Backtracking-Prinzip ("Trial-And-Error"). Die Implementierung ist zugegebenermaßen sehr komplex und man hätte das gleiche Ergebnis auch mit wesentlich weniger Code-Zeilen lösen können, aber vor allem die Klasse für die Verwaltung des Sudoku-Gitters ist sehr "mächtig". So reagiert sie beispielsweise dank entsprechender Exception-Klassen gut auf Ausnahmen und bietet außerdem eine Methode zum Laden eines Sudokus aus einer Datei. Außerdem ist diese Klasse vollständig mit JavaDoc-Kommentaren versehen.Das eigentliche Lösen geschieht in der Klasse SudokuSolver, also nicht in der Klasse zur Verwaltung des Gitters, wie es eigentlich "richtig" wäre. Grund ist, dass ich den Sudoku-Löser ursprünglich als Beispiel für meine Übungsgruppe in "Algorithmen und Datenstrukturen" geschrieben habe, aber zunächst nur die Klasse SudokuGrid zur Verfügung stellen wollte, damit sich die Übungsteilnehmer mit dem Thema Backtracking auseinandersetzen können.
Klasse "SudokuGrid"
Das ist die Klasse zur Verwaltung des Sudoku-Gitters:import java.io.*; /** * * SUDOKUGRID * * Klasse zum Verwalten eines Sudoku-Gitters in einer beliebigen (quadratischen) Groesse * * @author Patrick Kreutzer, patrick.kreutzer<at>informatik.stud.uni-erlangen.de * * @version 1.0 * */ public class SudokuGrid { private int size = 0; private SudokuField[][] grid; /** * SUDOKUFIELD * * SudokuField repraesentiert ein Feld im Gitter */ class SudokuField { private int number; private boolean immutable; private int x; private int y; /** * Konstruktor der Klasse SudokuField * @param x X-Position des Felds im Gitter * @param y Y-Position des Felds im Gitter */ public SudokuField(int x, int y) { reset(); this.x = x; this.y = y; } /** * Gibt die X-Postion des Felds im Gitter zurueck * @return X-Postion des Felds im Gitter */ public int getX() { return x; } /** * Gibt die Y-Position des Felds im Gitter zurueck * @return Y-Position des Felds im Gitter */ public int getY() { return y; } /** * Gibt an, ob das Feld leer ist oder ein Wert in ihm steht * @return true, wenn bereits ein Wert in dem Feld steht; false, wenn Feld leer ist */ public boolean isSet() { return (number > 0); } /** * Gibt die Zahl in dem Feld zurueck * @return Zahl, welche in dem Feld steht bzw. 0, wenn das Feld leer ist */ public int getNumber() { return number; } /** * Setzt den Wert des Felds auf eine uebergebene Zahl * @param number Zahl, welche in das Feld geschrieben werden soll * @throws ImmutableFieldException Wird geworfen, wenn das Feld, in welches die Zahl geschrieben werden soll, nicht beschrieben werden darf (weil die Eigenschaft immutable aktiviert ist) * @throws IllegalArgumentException Wird geworfen, wenn die uebergebene Zahl ungueltig ist */ public void setNumber(int number) throws ImmutableFieldException, IllegalArgumentException { if (number > 0 && number <= size*size) { if (!immutable) this.number = number; else throw new ImmutableFieldException(); } else throw new IllegalArgumentException("Invalid number."); } /** * Die Methode schreibt eine Zahl number in das Feld, unabhaengig davon, ob in das Feld geschrieben werden darf oder nicht. Die Methode setzt den Zustand "immutable" des Felds auf true! * @param number Zahl, welche in das Feld geschrieben werden soll * @throws IllegalArgumentException Wird geworfen, wenn die uebergebene Zahl ungueltig ist */ public void setImmutableNumber(int number) throws IllegalArgumentException { if (number > 0 && number <= size*size) { this.number = number; this.immutable = true; } else throw new IllegalArgumentException("Invalid number."); } /** * Gibt zurueck, ob in das Feld geschrieben werden darf oder nicht * @return true, wenn in das Feld NICHT geschrieben werden darf, false sonst */ public boolean getImmutable() { return immutable; } /** * Setzt den Zustand "immutable" des Felds auf einen Wahrheitswert * @param immutable true, wenn das Feld vor dem Beschreiben geschuetzt werden soll / false, wenn in das Feld geschrieben werden darf */ public void setImmutable(boolean immutable) { this.immutable = immutable; } /** * Loescht die eingetragene Zahl aus dem Feld * @throws ImmutableFieldException Wird geworfen, wenn die Zahl in dem Feld nicht geaendert werden darf ("immutable") */ public void unset() throws ImmutableFieldException { if (!immutable) { number = 0; } else throw new ImmutableFieldException(); } /** * Setzt das Feld wieder in seinen Ausgangszustand zurueck (Zahl = 0, immutable = false) */ public void reset() { number = 0; immutable = false; } } /** * Konstruktor der Klasse SudokuGrid, der beim Erzeugen das Setzen der Gitter-Groesse erlaubt * @param size Gibt die Groesse des Sudoku-Gitters an, wobei das Gitter eine Breite von size*size hat * @throws IllegalArgumentExcpetion Wird bei einer ungueltigen Groesse geworfen, d.h. wenn size <= 0 ist */ public SudokuGrid(int size) throws IllegalArgumentException { if (size > 0) this.size = size; else throw new IllegalArgumentException("Invalid size."); // createField(); } /** * Konstruktor der Klasse SudokuGrid, der beim Erzeugen des Gitters ein Sudoku aus einer Datei liest * @param filename Vollstaendiger Dateiname zu der Datei, die das zu ladende Sudoku enthaelt * @throws FileNotFoundException Wird geworfen, wenn die in filename spezifizierte Datei nicht gefunden werden kann * @throws IllegalFileFormatExcpetion Wird geworfen, wenn das Datei-Format der angegebenen Datei nicht korrekt ist bzw. wenn die Datei ungueltige Werte enthaelt * @throws IOExcpetion */ public SudokuGrid(String filename) throws FileNotFoundException, IllegalFileFormatException, IOException { File f = new File(filename); // if (f.exists()) { BufferedReader reader = new BufferedReader(new FileReader(filename)); // String line; int l = 0; int p; int n; String value; char c; int v; // while ((line = reader.readLine()) != null && l < size*size +1) { if (l == 0) { try { int s = Integer.parseInt(line); this.size = s; } catch (NumberFormatException ex) { throw new IllegalFileFormatException(); } // createField(); } else { p = 0; n = 0; value = ""; // while (p < line.length() && n < size*size) { c = line.charAt(p); // if (c != ',') value += c; else { parseValue(n,l-1,value); // value = ""; // n++; } // p++; } parseValue(n,l-1,value); } // l++; } } else throw new FileNotFoundException(); } /** * Parst einen Wert aus einer Datei * @throws IllegalFileFormatException Wird geworfen, wenn die Datei einen ungueltigen Wert enthaelt */ private void parseValue(int x, int y, String value) throws IllegalFileFormatException { value = value.trim(); // int v; // if (value.length() > 0) { try { v = Integer.parseInt(value); } catch (NumberFormatException ex) { throw new IllegalFileFormatException(); } // if (v > 0 && v <= size*size) { setImmutableField(x,y,v); } else if (v != 0) throw new IllegalFileFormatException(); } } /** * Gibt die Groesse des Gitters zurueck * @return Groesse des Gitters */ public int getSize() { return size; } /** * Erzeugt innerhalb des Gitters Objekte des Typs SudokuField als Felder des Gitters */ private void createField() { grid = new SudokuField[size*size][size*size]; // for (int i = 0; i < size*size; i++) for (int j = 0; j < size*size; j++) grid[i][j] = new SudokuField(i,j); } /** * Gibt ein Feld (vom Typ SudokuField) aus dem Gitter zurueck * @param x X-Position des gewuenschten Felds * @param y Y-Position des gewuenschten Felds * @return Gibt das durch die Koordinaten spezifizierte Feld als Objekt des Typs SudokuField aus dem Gitter zurueck * @throws IllegalArgumentException Wird geworfen, wenn Koordinaten ungueltig sind */ public SudokuField getField(int x, int y) throws IllegalArgumentException { if (x >= 0 && x < size*size && y >= 0 && y < size*size) { return grid[x][y]; } else throw new IllegalArgumentException("Invalid coordinates."); } /** * Setzt ein Feld im Gitter auf einen uebergebenen Wert * @param x X-Position des Felds * @param y Y-Position des Felds * @param number Zahl, welche in das Feld geschrieben werden soll * @throws ImmutableFieldException Wird geworfen, wenn das durch die Koordinaten spezifizierte Feld nicht geaendert werden darf ("immutable") * @throws IllegalArgumentException Wird geworfen, wenn Koordinaten ungueltig sind */ public void setField(int x, int y, int number) throws ImmutableFieldException, IllegalArgumentException { if (x >= 0 && x < size*size && y >= 0 && y < size*size) { grid[x][y].setNumber(number); } else throw new IllegalArgumentException("Invalid coordinates."); } /** * Setzt ein Feld im Gitter auf einen uebergebenen Wert, unabhaengig davon, ob in das Feld geschrieben werden darf oder nicht ("immutable"). Nach dem Aufruf der Methode ist das spezifizierte Feld "immutable"! * @param x X-Position des Felds * @param y Y-Position des Felds * @param number Zahl, welche in das Feld geschrieben werden soll * @throws IllegalArgumentException Wird geworfen, wenn Koordinaten ungueltig sind */ public void setImmutableField(int x, int y, int number) throws IllegalArgumentException { if (x >= 0 && x < size*size && y >= 0 && y < size*size) { grid[x][y].setImmutableNumber(number); } else throw new IllegalArgumentException("Invalid coordinates."); } /** * Loescht den Wert aus einem Feld im Gitter * @param x X-Position des Felds * @param y Y-Position des Felds * @throws ImmutableFieldException Wird geworfen, wenn das durch die Koordinaten spezifizierte Feld nicht geaendert werden darf ("immutable") * @throws IllegalArgumentException Wird geworfen, wenn Koordinaten ungueltig sind */ public void unsetField(int x, int y) throws ImmutableFieldException, IllegalArgumentException { if (x >= 0 && x < size*size && y >= 0 && y < size*size) { grid[x][y].unset(); } else throw new IllegalArgumentException("Invalid coordinates."); } /** * Leert alle Felder im Gitter */ public void clearGrid() { for (int i = 0; i < size*size; i++) for (int j = 0; j < size*size; j++) grid[i][j].reset(); } /** * Gibt das erste freie Feld im Gitter zurueck, d.h. das erste Feld, welches noch keinen Wert besitzt * @return Gibt ein Objekt vom Typ SudokuField zurueck, welches das erste freie Feld im Gitter darstellt. Die Methode gibt null zurueck, wenn es keine freien Felder mehr gibt */ public SudokuField getFirstFreeField() { for (int i = 0; i < size*size; i++) for (int j = 0; j < size*size; j++) if (!grid[i][j].isSet()) return grid[i][j]; // return null; } /** * Gibt in einem Array alle moeglichen Zahlen zurueck, die in ein bestimmtes Feld geschrieben werden koennen, ohne dass eine Sudoku-Regel verletzt wird * @param x X-Position des Felds * @param y Y-Position des Felds * @throws IllegalArgumentException Wird geworfen, wenn Koordinaten ungueltig sind * @return Gibt ein boolean-Array der Groesse size*size zurueck, das angibt, welche Zahlen in das Feld geschrieben werden duerfen und welche nicht */ public boolean[] getPossibleNumbers(int x, int y) throws IllegalArgumentException { if (x >= 0 && x < size*size && y >= 0 && y < size*size) { boolean[] result = new boolean[size*size]; // for (int i = 0; i < size*size; i++) result[i] = true; // for (int i = 0; i < size*size; i++) { if (i != y) if (grid[x][i].isSet()) result[grid[x][i].getNumber()-1] = false; if (i != x) if (grid[i][y].isSet()) result[grid[i][y].getNumber()-1] = false; } // int x1 = (x / size) * size; int y1 = (y / size) * size; // for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) if (x1+i != x && y1+j != y) if (grid[x1+i][y1+j].isSet()) result[grid[x1+i][y1+j].getNumber()-1] = false; // return result; } else throw new IllegalArgumentException("Invalid coordinates."); } /** * Gibt an, ob das Gitter mit der aktuellen Belegung korrekt ist, oder ob (mindestens) eine Sudoku-Regel verletzt wurde * @return true, wenn das Gitter mit den aktuell eingetragenen Zahlen korrekt ist oder false, wenn (mindestens) eine Sudoku-Regel verletzt wurde */ public boolean isCorrect() { boolean[] numbersRow = new boolean[size*size]; boolean[] numbersCol = new boolean[size*size]; // for (int i = 0; i < size*size; i++) { for (int j = 0; j < size*size; j++) { if (grid[i][j].isSet()) { if (numbersRow[grid[i][j].getNumber()-1]) return false; numbersRow[grid[i][j].getNumber()-1] = true; } // if (grid[j][i].isSet()) { if (numbersCol[grid[j][i].getNumber()-1]) return false; numbersCol[grid[j][i].getNumber()-1] = true; } } // for (int j = 0; j < size*size; j++) { numbersRow[j] = false; numbersCol[j] = false; } } // int x0, y0; // for (int i = 0; i < size*size; i++) { x0 = (i / size) * size; y0 = (i % size) * size; // for (int x = 0; x < size; x++) { for (int y = 0; y < size; y++) { if (grid[x0+x][y0+y].isSet()) { if (numbersRow[grid[x0+x][y0+y].getNumber()-1]) return false; numbersRow[grid[x0+x][y0+y].getNumber()-1] = true; } } } // for (int j = 0; j < size*size; j++) numbersRow[j] = false; } // return true; } /** * Gibt das Sudoku-Gitter auf der Standard-Ausgabe aus */ public void out() { String lineDelimiter = ""; // int a = 0; final int n = size * size * (size*size / 10 + 1) + size*(size + 1) + size+1; // while (a++ < n) lineDelimiter += "-"; // System.out.println(lineDelimiter); // for (int j = 0; j < size*size; j++) { System.out.print("| "); // for (int i = 0; i < size*size; i++) { if (grid[i][j].isSet()) System.out.printf("%" + (size*size / 10 + 1) + "d ",grid[i][j].getNumber()); else System.out.printf("%" + (size*size / 10 + 1) + "s ", ""); if ((i + 1) % size == 0 && i + 1 < size*size) System.out.print("| "); } // System.out.println("|"); // if ((j +1) % size == 0) System.out.println(lineDelimiter); } } } /** * IMMUTABLEFIELDEXCEPTION * Excpetion, die anzeigt, dass der Wert eines bestimmtes Feldes nicht veraendert werden darf */ class ImmutableFieldException extends IllegalArgumentException { } /** * ILLEGALFILEFORMATEXCEPTION * Zeigt an, dass das Format einer Datei ungueltig ist */ class IllegalFileFormatException extends Exception { }
SudokuGrid.java
Klasse "SudokuSolver"
Und hier folgt die Klasse, die das Lösen des Sudokus und in diesem Beispiel auch die Main-Methode beinhaltet:import java.util.*; import java.io.*; public class SudokuSolver { public static void main(String[] args) { SudokuGrid grid; // if (args.length > 0) { try { grid = new SudokuGrid(args[0]); } catch (FileNotFoundException ex) { System.out.println("File not found!"); return; } catch (IOException ex) { System.out.println("Something went terribly wrong!"); return; } catch (IllegalFileFormatException ex) { System.out.println("File is no valid Sudoku file."); return; } } else { grid = new SudokuGrid(3); // grid.setField(4,0,8); grid.setField(4,1,7); grid.setField(7,2,6); grid.setField(4,8,5); grid.setField(3,0,3); grid.setField(3,0,2); grid.setImmutableField(1,1,9); grid.setImmutableField(1,1,8); } // grid.out(); // if (grid.isCorrect()) { SudokuSolver solver = new SudokuSolver(); // if (solver.solveGrid(grid)) { System.out.println("Sudoku solved:"); grid.out(); } else { System.out.println("Sudoku cannot be solved!"); } // if (grid.isCorrect()) System.out.println("Grid is correct."); else System.out.println("GRID IS NOT CORRECT!"); } else System.out.println("The grid is not correct!"); } public boolean solveGrid(SudokuGrid grid) { SudokuGrid.SudokuField next = grid.getFirstFreeField(); // if (next != null) { return solveSingleField(next.getX(), next.getY(), grid); } else return false; } private boolean solveSingleField(int x, int y, SudokuGrid grid) { boolean[] possibleNumbers = grid.getPossibleNumbers(x,y); // int i = 0; SudokuGrid.SudokuField next; // while (i < possibleNumbers.length) { if (possibleNumbers[i]) { grid.setField(x,y,i+1); // next = grid.getFirstFreeField(); // if (next != null) { if (solveSingleField(next.getX(), next.getY(), grid)) { return true; } } else return true; } // i++; } // grid.unsetField(x,y); // return false; } }
SudokuSolver.java
Beispiel-Sudoku
Eine Datei mit einem Sudoku könnte beispielsweise wie folgt aussehen:4 0,14,0,0,9,0,0,5,11,0,0,8,0,4,6,0 0,5,16,11,0,0,0,0,0,0,6,0,13,15,14,0 15,0,4,0,0,12,6,0,0,9,10,0,0,7,0,5 0,0,10,0,1,14,7,0,0,4,5,13,0,9,0,0 0,0,0,12,0,6,13,0,0,5,11,0,2,0,0,0 8,9,0,0,11,3,16,0,0,10,15,2,0,0,12,14 13,0,0,2,8,0,1,10,3,0,0,12,9,0,0,7 0,1,11,10,0,0,0,9,7,0,0,0,0,3,4,0 0,4,8,15,0,0,0,6,2,0,0,0,5,12,10,0 2,0,0,5,7,0,4,16,0,0,0,6,1,0,0,3 12,10,0,0,5,11,8,0,0,3,16,1,0,0,15,0 0,0,0,7,0,10,2,0,0,8,14,0,4,0,0,0 0,0,15,0,14,7,11,0,0,13,9,10,0,2,0,0 4,0,12,0,0,13,10,0,0,16,2,0,0,5,0,15 0,6,1,3,0,2,0,0,0,0,7,0,14,16,13,0 0,0,13,0,0,0,0,15,14,0,0,4,0,10,7,0Die erste Zeile gibt die Größe des Sudokus an. Da nur quadratische Sudokus möglich sind, bedeutet die "4" in diesem Beispiel, dass das Sudoku-Gitter 4*4=16 Felder breit und hoch ist. Anschließend folgen pro Zeile jeweils die Zahlen, die in den jeweiligen Feldern stehen. Eine "0" steht dabei für ein leeres Feld.
Die Datei muss einfach als Text-Datei gespeichert werden. Beim Start des Java-Programms muss als erster Parameter dann nur noch der Name der Datei übergeben werden.
In diesem Beispiel gibt das Programm folgendes auf der Konsole aus:
--------------------------------------------------------- | 14 | 9 5 | 11 8 | 4 6 | | 5 16 11 | | 6 | 13 15 14 | | 15 4 | 12 6 | 9 10 | 7 5 | | 10 | 1 14 7 | 4 5 13 | 9 | --------------------------------------------------------- | 12 | 6 13 | 5 11 | 2 | | 8 9 | 11 3 16 | 10 15 2 | 12 14 | | 13 2 | 8 1 10 | 3 12 | 9 7 | | 1 11 10 | 9 | 7 | 3 4 | --------------------------------------------------------- | 4 8 15 | 6 | 2 | 5 12 10 | | 2 5 | 7 4 16 | 6 | 1 3 | | 12 10 | 5 11 8 | 3 16 1 | 15 | | 7 | 10 2 | 8 14 | 4 | --------------------------------------------------------- | 15 | 14 7 11 | 13 9 10 | 2 | | 4 12 | 13 10 | 16 2 | 5 15 | | 6 1 3 | 2 | 7 | 14 16 13 | | 13 | 15 | 14 4 | 10 7 | --------------------------------------------------------- Sudoku solved: --------------------------------------------------------- | 7 14 2 13 | 9 16 15 5 | 11 1 3 8 | 10 4 6 12 | | 9 5 16 11 | 10 4 3 8 | 12 2 6 7 | 13 15 14 1 | | 15 3 4 1 | 13 12 6 11 | 16 9 10 14 | 8 7 2 5 | | 6 12 10 8 | 1 14 7 2 | 15 4 5 13 | 16 9 3 11 | --------------------------------------------------------- | 3 15 7 12 | 4 6 13 14 | 1 5 11 9 | 2 8 16 10 | | 8 9 5 4 | 11 3 16 7 | 13 10 15 2 | 6 1 12 14 | | 13 16 6 2 | 8 15 1 10 | 3 14 4 12 | 9 11 5 7 | | 14 1 11 10 | 2 5 12 9 | 7 6 8 16 | 15 3 4 13 | --------------------------------------------------------- | 16 4 8 15 | 3 1 14 6 | 2 7 13 11 | 5 12 10 9 | | 2 11 14 5 | 7 9 4 16 | 10 15 12 6 | 1 13 8 3 | | 12 10 9 6 | 5 11 8 13 | 4 3 16 1 | 7 14 15 2 | | 1 13 3 7 | 15 10 2 12 | 9 8 14 5 | 4 6 11 16 | --------------------------------------------------------- | 5 8 15 16 | 14 7 11 3 | 6 13 9 10 | 12 2 1 4 | | 4 7 12 14 | 6 13 10 1 | 8 16 2 3 | 11 5 9 15 | | 10 6 1 3 | 12 2 9 4 | 5 11 7 15 | 14 16 13 8 | | 11 2 13 9 | 16 8 5 15 | 14 12 1 4 | 3 10 7 6 | --------------------------------------------------------- Grid is correct.