source: Java_Quellcode_SOOP_Vorlesung/arrays/SudokuSolverLogic.java @ 187

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

import java.util.Arrays;

public class SudokuSolverLogic extends SudokuHelper {

    /**
     * Löscht eine Zahl aus dem Array mit den möglichen Zahlen. Ausgehend von
     * einer Zelle, die mit der Zahl belegt wird, werden die Zeile, die Spalte
     * und der Block bereinigt.
     * 
     * @param m
     *            Array mit den möglichen Zahlen für jede Zelle
     * @param zeile
     *            Zeile der aktuellen Zelle
     * @param spalte
     *            Spalte der aktuellen Zelle
     * @param zahl
     *            Zahl, die für die aktuelle gefunden wurde und daher gelöscht
     *            werden muss
     */
    public static void loescheZahl(boolean[][][] m, int zeile, int spalte, int zahl) {
        // Feststellen in welchem Block wir eigentlich sind -> wir benötigen die
        // kleinste Zeile und die kleinste Spalte dieses Blocks als Offset
        int offsetZ = (zeile / 3) * 3;
        int offsetS = (spalte / 3) * 3;
        
        for (int i = 0; i < m.length; i++) {
            loopCount++;

            // lösche aus Zeile
            m[zeile][i][zahl] = false; 
            // lösche aus Spalte
            m[i][spalte][zahl] = false;
            // lösche aus Block
            m[offsetZ + i / 3][offsetS + i % 3][zahl] = false;
        }
        // Zelle selbst komplett löschen
        Arrays.fill(m[zeile][spalte], false);
    }
    
    // Prüft, ob bestimmte Zahl Single in der gegebenen Zeile ist
    // Falls ja: Liefert die Spalte, falls nein: -1
    public static boolean sucheSingleInZeile(boolean[][][] m, int zeile, int zahl) {
        int zaehler = 0;

        // suche diese Zahl in der Zeile,
        // i läuft über die Spalten
        for (int i = 0; i < 9; i++) {
            loopCount++;

            if (m[zeile][i][zahl]) {
                zaehler++; 
            }
        }

        return (zaehler == 1);
    }

    // Prüft, ob bestimmte Zahl Single in der gegebenen Spalte ist
    // Falls ja: Liefert die Zeile, falls nein: -1
    public static boolean sucheSingleInSpalte(boolean[][][] m, int spalte, int zahl) {
        int zaehler = 0;

        // suche diese Zahl in der Spalte,
        // i läuft über die Zeilen
        for (int i = 0; i < 9; i++) {
            loopCount++;

            if (m[i][spalte][zahl]) {
                zaehler++;
            }
        }

        return (zaehler == 1);
    }

    // Prüft, ob bestimmte Zahl Single in dem gegebenen Block ist
    // Falls ja: Liefert die Position, falls nein: -1
    public static boolean sucheSingleInBlock(boolean[][][] m, int zeile, int spalte, int zahl) {
        int minZeile = (zeile / 3) * 3;
        int minSpalte = (spalte / 3) * 3;
        
        int zaehler = 0;

        for (int i = minZeile; i < minZeile + 3; i++) {
            for (int j = minSpalte; j < minSpalte + 3; j++) {
                loopCount++;

                if (m[i][j][zahl]) {
                    zaehler++;
                }
            }
        }

        return (zaehler == 1);
    }
    
    
    public static void solve(int[][] a) {
        boolean[][][] moeglich = new boolean[9][9][10];
        // erstmal ist jede Zahl in jeder Zelle möglich
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                Arrays.fill(moeglich[i][j], true);
            }
        }

        // alle Zellen durchgehen und die Vorbelegungen aus den Möglichkeiten löschen
        for (int z = 0; z < 9; z++) {
            for (int s = 0; s < 9; s++) {
                if (a[z][s] < 0) {
                    loescheZahl(moeglich, z, s, -a[z][s]);
                }
            }
        }

        // alle Singles im Sudoku setzen
        boolean single = false;
        do {
            single = false;
            for (int z = 0; z < 9; z++) {
                for (int s = 0; s < 9; s++) {
                    for (int zahl = 1; zahl <= 9; zahl++) {
                        loopCount++;

                        // ist die Zahl für dieses Feld möglich und gibt es Singles?
                        if (moeglich[z][s][zahl]
                            && (sucheSingleInZeile(moeglich, z, zahl)
                                || sucheSingleInSpalte(moeglich, s, zahl)
                                || sucheSingleInBlock(moeglich, z, s, zahl))) {

                            single = true;
                            // Sudoku setzen
                            a[z][s] = -zahl;

                            // Möglichkeiten bereinigen
                            loescheZahl(moeglich, z, s, zahl);
                        }
                    }
                }
            }
            // Kontrollausgabe
/**/
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    for (int k = 1; k <= 9; k++) {
                        System.out.print(moeglich[i][j][k] ? k : "-");
                    }
                    System.out.print("  ");
                }
                System.out.println();
            }

            System.out.println("*************************************************************************************************");
/**/
        } while (single);
    }
    
    public static void main(String[] args) {
        
        int[][] sudoku = parseSudokuString(SudokuPuzzles.sExtreme2);
        
        printSudoku(sudoku);
        
        solve(sudoku);

        printSudoku(sudoku);

        SudokuSolverBF.solve(sudoku);
        
        printSudoku(sudoku);
    }
}