如何从递归函数中提取基本情况returns？

Question

这是我的递归函数，用于解决 N-Queens 问题，该问题要求找到棋盘上皇后的配置数量，使它们无法相互攻击。在 validPosition 的帮助下，此函数成功地输入基本情况 (curRow == N) 每个 N 值的正确次数。但是，我不清楚如何提取此信息。如果函数进入基本情况 10 次，则该函数应该 return 10。

但是，return 布尔值是在其递归调用上有条件地分支的技术。是否有一种干净且一致的方法既能以正确的次数输入基本情况，又能成功将该信息传播到根函数调用，然后 return 将其传递给调用者？

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

如何从递归函数中提取基本情况returns？

How to extract base-case returns from recursive function?

java

recursion

n-queens