51. N 皇后 (opens new window)

1.枚举+回溯

说是回溯本实质上是枚举，枚举每一行可以放置的位置。初始化二维数组a保存棋盘：

• 为1表示当前位置放置皇后
• 为0表示当前位置为空余位置
• 小于0表示当前位置禁止放置

每次放子后需要更新棋盘中的冲突位置，回溯时需要恢复冲突位置。

注意：两个不同位置的皇后可能产生相同的冲突位，因此如果采用直接赋值的方式进行更新，会把其它位置上的冲突位也一并恢复。因此这里采用增量的方式对冲突位进行标记。

class Solution {
    List<List<String>> res=new ArrayList<>();
    int[][] a;
    public List<List<String>> solveNQueens(int n) {
        a=new int[n][n];
        dfs(0);
        return res;
    }
    public void dfs(int row){
        if(row==a.length){
            List<String> path=new ArrayList<>();
            for(int i=0;i<a.length;i++){
                String s="";
                for(int j=0;j<a.length;j++){
                    if(a[i][j]==1) s+="Q";
                    else s+=".";
                }
                path.add(s);
            }
            res.add(path);
            return;
        }
        for(int i=0;i<a.length;i++){
            if(a[row][i]==0){
                a[row][i]=1;
                put(row,i);
                dfs(row+1);
                refresh(row,i);
                a[row][i]=0;
            }
        }
    }
    public void put(int x,int y){
        for(int i=x+1;i<a.length;i++){
            //错误做法：a[i][y]=-1
            a[i][y]--;
        }
        for(int i=1;;i++){
            if(x+i<a.length&&y+i<a.length){
                a[x+i][y+i]--;
            }
            else break;
        }
        for(int i=1;;i++){
            if(x+i<a.length&&y-i>=0){
                a[x+i][y-i]--;
            }
            else break;
        }
    }
    public void refresh(int x,int y){
        for(int i=x+1;i<a.length;i++){
            a[i][y]++;
        }
        for(int i=1;;i++){
            if(x+i<a.length&&y+i<a.length){
                a[x+i][y+i]++;
            }
            else break;
        }
        for(int i=1;;i++){
            if(x+i<a.length&&y-i>=0){
                a[x+i][y-i]++;
            }
            else break;
        }
    }
}