Zur Benutzung dieses Sudokus Algorithmus'
java -jar <option> <puzzle> <puzzle> <puzzle> <...>
<option> = Option
Option 1) = Zeige Sudoku
Option 2) = Löse Sudoku mit Backtracking
Option 3) = Löse Sudoku mit optimiertem Backtracking
<puzzle> = Dateiname
Die Puzzles werden nacheinander abgearbeitet
Beispielsudokus sind diesem Thread angehängt
Das ADSTool kümmert sich um Zeitenmessung und um das Einlesen der Dateien. Ihr findet es außerdem als Dateianhang
Alles anzeigen
java -jar <option> <puzzle> <puzzle> <puzzle> <...>
<option> = Option
Option 1) = Zeige Sudoku
Option 2) = Löse Sudoku mit Backtracking
Option 3) = Löse Sudoku mit optimiertem Backtracking
<puzzle> = Dateiname
Die Puzzles werden nacheinander abgearbeitet
Beispielsudokus sind diesem Thread angehängt
Das ADSTool kümmert sich um Zeitenmessung und um das Einlesen der Dateien. Ihr findet es außerdem als Dateianhang
Quellcode
- package ads;
- /**
- * Autoren: Marco May & Torben Brodt
- */
- import fhw.ADSTool;
- public class SudokuPlay {
- public static void main(String[] args) {
- if(args.length < 2)
- System.out.println("Zur Backtracking Loesung 2 als Paramter uebergeben\nZum intelligenten Loesen eine 3");
- ADSTool.resetTime();
- if(args.length > 1)
- for(int i=1; i<args.length; i++) {
- Sudoku feld = new Sudoku(9, args[0], args[i]);
- System.out.println(feld);
- ADSTool.showRTime();
- System.out.println();
- }
- }
- }
- class Sudoku {
- // Konstante fuer die Anzahl an Blöcken(9er/12er Sudoku) und die Breite einer Box (3 oder 4)
- public final int n, box_n;
- // Zaehlt die Anzahl der erprobten Platzierungen
- public int tries=0;
- // Sudoku Feld (noch nicht vorbelegt, da 9^12 moeglich sind)
- public byte[][] feld;
- /**
- * Konstruktor
- * args[0] = dateiname
- * args[1] = smart
- */
- public Sudoku(int n, String what, String filename) {
- this.n = n;
- this.box_n = (int)Math.sqrt(n);
- this.feld = new byte[n][n];
- //Datei einlesen
- read(filename);
- //und loesen
- if(what.equals("2")) {
- solveBacktrack(0,0);
- } else if(what.equals("3")) {
- smartSolve();
- } else if(what.equals("1")) {
- // belassen fuer einfache Ausgabe
- }
- }
- /**
- * Liest ein Raetsel ein
- */
- public void read(String filename) {
- int i=0, j=0;
- try {
- int[] file = ADSTool.readIntArray(filename);
- for(int digit : file) {
- if(j == n) {
- j = 0;
- i++;
- }
- feld[i][j] = (byte)digit;
- j++;
- }
- } catch(Exception e) {
- System.out.println("Bitte mit dem korrekten Dateinamen als Konsolenparameter starten");
- System.exit(0);
- }
- }
- /**
- * Loest das Raetsel durch Backtracking
- */
- public boolean solveBacktrack(int i, int j) {
- if(j == n) { /* Zeilenende erreicht,
- * fange wieder links an,
- * gehe eine Zeile nach unten
- * oder breche ab, wenn du ganz fertig bist
- */
- i++;
- if(i == n)
- return true;
- j = 0;
- }
- if(feld[i][j] > 0) // Das Feld ist erfolgreich gesetzt
- // Funktionsaufruf mit naechster Spalte
- return solveBacktrack(i, j+1);
- for(byte a=1; a<n+1; a++) {
- if(check(i, j, a) == false) {
- feld[i][j] = a;
- if(solveBacktrack(i, j+1))
- return true;
- }
- }
- feld[i][j] = 0; // Der Versuch war wohl nichts
- return false;
- }
- /**
- * Prueft ob dieses Feld gesetzt werden kann (ruft dabei 3 Subfunktionen auf)
- * @return-> Gibt true zurueck, wenn der Wert bereits existiert
- */
- public boolean check(int i, int j, int value) {
- tries++;
- // Fuer die Ausgabe mit SudokuSmart
- // System.out.println(""+i+"/"+j);
- if(checkHorizontal(j, value))
- return true;
- if(checkVertical(i, value))
- return true;
- if(checkBox(i, j, value))
- return true;
- return false;
- }
- /**
- * Prueft ob der Wert bereits in der (horizontalen) SPALTE existiert
- * @return-> Gibt true zurueck, wenn der Wert bereits existiert
- */
- public boolean checkHorizontal(int j, int value) {
- for(int a=0; a<n; a++)
- if(feld[a][j] == value)
- return true;
- return false;
- }
- /**
- * Prueft ob der Wert bereits in der (vertikalen) REIHE existiert
- * @return-> Gibt true zurueck, wenn der Wert bereits existiert
- */
- public boolean checkVertical(int i, int value) {
- for(int a=0; a<n; a++)
- if(feld[i][a] == value)
- return true;
- return false;
- }
- /**
- * Prueft ob der Wert bereits in der BOX existiert
- * @return-> Gibt true zurueck, wenn der Wert bereits existiert
- */
- public boolean checkBox(int i, int j, int value) {
- // oberes, linkes Eck der Box herausfinden (2|8 zu 0|6)
- int i_start = (int)(i/box_n) * box_n;
- int j_start = (int)(j/box_n) * box_n;
- for(int a=i_start; a<i_start+box_n; a++)
- for(int b=j_start; b<j_start+box_n; b++)
- if(feld[a][b] == value)
- return true;
- return false;
- }
- /**
- * SMART: Loest das Raetsel intelligenter
- */
- public boolean smartSolve() {
- int[] best = smartChoice();
- int i=best[0], j=best[1];
- if(i == -1 && j == -1) //Das Sudoku funktioniert - es gibt keine leeren Felder mehr
- return true;
- for(byte a=1; a<n+1; a++) {
- // System.out.print("pruefe wert "+a+" in ");
- if(check(i, j, a) == false) {
- feld[i][j] = a;
- if(smartSolve())
- return true;
- }
- }
- feld[i][j] = 0; // Der Versuch war wohl nichts
- return false;
- }
- /**
- * Sucht die Position der besten Möglichkeit
- * gibt es eine Anzahl von Moeglichkeiten oefter, dann
- * dann wird die letzte Zahl als beste Moeglichkeit gewaehlt,
- * um in einem späteren Schleifendurchläufen Performance zu sparen
- * @return: Gibt die Koordinaten zurueck
- */
- public int[] smartChoice()
- {
- int minCount=n, minI=-1, minJ=-1;
- for(int i=0; i<n; i++) {
- for(int j=0; j<n; j++) {
- if(feld[i][j] == 0) {
- int c = smartCount(i,j);
- if(c <= minCount) {
- minCount = c;
- minI = i;
- minJ= j;
- }
- }
- }
- }
- int[] results = {minI, minJ};
- return results;
- }
- /**
- * SMART: Zaehlt die leeren Felder (die Anzahl an moeglichen Loesungen)
- */
- public int smartCount(int i, int j) {
- boolean[] list = new boolean[10];
- for(int a=0; a<n; a++) {
- if(feld[i][a] > 0)
- list[feld[i][a]] = true; // Durch "true" schliessen wir die Felder mit Wert aus
- if(feld[a][j] > 0)
- list[feld[a][j]] = true;
- }
- //Box
- int i_start = (int)(i/box_n) * box_n;
- int j_start = (int)(j/box_n) * box_n;
- for(int a=i_start; a<i_start+box_n; a++)
- if(a != i)
- for(int b=j_start; b<j_start+box_n; b++)
- if(feld[a][b] > 0 && b != j)
- // >0 schliesst mehr Felder aus, dadurch an Pos1 der Abfrage
- list[feld[a][b]] = true;
- // Jetzt zaehlen wir die Felder, die wir gefunden haben
- byte max=0, possible=0;
- for(byte a=1; a<=n; a++) {
- if(list[a] == false)
- max++;
- else
- possible = a;
- }
- if(max == 1) {
- feld[i][j] = possible;
- }
- return max;
- }
- /**
- * Ueberschreibt die Ausgabefunktion
- * Wir verwenden hier nur einen Zaehler
- * n*n Stringerweiterungungen sind langsamer als StringBuffer
- */
- public String toString() {
- StringBuffer returns = new StringBuffer();
- for(int i=0; i<n*n; i++) {
- if(i%n == 0 && i > 0) {
- returns.append("\n");
- if(i%(box_n*n) == 0)
- returns.append("-----------------------\n");
- }
- if (i%box_n == 0 && i%n != 0)
- returns.append(" |");
- returns.append(feld[i/n][i%n] == 0 ? " " : " "+feld[i/n][i%n]);
- }
- returns.append("\nEs wurden "+tries+" Platzierungen ausprobiert in ");
- return returns.toString();
- }
- }