动态规划之N皇后问题_n皇后 动态规划

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

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

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

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

class Solution {
    //这个题目应该是使用回溯去解决，确定了一个皇后的位置之后就可变化为n-1个皇后寻找了，以此类推
    //在这里因为我们确定了我们需要求得所有的解然后在中间找到最合适的，那么使用回溯算法是最合适不过的了
    //首先我们需要一个数组来装载我们可以得到的所有的结果
    private List<List<String>> res;
    //然后我们需要一个数组来表示我们的棋盘，也就是n x n的表格，我们其实可以使用API---charAt来进行
    private char[][] m;
    //我们这里采用行解析，也就是我们一行一行的找，那么就需要知道对应的列还有对应的主对角线和斜对角线上的位置可以不可以放
    private boolean[] colUsed;
    private boolean[] diagonal45Used;
    private boolean[] diagonal135Used;
 
    public List<List<String>> solveNQueens(int n) {
        m=new char[n][n];
        res=new ArrayList<>();
        if(n==0) return res;  //如果n为1也就是0皇后，就直接返回我们创建的空的二维集合就可以了
       
        //然后我们需要进行填充，因为题目要求使用Q表示皇后，使用.表示空位，我们首先将所有的位置都填充为.
        for(int i=0;i<n;i++){
            //使用API进行进行填充
            Arrays.fill(m[i],'.');
        }
        colUsed=new boolean[n];
        //n个皇后的时候，总共有2*n-1个对角线
        diagonal45Used=new boolean[2*n-1];
        diagonal135Used=new boolean[2*n-1];
 
        //我们从第0行开始
        backTracking(0,n);
        return res;
    }
    private void backTracking(int row,int n){
        //如果可以递归到最后，就说明有了结果
        if(row==n){
             List<String> path=new ArrayList<>();
             //把二维数组转换为一维数组然后输出结果
             for(char[] chars:m){
                path.add(new String(chars));
             } 
             res.add(path);
             return;
        }
 
        for(int col=0;col<n;col++){
            //45°角上的所有点所在的下标值都相等，为r+c
            int diagonal45Index=row+col;
            //135°角上的所有点所在的下表为n-1（r-c）
            int diagonal135Index=n-1-(row-col);
            if(colUsed[col]||diagonal45Used[diagonal45Index]||diagonal135Used[diagonal135Index]){
                continue;
                //如果各个方向上都会有重合就不能使用，继续下一次循环
            }
            m[row][col]='Q';
            colUsed[col]=diagonal45Used[diagonal45Index]=diagonal135Used[diagonal135Index]=true;
            backTracking(row+1,n); //继续去找下一行
            //无论成不成功，都需要回溯到上一步寻找另外一个成功的案例
            colUsed[col]=diagonal45Used[diagonal45Index]=diagonal135Used[diagonal135Index]=false;
            m[row][col]='.';
        }
    }
}