N 皇后问题

喜欢ヅ旅行 2022-05-17 04:52 233阅读 0赞

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;
        }
    }