Wie extrahiert man Basis-Case-Returns von der rekursiven Funktion?

Question

Dies ist meine rekursive Funktion, um das N-Queens Problem zu lösen, das die Anzahl der Konfigurationen von Königinnen auf einem Schachbrett sucht, so dass sie sich nicht gegenseitig angreifen können. Mit Hilfe von validPosition gibt diese Funktion erfolgreich den Basisfall (curRow == N) die richtige Anzahl von Malen für jeden Wert von N ein. Ich bin jedoch unklar, wie diese Informationen extrahiert werden. Wenn die Funktion den Basisfall 10 Mal eingibt, sollte diese Funktion 10 zurückgeben.

Aber es boolean zurückzugeben ist die Technik für bedingte Verzweigung bei seinem rekursiven Aufruf. Gibt es eine saubere und konsistente Methode, um den Basisfall die richtige Anzahl von Malen einzugeben und diese Information erfolgreich an den Aufruf der Wurzelfunktion weiterzugeben und an den Aufrufer zurückzugeben?

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

benötigen Sie Informationen über erfolgreiche Positionen zu sammeln, wie folgt aus:

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; 
}