递归 N 皇后区：缺少解决方案

Question

我写了一个 Java N 皇后拼图的小算法（带有 c*c 棋盘）。您将在下面找到我的递归方法的代码。

它没有找到所有的解决方案。

我的功能是什么

我的想法是，在 main 方法中，第一次调用我的函数，为它提供最大数量的皇后，直到找到解决方案，没有任何皇后的棋盘和这些新皇后的坐标：x=0 ,y=0.

函数会遍历棋盘。对于每个方块，它测试是否可以放置皇后 (0;0)（即：没有威胁）。皇后（0；0）可以放置吗？好吧，我们这样做（修改棋盘）并调用函数（递归调用）。此递归调用是通过以下方式完成的："maximum number of queens - 1"、修改后的棋盘和 "new-queen's y + 1"（有点复杂）。

找到 n=4 和 c=4 的解决方案（通常有两个解决方案...！）

&&问&

问&&&

&&&Q

&问&&

我函数的最新代码

private static void setQueen(int nb_queens, ArrayList<ArrayList<Boolean>> chessboard, int x, int y, ArrayList<ArrayList<ArrayList<Boolean>>> solutions) {
    if (nb_queens == 0) { // If there isn't any queen remaining, it means we found a solution
        drawChessboard(chessboard);
        solutions.add(chessboard);
    }

    for(int i = x; i < chessboard.size(); i++) {
        for (int z = y; z < chessboard.get(i).size(); z++) {
            if(!canBePlaced(i, z, chessboard)) {
                chessboard.get(z).set(i, true); // On peut donc placer cette reine(x;y) et on le fait
                setQueen(nb_queens-1, chessboard, i+1, 0, solutions);
                chessboard.get(z).set(i, false);
            }
        }
    }

}

旧代码

private static void setQueen(int nb_queens, ArrayList<ArrayList<Boolean>> chessboard, int x, int y, ArrayList<ArrayList<ArrayList<Boolean>>> solutions) {
    if (nb_queens == 0) {
        drawChessboard(chessboard); // Il n'y a plus de reine à placer => on dessine cette solution
        solutions.add(chessboard);
    }

    for(int i = x; i < chessboard.size(); i++) {
        for (int z = y; z < chessboard.get(i).size(); z++) {
            if(!isAQueenAlreadyPresent(i, z, chessboard)) {
                chessboard.get(z).set(i, true); // On peut donc placer cette reine(x;y) et on le fait
                setQueen(nb_queens-1, chessboard, i, (z+1 >= WIDTH) ? 0 : z+1, solutions);
                chessboard.get(z).set(i, false);
            }
        }
    }

}

Answer 1

哦对了，那是因为你如何递归调用，你在做什么 setQueen(nb_queens-1, chessboard, i, z+1, solutions);。 z+1 部分是问题所在，它总是会在您放置在全局板上的第一个皇后的右侧找到解决方案。

编辑：啊你之前发现了，不错。

因此，问题在于 for 循环充当 if(z>=y)，因为它从 y 开始。 i = x（读第一行）的时候可以，但是i > x的时候不行。因此，一个简单的解决方法是将 y = ( i == x ) ? y : 0 放在第一个 for 循环之后。

还有更简洁的解决方案，比如使用单个索引遍历整个棋盘。

我还建议您将参数重命名为 startX 和 startY（而不是 x 和 y，您可以在循环中使用 x 和 y 以便更清楚）。

Edit2：由于游戏规则，同一条线上永远不会有皇后，所以您可以像 setQueen(nb_queens-1, chessboard, i+1, 0, solutions); 一样进行递归调用（i+1 因为您从下一个开始直接上线）。因此，您甚至可以从 setQueen 方法中删除 int y 参数并始终从 0.

开始 z loop