Frage zu Rekursion und Backtracking

[phili3]

Hallo,
ich versuche gerade zu verstehen, wie Backtracking funktioniert und habe mir dafür folgendes Video angeschaut:

Der gesamte Code ist:

public class SudokuSolver {

    private static final int GRID_SIZE = 9;

    public static void main(String[] args) {

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

        printBoard(board);

        if (solveBoard(board)) {
            System.out.println("Solved successfully!");
        }
        else {
            System.out.println("Unsolvable board :(");
        }

        printBoard(board);

    }


    private static void printBoard(int[][] board) {
        for (int row = 0; row < GRID_SIZE; row++) {
            if (row % 3 == 0 && row != 0) {
                System.out.println("-----------");
            }
            for (int column = 0; column < GRID_SIZE; column++) {
                if (column % 3 == 0 && column != 0) {
                    System.out.print("|");
                }
                System.out.print(board[row][column]);
            }
            System.out.println();
        }
    }


    private static boolean isNumberInRow(int[][] board, int number, int row) {
        for (int i = 0; i < GRID_SIZE; i++) {
            if (board[row][i] == number) {
                return true;
            }
        }
        return false;
    }

    private static boolean isNumberInColumn(int[][] board, int number, int column) {
        for (int i = 0; i < GRID_SIZE; i++) {
            if (board[i][column] == number) {
                return true;
            }
        }
        return false;
    }

    private static boolean isNumberInBox(int[][] board, int number, int row, int column) {
        int localBoxRow = row - row % 3;
        int localBoxColumn = column - column % 3;

        for (int i = localBoxRow; i < localBoxRow + 3; i++) {
            for (int j = localBoxColumn; j < localBoxColumn + 3; j++) {
                if (board[i][j] == number) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean isValidPlacement(int[][] board, int number, int row, int column) {
        return !isNumberInRow(board, number, row) &&
                !isNumberInColumn(board, number, column) &&
                !isNumberInBox(board, number, row, column);
    }

    private static boolean solveBoard(int[][] board) {
        for (int row = 0; row < GRID_SIZE; row++) {
            for (int column = 0; column < GRID_SIZE; column++) {
                if (board[row][column] == 0) {
                    for (int numberToTry = 1; numberToTry <= GRID_SIZE; numberToTry++) {
                        if (isValidPlacement(board, numberToTry, row, column)) {
                            board[row][column] = numberToTry;

                            if (solveBoard(board)) {
                                return true;
                            }
                            else {
                                board[row][column] = 0;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }



}

Aber eigentlich geht es bei meiner Frage nur um folgenden Teil:

    private static boolean solveBoard(int[][] board) {
        for (int row = 0; row < GRID_SIZE; row++) {
            for (int column = 0; column < GRID_SIZE; column++) {
                if (board[row][column] == 0) {
                    for (int numberToTry = 1; numberToTry <= GRID_SIZE; numberToTry++) {
                        if (isValidPlacement(board, numberToTry, row, column)) {
                            board[row][column] = numberToTry;

                            if (solveBoard(board)) {
                                return true;
                            }
                            else {
                                board[row][column] = 0;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

Ich verstehe bei dem Code so viel, dass irgendwann jede Zeile und Reihe korrekt befüllt ist und dann zu dem unteren "return true" gesprungen wird.
Damit wird ja dann der letzte rekursive Methodencall (sagen wir für das Beispiel jetzt mal der 20.) beendet und man springt zurück zu if(solveBoard(board)){...
Da wird dann das ausgeführt, was in der If Bedingung steht, weil solveBoard(board) ja true returnt hat. Ab da weißt ich nicht mehr genau was passiert...
Wird dann der vorherige rekursive Methodencall (jetzt der 19.) auch beendet, weil für den 19. auch true returned wurde? Damit würde man dann ja wieder zurück zu
if(solveBoard(board)){... springen und für den 18. Methodencall true returnen und dann immer so weiter, bis jeder Methodencall beendet ist.
Ist das so richtig? oder verstehe ich etwas falsch?
Vielen Dank schonmal

 

[KonradN]

Wenn ich Deinen Text richtig verstanden habe, dann drückst Du das Richtige aus. Bei dem untersten return true bedeutet es ja, dass alle Felder durchgegangen wurden und es gibt kein Feld ohne gültige Zahl. Und dieses true wird dann durch alle rekursiven Aufrufe zurück gegeben - so wie Du es beschrieben hast (Das innere return true).

Das return false bedeutet, dass für die aktuelle Position keine gültige Zahl gefunden werden konnte. Wenn false zurück gegeben wird, bedeutet das, dass eine Zahl nicht stimmt. Daher wird die zuletzt probierte Zahl verworfen und die nächste gefunden wurde.

 

[Groomit]

Hallo,

vielleicht hilft die Visualisierung des Backtracking weiter:

https://minakhamesi.github.io/Sudoku-Solver-Visualizer/