algorithm - N皇后递归程序

Question

我试图通过定义一个函数来解决 n-queen 问题(将 n 个皇后放在 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 填充它，然后调用 queen(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;