力扣51 N皇后 Java版本

文章目录

• 题目描述
• 代码

题目描述

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

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

代码

class Solution {
    public List<List<String>> result = new ArrayList<>();
    public LinkedList<String> path = new LinkedList<>();

    public List<List<String>> solveNQueens(int n) {
        //创建一个二维数组用来标记是否这个位置使用
        boolean[][] used = new boolean[n][n];
        for(boolean[] c:used){
            Arrays.fill(c,false);
        }
        char[][] desk = new char[n][n];
        for(char[] c:desk){
            Arrays.fill(c,'.');
        }
        backTracking(desk,n,0,used);
        return result;
    }

    public void backTracking(char[][] desk, int n, int row,boolean[][] used) {//需要传递现在的棋盘、总数n、现在的行数
        //递归出口
        if (row == n) {
            //棋盘所有的行都已经存在一个皇后了，所以满足条件
            result.add(toResult(desk));
            return;
        }

        for (int j = 0; j < n; j++) {//j表示要放置皇后位置的纵坐标
            if (isOk(desk, row, j, n,used)) {
                desk[row][j] = 'Q';
                used[row][j] = true;
                backTracking(desk, n, row + 1,used);
                desk[row][j] = '.';
                used[row][j] = false;
            }
        }

    }

    //用来判断是否可以放置
    public boolean isOk(char[][] desk, int x, int y, int n,boolean[][] used) {

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (used[i][j]==true){
                    //如果是当前位置就跳过
                    if (x==i&&y==j){
                        continue;
                    }
                    //和当前位置是同一行或者同一列都不行
                    if (i==x||j==y){
                        return false;
                    }
                    //在一个斜线上也不行
                    if ((i-x)==(j-y)||(i-x)==(y-j)){
                        return false;
                    }
                }
            }
        }
        return true;
    }

    //用来将二维数组转换为字符串
    public List toResult(char[][] desk) {
        List<String> list = new ArrayList<>();
        for (char[] c :desk) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}