再帰関数からベースケースのリターンを抽出するには？

Question

これは私がお互いを攻撃することができないようにチェスボード上のクイーンの構成の数を見つけるよう求めているN-Queensの問題を解決する私の再帰関数です。 validPositionの助けを借りて、この関数は基底ケース(curRow == N)を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; 
}