source: Java_Quellcode_SOOP_Vorlesung/arrays/SudokuSolver.java @ 414

package eu.hsrw.tr.prog.vl.arrays;

/**
 * Löst 9x9 Sudokus mittels Brute Force und Backtracking: Durchprobieren von
 * oben links nach unten rechts
 * 
 * @author Thomas Richter
 * 
 */
public class SudokuSolver {

    /**
     * Testet, ob die Zahl bereits in der angegebenen Zeile des Sudokus vorkommt
     * 
     * @param a
     *            9x9 Array mit dem Sudoku
     * @param zeile
     *            zu prüfende Zeile
     * @param kandidat
     *            zu prüfende Zahl
     * @return false, falls die Zahl vorkommt, sonst true
     */
    public static boolean zeileOK(int[][] a, int zeile, int kandidat) {
        for (int i = 0; i < a.length; i++) {
            if (Math.abs(a[zeile][i]) == kandidat) {
                return false;
            }
        }
        return true;
    }

    /**
     * Testet, ob die Zahl bereits in der angegebenen Spalte des Sudokus
     * vorkommt
     * 
     * @param a
     *            9x9 Array mit dem Sudoku
     * @param spalte
     *            zu prüfende Spalte
     * @param kandidat
     *            zu prüfende Zahl
     * @return false, falls die Zahl vorkommt, sonst true
     */
    public static boolean spalteOK(int[][] a, int spalte, int kandidat) {
        for (int i = 0; i < a.length; i++) {
            if (Math.abs(a[i][spalte]) == kandidat) {
                return false;
            }
        }
        return true;
    }

    /**
     * Testet, ob die Zahl bereits in dem 3x3 Block vorkommt, in dem das durch
     * zeile und spalte festgelegte Feld liegt
     * 
     * @param a
     *            9x9 Array mit dem Sudoku
     * @param zeile
     *            Zeile des Elements, dessen 3x3 Block getestet werden soll
     * @param spalte
     *            Spalte des Elements, dessen 3x3 Block getestet werden soll
     * @param kandidat
     *            zu prüfende Zahl
     * @return false, falls die Zahl vorkommt, sonst true
     */
    public static boolean blockOK(int[][] a, int zeile, int spalte, int kandidat) {
        // Feststellen in welchem Block wir eigentlich sind -> wir benötigen die
        // kleinste Zeile und die kleinste Spalte dieses Blocks
        int startZeile = zeile - zeile % 3;
        int startSpalte = spalte - spalte % 3;

        for (int i = startZeile; i < startZeile + 3; i++) {
            for (int j = startSpalte; j < startSpalte + 3; j++) {
                if (Math.abs(a[i][j]) == kandidat) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Löst das übergebene 9x9 Sudoku mittels Brute Force und Backtracking: Es
     * wird mit dem Feld oben links begonnen und dann spalten- und zeilenweise
     * nach rechts unten gearbeitet. Als erster Wert wird die 1 versucht. Falls
     * der Versuch einen Konflikt auslöst, wird die Zahl immer weiter erhöht,
     * bis entweder kein Konflikt mehr auftritt oder die Zahl 10 erreicht wurde.
     * Falls 10 erreicht wurde konnte kein passender Eintrag gefunden werden,
     * das Problem muss also schon weiter vorn liegen. Es wird um ein Feld
     * zurückgegangen und dort die nächsthöhere Zahl versucht. Ggf. sind sehr
     * viele Rücksprünge erforderlich, da viele Kombinationen durchprobiert
     * werden müssen.
     * 
     * @param a
     *            zu lösendes Sudoku als 9x9 Array
     */
    public static void solve(int[][] a) {
        // wir beginnen oben links und gehen nach unten rechts durch
        // Nummer des Feldes: 0..80
        int position = 0;
        // zähle die Rücksprünge (nur zu Informationszwecken)
        int rueckspruenge = 0;

        while (position < 81) {
            // Zeile und Spalte aus der Nummer des Feldes bestimmen
            int zeile = position / 9;
            int spalte = position % 9;

            // Es werden nur Felder bearbeitet, die nicht negativ sind.
            // negative Zahlen sind die Startbelegung -> überspringen
            if (a[zeile][spalte] < 0) {
                // Zahl war negativ -> weiterrücken
                position++;
            
            } else {
                // Versuche, eine Zahl im Feld a[zeile][spalte] einzubauen
                // Beginne mit der aktuellen Zahl + 1: anfangs 0 + 1
                int kandidat = a[zeile][spalte] + 1;

                // testen, ob die Zahl einen Sudoku-Fehler verursacht
                // bei Fehler: Zahl erhöhen
                while (!zeileOK(a, zeile, kandidat) ||
                       !spalteOK(a, spalte, kandidat) ||
                       !blockOK(a, zeile, spalte, kandidat)) {
                    kandidat++;
                }

                // Warum sind wir aus der Schleife rausgekommen?
                if (kandidat < 10) {
                    // zahl < 10 hat keinen Fehler verursacht -> eintragen
                    a[zeile][spalte] = kandidat;
                    // weiterrücken zum nächsten Feld
                    position++;

                } else {
                    // zahl == 10 -> keine passende Zahl gefunden -> zurückgehen
                    // Feld auf 0 zurücksetzen damit spätere Einträge nicht verfälscht
                    // werden
                    a[zeile][spalte] = 0;

                    // Wir dürfen nicht auf ein Feld mit negativem Eintrag
                    // zurückspringen, da die negativen Zahlen die Startbelegung
                    // kennzeichnen -> Zurück bis Inhalt nicht mehr negativ
                    do {
                        position--;
                        rueckspruenge++;
                    } while (a[position / 9][position % 9] < 0);
                }
            }
        }
        System.out.println("Rücksprünge: " + rueckspruenge);
    }

    /**
     * Gibt ein Sudoku auf der Konsole aus
     * 
     * @param a
     *            zweidimensionales Array mit dem Sudoku
     */
    public static void printSudoku(int[][] a) {
        System.out.println("\n----------------------");

        for (int i = 0; i < a.length; i++) {
            System.out.print("|");
            for (int j = 0; j < a[i].length; j++) {
                System.out.print(Math.abs(a[i][j]) + " ");
                if (j % 3 == 2) {
                    System.out.print("|");
                }
            }
            if (i % 3 == 2) {
                System.out.print("\n----------------------");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {

        // Beispiele für schnell und langsam zu lösende Sudokus
        int[][] sudokuLeer = new int[9][9];

        int[][] sudokuSchnell = {
                { 0,  0, -5,  0,  0,  0,  0, -6,  0},
                { 0,  0, -8, -7,  0,  0,  0,  0,  0},
                { 0,  0,  0,  0, -3,  0,  0,  0, -9},
                { 0,  0,  0,  0,  0, -6,  0,  0,  0},
                { 0,  0, -3,  0,  0,  0,  0,  0, -7},
                { 0,  0,  0, -5,  0,  0,  0, -4,  0},
                { 0, -9,  0,  0,  0, -1,  0,  0,  0},
                { 0, -6,  0,  0,  0,  0, -7,  0,  0},
                { 0,  0,  0,  0,  0, -5,  0,  0, -8}
        };

        int[][] sudokuLangsam = {
                {  0,  0,  0,  0,  0,  0,  0,  0,  0},
                {  0,  0,  0,  0,  0,  0, -9, -6,  0},
                { -5, -8,  0,  0, -3,  0,  0,  0,  0},
                {  0, -7,  0,  0,  0, -5,  0,  0,  0},
                {  0,  0, -3,  0,  0,  0,  0,  0,  0},
                {  0,  0,  0, -6,  0,  0, -1,  0, -5},
                {  0,  0,  0,  0,  0,  0,  0, -7,  0},
                { -6,  0,  0,  0,  0, -4,  0,  0,  0},
                {  0,  0, -9,  0, -7,  0,  0,  0, -8}
        };

        int[][] sudoku;
        sudoku = sudokuSchnell;
        sudoku = sudokuLangsam;
        // sudoku = sudokuLeer;

        printSudoku(sudoku);

        solve(sudoku);

        printSudoku(sudoku);
    }
}