N皇后遞歸程序

Question

我想通過定義一個函數，該函數需要一個nxn布爾型數組，並填寫答案來解決n皇后問題（將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 **板，並用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;