public class Sudoku {
    int[][] field;                  // zweidimensionales Array für das Spielfeld.
    boolean[][] filledFromStart;    // Korrespondierendes Array, welches angibt,
                                    // ob ein Feld schon von Anfang an gefüllt ist.
    int line, column;               // Variablen für die aktuelle Zeile und Spalte.
    boolean finished;               // Gibt an, ob wir fertig sind

    public static void main(String[] args) {
        int[][] initialState = new int[9][9];

        // Fülle das Array für die Startfelder, leere Felder bleiben auf 0 gesetzt.
        initialState[0][0] = 8;
        initialState[0][2] = 9;
        initialState[0][3] = 2;
        initialState[0][8] = 3;
        initialState[1][0] = 7;
        initialState[1][4] = 9;
        initialState[1][5] = 3;
        initialState[2][4] = 6;
        initialState[2][5] = 1;
        initialState[3][0] = 1;
        initialState[3][2] = 4;
        initialState[3][7] = 8;
        initialState[4][2] = 3;
        initialState[4][6] = 2;
        initialState[5][1] = 6;
        initialState[5][6] = 3;
        initialState[5][8] = 4;
        initialState[6][3] = 4;
        initialState[6][4] = 5;
        initialState[7][4] = 8;
        initialState[7][5] = 2;
        initialState[7][8] = 7;
        initialState[8][0] = 3;
        initialState[8][5] = 7;
        initialState[8][6] = 4;
        initialState[8][8] = 9;

        // Erzeuge die Sudoku-Instanz und löse das Sudoku
        Sudoku sudoku = new Sudoku(initialState);
        sudoku.solveSudoku();
    }

    /**
     * Konstruktor zum Erstellen eines Sudokus mit der initiellen Belegung
     * im übergebenen Array initialState. Leere Felder sind mit 0 zu belegen.
     */
    public Sudoku(int[][] initialState) {
        field = new int[9][9];                 // initialisiere die Arrays
        filledFromStart = new boolean[9][9];

        // Initialisiere das Spielfeld mit dem Ausgangsstatus
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                field[i][j] = initialState[i][j];
                filledFromStart[i][j] = (initialState[i][j] != 0); // leeres Feld = 0
            }
        }
    }

    /**
     * Lösung durch Backtracking
     */
    public void solveSudoku() {
        finished = false;
        line = column = 0;                    // Beginne in der linken oberen Ecke
        if (filledFromStart[line][column])    // Wenn dieses Feld bereits gefüllt war
            nextFreeField();                  // gehe zum nächsten freien Feld

        while (!finished) {
            // Wenn im aktuellen Feld noch nicht alle Ziffern ausprobiert wurden
            // probiere die nächsthöhere Ziffer und, wenn keine Bedingung verletzt
            // ist, gehe zum nächsten freien Feld weiter

            for(int k = field[line][column]; k<10; k++) {
              field[line][column] = k;
              if (conditionsOK(line, column)) {
                break;
              }

            // ansonsten lösche dieses Feld und gehe zurück zum letzten Feld
            // (das kein Startfeld war)

            else {
                field[line][column] = 0;
                lastFreeField();
              }
            }
        }

        // Gib die Lösung aus
        outputSolution();
    }

    /**
     * Gibt an, ob die Eintragung im Feld (i, j) alle Bedingungen erfüllt.
     */
    private boolean conditionsOK(int i, int j) {
        boolean ok = true;
        // Erste Bedingung: keine doppelte Zahl in Zeile i

        for(int k=0; k < 9; k++) {
          if (field[i][k] == field[i][j]) ok = false;
        }

        // Zweite Bedingung: keine doppelte Zahl in Spalte j

        for(int k=0; k < 9; k++) {
          if (field[k][j] == field[i][j]) ok = false;
        }

        // Dritte Bedingung: keine doppelte Zahl im 3x3 Quadrat, das (i, j) enthält

        int top = i - (i % 3);
        int left = j - (j % 3);
        for(int k = top; k < 3; k++) {
          for(int l = left; l < 3; l++) {
            if(field[k][l] == field[i][j] && ( k != i || l != j )) ok = false;
          }
        }

        return ok;
    }

    /**
     * Gehe zum nächsten freien Feld
     */
    private void nextFreeField() {
        column++;
        if (column > 8) {
            column = 0;
            line++;
        }
        if (line > 8)
            finished = true;
        else if (filledFromStart[line][column])
            nextFreeField();
    }

    /**
     * Gehe zurück zum letzten Feld, das nicht zu Beginn gefüllt war
     */
    private void lastFreeField() {
        column--;
        if (column < 0) {
            column = 8;
            line--;
        }
        if (filledFromStart[line][column])
            lastFreeField();
    }

    /**
     * Gib die Lösung aus
     */
    private void outputSolution() {
        System.out.println();
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                System.out.print(" " + field[i][j]);
            }
            System.out.println();
        }
    }
}