java - java中的谜题求解器的递归回溯

Question

只要我开始编码，就会非常上瘾。所以我尝试制作解谜游戏的新挑战。我快要完成它了，但卡住了。

主要有2个方法:puzzleSolver和check

我已经在所有情况下测试了检查方法，并且效果很好。

所以唯一的问题是解决方法，我不知道它出了什么问题。

请查看我的代码并帮助我。

非常感谢。

我将解释下面的规则。

规则:

1.每行每列中没有 3 个连续值(1 和 2)。

2.每行和每列包含相同数量的值。

如果网格[6][6]。每行和每列将有 3 个 1 和 3 个 2。

但不能有 3 个 1 或 2 彼此相邻。

示例:

grid[2][2]
0 1
1 0
Solution:
2 1
1 2

grid[2][2]
1 1
0 0
Unsolvable
It violated rule number 2. 

grid[4][4]
[0, 2, 2, 1]
[0, 2, 1, 2]
[2, 1, 0, 1]
[2, 0, 0, 0]
solution: 
[1, 2, 2, 1]
[1, 2, 1, 2]
[2, 1, 2, 1]
[2, 1, 1, 2]

grid[4][4]
[0, 2, 2, 2] <- violated rule number 2
[0, 2, 1, 2]
[2, 1, 0, 1]
[2, 0, 0, 0]
Unsolvable

grid[6][6]
[0, 0, 1, 1, 1, 0] <- violated rule #1
[0, 0, 0, 1, 0, 0]
[2, 2, 2, 0, 0, 0] <-violated rule #1
[0, 0, 0, 1, 0, 0]
[0, 1, 2, 0, 0, 0]
[0, 2, 0, 1, 0, 0]
Unsolvable

这是我的输入网格:

public static void main(String[] args) {
        int[][] grid = { { 0, 1 }, { 1, 0 } };
        int[][] grid1 = { { 0, 2, 2, 1 }, { 0, 2, 1, 2 }, { 2, 1, 0, 1 }, { 2, 0, 0, 0 } };
        int[][] grid2 = { { 0, 2, 2, 0 }, { 0, 0, 0, 0 }, { 0, 2, 0, 0 }, { 0, 0, 0, 1 } };
        int[][] grid3 = { { 0, 0, 1, 0, 2, 2 }, { 0, 0, 2, 0, 0, 0 }, { 0, 0, 1, 0, 0, 0 }, { 0, 0, 0, 2, 0, 0 },
                { 2, 0, 1, 0, 0, 0 }, { 0, 0, 2, 1, 2, 0 } };

它在某些情况下有效，但并非全部，我不知道为什么

OUTPUT
Fail to find solution
[0, 2, 2, 0]
[0, 0, 0, 0]
[0, 2, 0, 0]
[0, 0, 0, 1]
false
Solution should have:
1, 2, 2, 1
2, 1, 1, 2
1, 2, 1, 2
2, 1, 2, 1

这是我的代码

Solve 方法将运行所有行和列，并使用 check 方法来决定放置哪个值

public static boolean puzzleSolve(int[][] grid) {

        for (int row = 0; row < grid.length; row++) {
            // column start from 0 and increasing as going down
            for (int col = 0; col < grid.length; col++) {
                // start at 0, 0
                if (grid[row][col] == 0) { // if value =0, will be replaced with n
                    for (int n = 1; n < 3; n++) { // n =1 or n=2
                        grid[row][col] = n; // place n=1 then check condition
                        if (check(grid)) {
                            grid[row][col] = n;// if true, replace 0 with n

                            if (solve(grid)) { // check whole grid if violated rules
                                return true;
                            }
                        }
                    }
                    // System.out.println("No solution");
                    return false; // fail in replacing
                }
            }
        }
        // print out solved grid if succeed
        System.out.println("solution: ");
        for (int i = 0; i < grid.length; i++) {
            System.out.println(Arrays.toString(grid[i]));
        }
        return true; // success
    }
//end code

我有检查方法来检测任何违规行为，并且在任何情况下都运行良好。 我知道解决方法有问题，但找不到它。

Answer 1

在伪代码中，您的解决方案如下所示:

for each cell with value zero
    for each allowed value
        place value in cell
        check if it's a solution

演练如果单元格中全部为零会发生什么情况。第一个单元格将被赋予值 1，然后是 2，这两个值都不能解决整个网格(因为仍然有零)。因此，它会在整个网格中移动第二个单元格，依此类推，使每个单元格的值均为 2。在这种情况下，它显然找不到解决方案。

这里的第一个问题是您实际上没有进行任何递归或回溯。

正确的解决方案可能如下所示:

solve (grid, position):
    if position is past end and grid is solved
        yah!
    else
        for each allowed value
            place value in position on grid
            call solve(grid, next position)

这是递归(因为它调用自身)和回溯，因为如果它找不到解决方案，它会返回到先前的位置(在调用堆栈中位于其上方)并尝试新值。

因此，实际的解决方案可能类似于:

private void findSolutions(int[][] grid, int col, int row) {
    if (row == grid.length && isSolved(grid)) {
        printSolution(grid);
    } else {
        for (int v = 1; v <= 2; v++) {
            grid[row][col] = v;
            if (col == grid[row].length) {
                findSolutions(grid, 0, row + 1);
            } else {
                findSolutions(grid, col + 1, row + 1);
            }
        }
    }
}