N皇后递归程序

Question

我正试图通过定义一个函数来解决n皇后问题(将n个皇后放在一个nxn板上，而不是任何两个皇后互相攻击)，该函数接受一个nxn布尔数组，并且应该在皇后应该在的位置填充正确的答案。我得到了不正确的答案，但不明白为什么递归不能工作！

bool check(bool ** board, int n, int row, int col){
  if(row == 0) return true;
  for(int r = 0 ; r < row ; ++r){
    if(board[r][col]) return false;
    int left = max(col - row + r, 0), right = min(col + row - r, n-1);
    if(board[r][left] || board[r][right]) return false;
  }
  return true;
}


bool queen(bool ** board, int n, int level = 0 ){
  for(int col = 0 ; col < n ; ++col){
    if( !check(board, n, level, col) ) continue;
    board[ level ][ col ] = true;
    if( level == n-1 ) return true;
    if( queen(board, n, level+1) ) return true;
    board[ level ][ col ] = false;
  }
  return false;
}    

在main()中，我动态创建bool ** board，并将其填充为false，然后调用皇后(board，n)。

奇怪的是，除了n=4,6之外，它还提供了正确的解决方案！

任何帮助都是非常感谢的！

Answer 1

您的错误是最小/最大操作，所以您不检查直线。这应该能起作用：

int left = col - row + r;
int right = col + row - r;

    if ( left >= 0 && board[r][left] || right < n && board[r][right])
            return false;