N 皇后问题_用回溯法解N皇后问题

全栈程序员-站长 • 2022年9月30日上午11:00 • 未分类 • 阅读 4

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

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

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例如下:


输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

采用回溯法解决如下：

class Solution {

    private List<List<String>> res = new ArrayList<>();
    private boolean[] col;    // false 代表竖方向没有皇后
    private boolean[] dia1;   // false 代表 左下 到 上右 对角线没有皇后, 这条对角线所有元素横纵坐标和相同
    private boolean[] dia2;   // false 代表 左上 到 下右 对角线没有皇后, 这条对角线所有元素横纵坐标差相同

    public List<List<String>> solveNQueens(int n) {

        if(n < 1)
            return res;

        col = new boolean[n];
        dia1 = new boolean[2*n-1];  // 对角线条数
        dia2 = new boolean[2*n-1];

        LinkedList<Integer> row = new LinkedList<>();
        putQueue(n, 0, row);

        return res;
    }

    // 尝试在一个n皇后问题中，摆放第index行的皇后位置
    public void putQueue(int n, int index, LinkedList<Integer> row){

        if(index == n){
            res.add(generateBoard(n ,row));
            return ;
        }

        for(int i=0; i<n; i++)
            if( !col[i] && !dia1[index+i] && !dia2[index-i+n-1]){   // index-i+n-1 ：将横纵坐标差值转换为数组坐标
                row.addLast(i);
                col[i] = true;
                dia1[i+index] = true;
                dia2[index-i+n-1] = true;
                putQueue(n, index+1, row);
                row.removeLast();
                col[i] = false;
                dia1[i + index] = false;
                dia2[index-i+n-1] = false;
            }
        return ;
    }

    private List<String> generateBoard(int n, LinkedList<Integer> row){

        assert(row.size() == n);

        ArrayList<String> board = new ArrayList<>();
        for(int i = 0 ; i < n ; i++){
            char[] charArray = new char[n];
            Arrays.fill(charArray, '.');
            charArray[row.get(i)] = 'Q';
            board.add(new String(charArray));
        }
        return board;
    }
}