java - 卡在 N-Queens java 算法中。 (回溯)

Question

有人可以给我一些关于我的 java 程序的提示或指导吗？我坚持回溯的想法。这是代码。如果您看一下 solve() 方法，它会递归调用自身，但是我卡在了无法放置更多皇后并尝试回溯的地步。

public NQueens(int N)
{
    this.N = N;
    board = new boolean[N][N];
    solved = solve(N);
    if(solved == true)
    {
        System.out.println(N+"x"+N+" solution:");
        printBoard(N);
    }
    else
    {
        System.out.println("There is no solution for "+N+"x"+N+" board");
    }
}

public boolean solve(int waitingQueens)
{
    if(waitingQueens == 0) return true;

    for(int row = 0; row < N; row++)
    {

        for(int column = 0 ; column < N ; column++)
        {
            if(isValid(row, column))
            {
                board[row][column] = true;
                waitingQueens--;
                boolean solved = solve(waitingQueens);

                if(!solved)
                {
                    board[row][column] = false;

                    solved = solve(waitingQueens);
                }
                return solved;
            }

        }

    }

    return false;
}

public boolean isValid(int rowParam, int columnParam)
{
    for(int x = 0; x < N; x++)
    {
        for(int y = 0; y < N; y++)
        {
            if(board[x][y] == true) //find the already placed queens on the board and check if the queen about to be placed is on a valid position
            {
                if(x == rowParam) //check the validity of the row
                    return false;
                if(y == columnParam) //check the validity of the column
                    return false;
                if(Math.abs(x-rowParam) == Math.abs(y-columnParam)) //check the validity of the diagonals
                    return false;
            }
        }
    }
    return true;
}

public void printBoard(int printParam)
{
    for(int x1 = 0; x1 < printParam; x1++)
    {
        for(int y1 = 0; y1 < printParam; y1++)
        {
            if(board[x1][y1] == true)
            {
                System.out.print("Q ");
            }
            else{
                System.out.print("* ");
            }
        }
        System.out.println();
    }
    System.out.println();
}

Answer 1

我了解到这是您要实现的算法:假设您的棋盘上已经有 M 皇后(它看起来像 M = N - waitingQueens 之类的)。然后，您寻找可以放置皇后的每个空方格。如果在那里放置皇后是有效的，则将 board 中的正方形设置为 true，然后递归调用 solve 以查看是否可以放置 waitingQueens-1 更多皇后。

您最大的问题在于如果递归 solve 返回 false 会发生什么。假设这是一个 4x4 的棋盘，waitingQueens 是 4。您将放置第一个皇后，然后使用 waitingQueens=3 调用 solve。但是假设它说没有解决方案。然后你这样做:

            if(!solved)
            {
                board[row][column] = false;
                solved = solve(waitingQueens);
            }

这会将正方形设置为 false，这意味着棋盘现在又是空的。但是随后您使用 waitingQueens=3 调用 solve(waitingQueens)，这意味着您的递归 solve 现在将寻找只有 3 个皇后的解决方案在板上。这不可能是对的。将 waitingQueens 重新增加到 4 将导致无限递归，因为 solve(4) 将调用 solve(4)同样的空板。

这里的问题是，您已经处于一个双循环中，该循环将寻找可以放置皇后的每个方格。如果你试图在某个地方放置一个皇后但它没有成功(递归调用失败)，你将移除皇后，然后让双循环为你找到下一个有效方 block 。您不想进行另一个递归调用。所以上面的 solve(waitingQueens) 调用应该被删除。

此外，这需要修复:

            waitingQueens--;
            boolean solved = solve(waitingQueens);

减少 waitingQueens 是个坏主意，因为如果 solve 返回 false，您必须返回到下一个循环迭代，waitingQueens 会比之前少一个，这样不好。您可以通过在 if (!solved) 分支中说 waitingQueens++ 来恢复它，但何必呢？不用理会 waitingQueens ，将上面两行替换为

            boolean solved = solve(waitingQueens-1);

我不确定这两个修复是否足以产生正确答案，但它们是一个开始。虽然这些只是优化，但我还想提及一些其他事情:(1) solve 中的循环甚至不应该查看不为空的方 block 。按照你写的方式，如果你给它一个非空的正方形，isValid 将返回 false，但它是以一种迂回的方式这样做的。我可能会在调用 isValid 之前检查该方 block 是否为空。 (2) 一旦你将 M 皇后放在第 0 行到 M-1 中，你的递归调用甚至不应该查看这些行，因为我们知道你可以'同一行不能有两个皇后。如果你查看 M 行没有找到解决方案，你可以立即放弃，因为我们知道正确的解决方案必须在每一行中都有一个皇后。所以你真的只需要在 solve 中有一个循环。