如何從遞歸函數中提取基本返回值？

Question

這是我的遞歸函數，用於解決N-Queens問題，要求查找棋盤上的皇后配置的數量，以便它們不能相互攻擊。在validPosition這個函數的幫助下，這個函數成功地爲每個N的值輸入了合適的次數(curRow == N)。但是，我不清楚如何提取這些信息。如果函數輸入基本情況10次，則此函數應該返回10.

但是，讓它返回布爾值是在其遞歸調用中有條件地分支的技術。是否有一個乾淨而一致的方法來輸入基本情況正確的次數，併成功地將該信息傳播到根函數調用並將其返回給調用者？

static boolean findNQueensSolutions(int N, int curRow, int[][] board, int result) { 

    if (curRow == N) { 
     return true; 
    } 

    for (int curCol = 0; curCol < N; curCol++) { 

     if (validPosition(board, curRow, curCol, N)) { 

      board[curRow][curCol] = 1; 

      if (findNQueensSolutions(N, curRow + 1, board, result)) { 
       return true; 

      } 

      board[curRow][curCol] = 0; 
     } 

    } 
    return false; 
} 

Answer 1

你需要收集信息，關於成功的位置，就像這樣：

static int findNQueensSolutions(int N, int curRow, int[][] board) { 
    if (curRow == N) 
     return 1; // found 1 position 

    int result = 0; // found 0 positions yet 
    for (int curCol = 0; curCol < N; curCol++) 
     if (validPosition(board, curRow, curCol, N)) { 
      board[curRow][curCol] = 1; 
      result += findNQueensSolutions(N, curRow + 1, board); // do not return immediately, maybe there are more? 
      board[curRow][curCol] = 0; 
     } 
    return result; 
}