我编写了Java的N皇后难题小算法（带有c * c棋盘）。您将在下面找到我的递归方法的代码。
它没有找到所有解决方案。
我的功能是什么
这个想法是，在main方法中，首先调用我的函数，以使其获得最大的皇后数，直到找到解决方案为止，而没有任何皇后和这些新女王的坐标的棋盘：x = 0，y = 0。
该功能将通过棋盘。对于每个正方形，它测试是否可以放置皇后（0; 0）（即：无威胁）。女王（0; 0）可以放置吗？好吧，我们做到了（修改棋盘），然后调用了函数（递归调用）。此递归调用通过以下方式完成：“最大皇后数-1”，修改后的棋盘和“新皇后的y + 1”（稍微复杂一点）。
找到n = 4和c = 4的解决方案（通常有两个解决方案...！）
&& Q＆
问答
&&& Q
＆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);
}
}
}
}
最佳答案
哦，对，这是因为您递归调用的方式是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，因为您直接从下一行开始）。因此，您甚至可以从int y方法中删除setQueen参数，并始终将z loop从0开始。
关于java - 递归N-Queens:缺少解决方案，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39791116/