source: Java_Quellcode_SOOP_Vorlesung/arrays/SudokuSolverBF.java @ 187

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 SudokuSolverBF extends SudokuHelper {

    /**
     * Löst das übergebene 9x9 Sudoku mittels Brute Force und Backtracking: Es
     * wird mit dem Element 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
     * @return Informationen über die Anzahl der Rücksprünge und der
     *         Schleifeneintritte
     */
    public static String solve(int[][] a) {
        // wir beginnen oben links und gehen nach unten rechts durch        
        // Nummer des Elements: 0..80
        int element = 0;
        // zähle die Rücksprünge
        long rueckspruenge = 0;
        
        while (element <= 80) {
            // Zeile und Spalte aus der Nummer des Elements bestimmen
            int zeile = element / 9;
            int spalte = element % 9;
            
            // Es werden nur Elemente bearbeitet, die nicht negativ sind.
            // negative Zahlen sind die Startbelegung -> überspringen
            if (a[zeile][spalte] >= 0) {

                // Versuche, eine Zahl im Element a[zeile][spalte] einzubauen
                // Beginne mit der aktuellen Zahl + 1: anfangs 0 + 1
                int zahl = a[zeile][spalte] + 1;

                // testen, ob die Zahl einen Sudoku-Fehler verursacht
                // bei Fehler: Zahl erhöhen
                while (!kandidatOK(a, zeile, spalte, zahl)) {
                    loopCount++;

                    zahl++;
                }

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

                } else {
                    // zahl == 10 -> keine passende Zahl gefunden -> zurückgehen
                    // Element auf 0 zurücksetzen damit der Test nicht verfälscht wird
                    a[zeile][spalte] = 0;

                    // Wir dürfen nicht auf ein Element mit negativem Eintrag
                    // zurückspringen, da die negativen Zahlen die Startbelegung
                    // kennzeichnen -> Zurück bis Inhalt nicht mehr negativ
                    do {
                        loopCount++;

                        element--;
                        rueckspruenge++;
                    } while (a[element / 9][element % 9] < 0);                  
                }

            } else {
                // Zahl war negativ -> weiterrücken
                element++;
            }
        }
//      return rueckspruenge + ";" + loopCount;
        
        return "Rücksprünge: " + rueckspruenge + " --- LC: " + loopCount;
    }
        
    public static void main(String[] args) {
        
        int[][] sudoku = parseSudokuString(SudokuPuzzles.sExtreme2);
        
        printSudoku(sudoku);
        
        System.out.println(solve(sudoku));
        
        printSudoku(sudoku);
    }
}