N 皇后问题[亲测有效]

N 皇后问题[亲测有效]n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上,并且使皇后彼此之间不能相互攻击。给定一个整数n,返回所有不同的n皇后问题的解决方案。每一种解法包含一个明确的n皇后问题的棋子放置方案,该方案中‘Q’和‘.’分别代表了皇后和空位。示例如下:输入:4输出:[[".Q..",//解法1"…Q","Q…","…..

大家好,欢迎来到IT知识分享网。

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

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

示例如下:


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

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

IT知识分享网

  • 采用回溯法解决如下:
IT知识分享网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;
    }
}

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/11912.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信