算法-N皇后堆栈溢出

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)，它...

Answer 2

问题是当使用false调用recurseMark时。下面是一个正确的recurseMark()：

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] != null) 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);
}

我们在这里所做的是切换到一个布尔类，而不是原始的布尔值，并使用null大小写来表示"square not visited“。因为它是"square not visited“状态是"false”。