N 皇后 - weblog

leetcode第51题（困难）

原链接： https://leetcode-cn.com/problems/n-queens/

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.'分别代表了皇后和空位。

示例 1：

输入：n = 4，输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1，输出：[["Q"]]

解题思路

该题采用经典的回溯算法，因为根据题目在每行或每列都不能出现多个皇后，所以每行每列有且只能有一个皇后。

采用回溯算法，先把第一个皇后放在第一列的第一个位置[0][0]，此时是满足条件的。

然后把第二个皇后放在第二列的第一个位置[0][1]，这时和第一个皇后发送冲突，第一行有两个皇后，不满足条件，移动位置，把第二个皇后放在第二列的第二个位置[1][1]，发现还冲突，对角线上有两个皇后，然后再放到第三个位置[2][1]，满足条件。

然后放第三个皇后，先将第三个皇后放第三列的第一个位置[0][2]，发现不满足条件第一行有两个皇后，放在第二个位置发现还不满足条件，对角线有两个皇后，最终第三个第四个位置都不满足条件。那么此时将先放弃第三个皇后的摆放回溯到第二个皇后，遍历第二个皇后的下一个位置[3][1]，满足条件后再放第三个皇后。当所有皇后都摆放完毕，且都满足条件后，那么这就是一种完整的解法。

依次类推，当每一个皇后所在列的所有行都遍历完后，那么算法就结束了。

通常这种算法采用递归函数来实现，当然我们用定义的栈的数据结构也可以解决，只不过复杂度更高一些。

在判断放置每个皇后是否满足条件的时候可以采用状态压缩的方式，例如在表示二维数组的每一行上是否有皇后时，我们可以定义一个一维数组去表示比如：hang[n]={1,0,1,0}，意思就是第一行和第三行有一个皇后，第二行和第四行没有皇后，采用这个方法就可以很快速的知道某一行是否有皇后，那么列和斜线都可以采用这种方案。只需要在放置皇后以后去改变该位置上数组的值就可以。

代码（java）

class Solution {
    public List<List<String>> solveNQueens(int n) {
        return begin(n);
    }
    int w,hh;
    int [] hang,lie,s,x;
    char area[][];
    List<List<String>> list=new ArrayList<>();
    public List<List<String>> begin(int n) {
        hang=new int[n];
        lie=new int[n];
        s=new int[2*n-1];
        x=new int[2*n-1];
        w=(hh=n)-1;
        area=new char[n][n];
        for(int i=0;i<hh;i++){
            for(int j=0;j<hh;j++){
                area[i][j]='.';
            }
        }
        dfs(0);
        return list;
    }
    //第n个
    public void dfs(int n){
        if(n>=hh){
            ArrayList arrayList=new ArrayList(hh);
            for(int i=0;i<hh;i++){
                StringBuilder stringBuilder=new StringBuilder();
                for(int j=0;j<hh;j++){
                    stringBuilder.append(area[i][j]);
                }
                arrayList.add(stringBuilder.toString());
            }
            list.add(arrayList);
            return;
        }
        for (int i=0;i<hh;i++){
            int ni=n+i;
            int wi=n+(w-i);
            if(hang[i]==1||lie[n]==1||s[ni]==1||x[wi]==1){
                continue;
            }else{
                hang[i]=1;lie[n]=1;s[ni]=1;x[wi]=1;
                area[i][n]='Q';
                dfs(n+1);
                area[i][n]='.';
                hang[i]=0;lie[n]=0;s[ni]=0;x[wi]=0;
            }
        }
    }
}