java - 我怎样才能修改这个递归回溯算法 (NQueens) 来找到所有的解决方案而不是一个？

Question

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

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;
        }
    }
}

Answer 1

目前您正在寻找一种解决方案。当您找到可以放置皇后的 x,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 值。