java - 递归 N 皇后 : missing solutions

Question

我编写了一个 N-Queens 难题的 Java 小算法(使用 c*c 棋盘)。您将在下面找到我的递归方法的代码。

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

我的功能是什么

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

该函数将遍历棋盘。对于每个方格，它测试是否可以放置皇后(0;0)(即:没有威胁)。可以放置皇后(0;0)吗？好吧，我们这样做(修改棋盘)并调用该函数(递归调用)。此递归调用是通过以下内容完成的:“皇后的最大数量 - 1”、修改后的棋盘和“新皇后的 y + 1”(稍微复杂一点)。

找到 n=4 和 c=4 的解决方案(通常有两个解决方案...!)

&&问&

问&&&

&&&问

&问&&

我的函数的最新代码

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 来更清晰)。

编辑2:由于游戏规则，同一行上永远不会有皇后，因此您可以进行递归调用，如 setQueen(nb_queens-1, chessboard, i+1, 0, solutions); ( i+1 因为您直接从下一行开始)。因此，您甚至可以删除 int y来自 setQueen 的参数方法并始终启动 z loop为 0。