Sudoku Backtracking Recursion (Java)

Question

This one is supposed to create a valid sudoku field. I have removed the square-check, that's not part of the problem I have right now, so don't wonder about that.

My problem is, that the method interrupts, when a 9 can't be added correctly. I somehow don't get how to make it return to the previous point and count up, which would create a new "path", so I think if I got that right, everything should be fine. I am still struggling with using recursion :-/

As I can tell I think that sudokuCorrect() does what it should. Edit: You can ignore boolean test. I know I don't use it, I tried to think of something, but apparently I don't get how to use it.

Output is

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

| 2 | 1 | 4 | 3 | 6 | 5 | 8 | 7 | 9 |

respectively when squarechecker is integrated it will look like

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

| 4 | 5 | 6 | 2 | 3 | 7 | 9 | 0 | 0 |

and after that lines of regardless which variant is checked. So the problem is the same.

| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

public static boolean sudoku(int i, int j) {

        boolean test = false;
        for (int n = 1; n < 10; n++) {
            feld[i][j] = n;

            if (sudokuCorrect(i, j)) {
                if (j < 8) {
                    test = sudoku(i, j + 1);
                } else if (i < 8) {
                    test = sudoku(i + 1, 0);
                }

                System.out.println(i + ", " + j);
                if ((i == 8 && j == 8 && feld[i][j] > 0) || feld[i][j] > 0) {
                    return true;
                } else {
                    return false;
                }
            }

        }
        if (test) {
            return true;
        } else {
            return false;
        }

    }

    public static boolean sudokuCorrect(int i, int j) {
        for (int a = 0; a <= j; a++) {
            map.get(i + 10).add(feld[i][a]);
        }
        if (map.get(i + 10).size() == j + 1) {
            // wenn Zeilen korrekt sind, so prüfe Spalte
            for (int a = 0; a <= i; a++) {
                map.get(j).add(feld[a][j]);
            }
            if (map.get(j).size() == i + 1) {
                return true;
            }

        }
        map.get(i + 10).clear(); // leert das HashSet
        map.get(j).clear();

        return false;

    }

Roger Lindsjö Roger Lindsjö · Accepted Answer · 2018-01-13T21:02:49

I din't look at the code that checks for correct state or not (as it wasn't complete), just the code which tries the different solutions.

What you should do is test a number in the current position. If that is a viable solution, then if this is the last field (8,8) we are done. If not, try placing a digit in the next field. If that was successful then we are done (as then all digits are correct). If it wasn't successful, try next digit.

If none of the digits works then we are in a state that is not possible to continue with, return false so we try replacing one of the number in the previous fields.

Also, I think you need to cleanup the current field before backtracking to simplify your correctness check.

Something like this:

public static boolean sudoku(int i, int j) {
    for (int n = 1; n < 10; n++) {
        // Try using n
        feld[i][j] = n;
        if (sudokuCorrect(i, j)) {
            if (i == 8 && j == 8) {
                // Last digit successful, we are done
                return true;
            }
            boolean followingSolved;
            if (j < 8) {
                followingSolved = sudoku(i, j + 1);
            } else {
                followingSolved = sudoku(i + 1, 0);
            }

            if (followingSolved) {
                // All following numbers successful, we are done
                return true;
            }
        }
        // n didn't fit, try next
    }
    // No number fit, current state not possible
    feld[i][j] = 0; // Cleanup attempt
    return false;
}

Sudoku Backtracking Recursion (Java)

1 Answers