[LeetCode] N-Queens N皇后问题

桃扇骨 2022-04-14 03:48 174阅读 0赞

## 问题: ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70][]

![8-queens.png][]

## 测试数据: ##

[
     [".Q..",  // Solution 1
      "...Q",
      "Q...",
      "..Q."],
    
     ["..Q.",  // Solution 2
      "Q...",
      "...Q",
      ".Q.."]
    ]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1][]  
优化   -- 剪枝:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 2][]

思路:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 3][]  
对角线分析:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 5][]

代码;

import java.util.LinkedList;
    import java.util.List;
    import java.util.ArrayList;
    import java.util.Arrays;
    public class liubobo_8_6 {
    /// 51. N-Queens
    /// https://leetcode.com/problems/n-queens/description/
    /// 时间复杂度: O(n^n)
    /// 空间复杂度: O(n)
        private boolean[] col;//列方向是否冲突
        private boolean[] dia1;//左对角线是否冲突
        private boolean[] dia2;//右对角线是否冲突
        private ArrayList<List<String>> res;
    
        public List<List<String>> solveNQueens(int n) {
    
            res = new ArrayList<List<String>>();
            col = new boolean[n];
            dia1 = new boolean[2 * n - 1];
            dia2 = new boolean[2 * n - 1];
    
            LinkedList<Integer> row = new LinkedList<Integer>();
            putQueen(n, 0, row);
    
            return res;
        }
    
        // 尝试在一个n皇后问题中, 摆放第index行的皇后位置
        private void putQueen(int n, int index, LinkedList<Integer> row){
    
            if(index == n){//递归函数终止情况
                res.add(generateBoard(n, row));
                return;
            }
    
            for(int i = 0 ; i < n ; i ++)
                // 尝试将第index行的皇后摆放在第i列
                if(!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]){
                    row.addLast(i);
                    col[i] = true;// i列不能再有元素了
                    dia1[index + i] = true;//index +i对角线中不能再有元素了
                    dia2[index - i + n - 1] = true;//index- i + n - 1对角线中不能再有元素了
                    putQueen(n, index + 1, row);
                    col[i] = false;//回溯
                    dia1[index + i] = false;// 回溯
                    dia2[index - i + n - 1] = false;// 回溯
                    row.removeLast();//回溯
                }
    
            return;
        }
        //将row的解转换为二维数组的解
        private List<String> generateBoard(int n, LinkedList<Integer> row){
    
            assert row.size() == n;
    
            ArrayList<String> board = new ArrayList<String>();
            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;
        }
    
        private static void printBoard(List<String> board){
            for(String s: board)
                System.out.println(s);
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            int n = 4;
            List<List<String>> res = (new liubobo_8_6()).solveNQueens(n);
            for(List<String> board: res)
                printBoard(board);
        }
    }

类似问题;

1. Sudoku Solver 求解数独

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 6][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70]: /images/20220414/dd7fae72bdb64c7b98b7a71e6e48d8ae.png
[8-queens.png]: http://www.leetcode.com/wp-content/uploads/2012/03/8-queens.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1]: /images/20220414/4e3be6b57a81478b914b7052ccadc088.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 2]: /images/20220414/50cc7c88c36c456db126b21a5a2036a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 3]: /images/20220414/66d65df679b84b5d8f420105aa68d906.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 4]: /images/20220414/f90dd07697c145e68477c2b2d2036e9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 5]: /images/20220414/c6db12b8e5454b48843c74f69710849d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 6]: /images/20220414/9909bf12b8c0486abed7cbefcf497bd5.png