Рекурсия судоку с возвратом (Java)

Это должно создать действительное поле судоку. Я удалил квадратный чек, это не часть моей проблемы, так что не удивляйтесь этому.

Моя проблема в том, что метод прерывается, когда не удается правильно добавить 9. Я почему-то не понимаю, как заставить его вернуться к предыдущей точке и подсчитать, что создаст новый путь, поэтому я думаю, что если я правильно понял, все должно быть в порядке. Я все еще пытаюсь использовать рекурсию: - /

Насколько я могу судить, я думаю, что sudokuCorrect () делает то, что должно. Изменить: вы можете игнорировать логический тест. Я знаю, что не использую, я пытался что-то придумать, но, видимо, не понимаю, как это использовать.

Выход

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

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

соответственно, когда Squarechecker интегрирован, он будет выглядеть как

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

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

и после этого строки независимо от того, какой вариант отмечен. Так что проблема та же.

| 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;

    }

java recursion backtracking sudoku recursive-backtracking
person kaiya    schedule 13.01.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я не смотрю на код, который проверяет правильность состояния или нет (поскольку он не был завершен), а только на код, который пробует разные решения.

Что вам нужно сделать, так это проверить число в текущей позиции. Если это жизнеспособное решение, то если это последнее поле (8,8), мы закончили. Если нет, попробуйте поместить цифру в следующее поле. Если это было успешно, то все готово (так как тогда все цифры верны). Если это не удалось, попробуйте следующую цифру.

Если ни одна из цифр не работает, значит, мы находимся в состоянии, в котором невозможно продолжить, возвращаем false, поэтому мы пытаемся заменить одно из чисел в предыдущих полях.

Кроме того, я думаю, вам нужно очистить текущее поле перед возвратом, чтобы упростить проверку правильности.

Что-то вроде этого:

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;
}
person Roger Lindsjö    schedule 13.01.2018