1

我编写了一种使用递归和回溯来找到 N-Queens 问题的解决方案的方法。我现在要做的是修改此方法，以便它可以找到所有可能的解决方案。我假设我需要使用 2D 整数数组来存储所有解决方案，并且还添加一个计数器，每次找到解决方案时都会递增。但是，一旦找到解决方案并继续回溯以找到所有其他可能的解决方案，我似乎无法理解如何使这种方法继续下去。我认为我要做的就是摆脱“回归真实”；找到解决方案时会发生这种情况，但是我不知道如何使该方法递归地确定是否找到解决方案....这是我现在拥有的单一解决方案版本：

public boolean placeQueens(int x, int y) {
    if (!underAttack(x, y)) {
        queen[x] = y;
        board[x][y] = true;
        if (x + 1 == boardSize
                ||placeQueens(x + 1, 0)) {
            return true;
        }
        queen[x] = 0;
        board[x][y] = false;
    }
    if (y + 1 == boardSize) {
        return false;
    }
    return placeQueens(x, y + 1);
}

编辑：修正了方法，结果如下。它仍然可能有点混乱，但它有效！我没有打印找到的每个解决方案，而是将其添加到数组中。我仍然拥有 Queen[] 变量的原因是我可以让解决方案数组独立于棋盘状态。而我仍然拥有 board[][] 变量的原因是因为它使 underAttack() 方法更容易编写（尤其是计算斜率）......无论如何，我非常感谢大家的帮助！

public void placeQueen(int x) {
    if (x == N) {            
        for (int i : queen) {
            solution[counter][i] = queen[i];
        }
        counter++;            
        return;
    }
    for (int y = 0; y < N; y++) {
        if (!underAttack(x, y)) {                
            queen[x] = y;
            board[x][y] = true;
            placeQueen(x + 1);
            queen[x] = 0;
            board[x][y] = false;
        }
    }
}
4

2 回答 2

1

目前，您只是在寻找一种解决方案。当您找到 ax,y 可以放置皇后的位置时，您向前移动一列并尝试将皇后放置在以下列中。

为了生成所有解决方案，而不是返回 true，您可以在最后打印最终数组，回溯并更改您在当前列的位置，然后尝试再次生成解决方案。

伪代码可以是这样的

Place(x)

  // Here x is the column number where you want to put the queen
  if (x == board_size + 1):
      print (array A)
      return;
  for y from 0 to board_size:
       if (!underattack(A,x,y)) // A[x] = y => the queen is at row y in col x
            A[x] = y
            Place(x+1)
  return;

在这里，即使我们找到一个有效的特定 (x,y)，我们也会回溯并尝试当前 x 的后续 y 值。

于 2013-11-28T07:08:01.080 回答
0

这是 NQueens 的伪代码：-

void Nqueens(int row,int columns[],int n) {

if(row<n) {

for(int col=0;col<n;col++) {

  if(safe(row,col,columns)) {

     columns[i] = k;
     NQueens(row+1,columns);
  }

}



}

else {

   printf("solution: \n");

   for(int i =0;i<n;i++) {

       printf("(%d,%d)\n",i,columns[i]);
   }

}

}
于 2013-11-28T07:11:57.673 回答