数独回溯递归 (Java)

Question

这个应该可以创建一个有效的数独字段。我已经删除了方形检查，这不是我现在遇到的问题的一部分，所以不要对此感到疑惑。

我的问题是，当无法正确添加 9 时，该方法会中断。我不知何故不知道如何将它 return 到前一点并向上计数，这将创建一条新的“路径”，所以我认为如果我做对了，一切都应该没问题。我仍在努力使用递归:-/

据我所知，我认为 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;

    }

Answer 1

我没有看检查状态是否正确的代码（因为它不完整），只是看尝试不同解决方案的代码。

你应该做的是在当前位置测试一个数字。如果这是一个可行的解决方案，那么如果这是最后一个字段 (8,8)，我们就完成了。如果不是，请尝试在下一个字段中放置一个数字。如果成功，那么我们就完成了（因为所有数字都是正确的）。如果不成功，请尝试下一个数字。

如果 none 个数字有效，那么我们处于无法继续的状态，return 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;
}

数独回溯递归 (Java)

Sudoku Backtracking Recursion (Java)

java

recursion

sudoku

backtracking

recursive-backtracking