LeetCode每日一题.05(N皇后)

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

示例 1：

输入：n = 4

输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

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

示例 2：

输入：n = 1

输出：[["Q"]]

提示：

• 1 <= n <= 9

解题思路：

? ? ? ? 从上往下按行依次放置皇后，标记放置过皇后的那一列，后面放皇后不可放在已标记的列上。但如此做，则会有冲突，例如会出现以下情况：

? y\x? ? ? ?0? ? ? ? ?1? ? ? ? ?2? ? ? ? 3? ? ? ??

?0? ? ? ?皇后? ? ? ? +? ? ? ? +? ? ? ? +? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? +? ? ? ? 皇后? ? ? ? +? ? ? ? +

?1? ? ? ?+? ? ? ? 皇后? ? ? ? +? ? ? ? +? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 皇后? ? ? ? +? ? ? ? +? ? ? ? +

?2? ? ? ?+? ? ? ? +? ? ? ? 皇后? ? ? ? +? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? +? ? ? ? +? ? ? ? +???????? 皇后

?3? ? ? ?+? ? ? ? +? ? ? ? +? ? ? ? 皇后? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? +? ? ? ? +? ? ? ? 皇后????????+? ? ? ?

但我们会发现：左边第一种情况下，相同左上到右下的斜线上的皇后的y坐标减去x坐标值是相同的；而右边的第二种情况下，相同右上到左下的斜线上的皇后的x坐标加上y坐标值是相同的；

因此我们可以得出结论：当有两个皇后的x,y坐标满足x+y相等或y-x相等时，该摆放方法不成立。

思路理清之后，接下来就可以用回溯的方法遍历，筛选出可行的方案。

class Solution {
    //创建一个数组放置第i个皇后的位置
    int queen[][]=new int[10][2];
    //创建一个数组记录已被占据的列
    int line[]=new int[10];
    //创建总返回数组list
    List<List<String>>list=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        List<String> l=new ArrayList<>();
        backtraver(l,n,0);
        return list;
    }
    //回溯：dfs+for循环
    public void backtraver(List<String>l,int n,int m){
        //当数组l大小等于n时表示放置完毕，存入list
        if(l.size()==n){
                list.add(new ArrayList<>(l));
                return;
            }
        if(m<n){
            //for循环遍历每一列
            for(int x=0;x<n;x++){
                //访问未被占据的列
                if(line[x]==0){
                    //判断这一行放的皇后是否会与前面的冲突，若不冲突则放进数组
                    if(isvisit(m,x)){
                    //创建对应要求的String输出
                    char[] row=new char[n];
                    Arrays.fill(row,'.');
                    row[x]='Q';
                    l.add(new String(row));
                    //将该皇后位置放入存放所有皇后位置的数组中
                    queen[m][0]=m;
                    queen[m][1]=x;
                    //将该列置零
                    line[x]=1;
                    //继续回溯
                    backtraver(l,n,m+1);
                    //访问完后退回来将该列置零再将对应元素移除
                    line[x]=0;
                    l.remove(l.size()-1);
                    }
                }
            }
        }
    }
    //判断这一行的皇后与前几行的是否冲突
    public boolean isvisit(int x,int y){
        if(x==0) return true;
        for(int z=0;z<x;z++){
            //若前几行有皇后的y-x或x+y与该皇后相同则返回false
            if(queen[z][0]+queen[z][1]==x+y||queen[z][1]-queen[z][0]==y-x)
            return false;
        }
        return true;
    }
}