N Queen

出处

Solution

本题是经典的八皇后问题。由于需要找到所有解,属于发散性问题。对于每一行,我们枚举可以将当前的皇后放在哪一列,所有目前为止可行的列都可以作为选择进行DP,即每次选择方向时都经过充分剪枝,使得每一步都朝着胜利条件前进。这样,最后得到的解“一定是需要的解。

Complexity

回溯总共n步,每次供选择的方向为n。经过剪枝之后,可以认为复杂度小于n!。

Code

boolean checkValid(int row, int col, int[] rowCol){
    for (int r = row - 1; r >=0; r--){
        if (rowCol[r] == col) return false;
        if (abs[r - row) == abs(rowCol[r] - col) return false;
    }
    return true;
}

void placeQ(int row, int[] rowCol, ArrayList<ArrayList<Integer> res){
    if (row == GRID_SIZE){
        // winning
        ArrayList<Integer> sol = new ArrayList<Integer>();
        for (int i = 0; i < GRID_SIZE; i++){
            sol.add(rowCol[i]);
        }
        res.add(sol);
        return;
    }
    
    int col = 0;
    for (col = 0; col < GRIDSIZE; col++){
        if (checkValid(row, col, rowCol)){
            rowCol[row] = col;
            placeQ(row+1, rowCol, res);
            // because we rewrite rowCol[row] everytime, 
        // so backtracking is inferred here
        }
    }
}