0

有人可以给我关于我的 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();
}
4

1 回答 1

3

我认为这是您尝试实现的算法：假设您已经M在棋盘上拥有皇后（看起来像M=N - waitingQueens或其他东西）。然后，您寻找可以放置女王的每个空方格。如果在那里放置皇后是有效的，则将正方形设置board为true，然后solve递归调用以查看是否可以放置waitingQueens-1更多皇后。

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

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

这会将正方形设置为false，这意味着棋盘现在又是空的。但是然后你solve(waitingQueens)用 跟waitingQueens=3注，这意味着你的递归solve现在将寻找一个只有 3 个皇后在棋盘上的解决方案。这不可能。并且重新递增waitingQueens回 4 将导致无限递归，因为solve(4)将solve(4)使用相同的空板进行调用。

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

此外，这需要修复：

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

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

            boolean solved = solve(waitingQueens-1);

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

于 2014-02-24T01:11:57.023 回答