java - 算法 - N Queens Stack Overflow

Question

我正在尝试编写一个回溯代码，用于查找 NQueens 问题中解的数量。但是当我尝试标记放置皇后不安全的对角线网格时，我遇到了堆栈溢出。

int dim;

private void recurseMark(int row, int col, boolean[][] board, boolean val) {
    if(row >= dim || col >= dim || row < 0 || col < 0) return;
    if(board[row][col]) return;
    System.out.println("Row " + row + " Col " + col);
    board[row][col] = val;
    recurseMark(row+1, col-1, board, val);
    recurseMark(row+1, col+1, board, val);
    recurseMark(row-1, col+1, board, val);
    recurseMark(row-1, col-1, board, val);
}

private void mark(int i, int k, boolean[][] board, boolean val) {
     for(int j = 0; j < dim; j++) {
        board[i][j] = val;
    }

    for(int j = 0; j < dim; j++) {
        board[j][k] = val;
    }
}

private int countQueens(int i, boolean[][] board) {
    int count = 0;

    if(i == dim) return 1;

    for(int k = 0; k < dim; k++) {
        if(!board[i][k]) {
            board[i][k] = true;
            mark(i, k, board, true);
            System.out.println("Giving " + i + " " + k);
            recurseMark(i, k, board, true);
            count += countQueens(i+1, board);    
            recurseMark(i, k, board, false);
            mark(i, k, board, false);
        }
    }

    return count;
}


public int totalNQueens(int n) {
    dim = n;

    boolean[][] board = new boolean[n][n];

    return countQueens(0, board);
}

public static void main(String[] args) {
    NQueens nq = new NQueens();
    System.out.println(nq.totalNQueens(2));
}

知道为什么它会因为 N 值较小而溢出吗？

Answer 1

因为你的方法无限递归。

如果棋盘是 8x8，那么例如 recurseMark(1, 1, board, false) 调用 recurseMark(2, 2, board, false) 调用 recurseMark(1, 1, board, false) 调用 recurseMark(2, 2, board, false) 调用 recurseMark(1, 1, board, false) 哪个...