前言

什么是皇后

  • 皇后是可以攻击一行，一列，和自己的对角线的。

    那如何避免皇后攻击，也就是如何放N皇后是合理的呢

  • 也就是，一行，一列，每一个皇后的对角线 等 不能有其他皇后。

    思路

    N皇后摆放问题：皇后需要一行一行的放，看每一行放在那里

    我们关注的内容

  1. 一行一行的放，我们当前放到了第几行。也就是当前行号是多少。
  2. 当前已经摆放了的情况

    所以：一个是行号，一个是放的情况，就是本题的【状态】

    题目本质

  • 就是一个排列程序
  • 0~N行，每一行选取一个列，每个列不能重复（解决皇后行列之间攻击问题）
  • 在上面基础上，在限制上对角线不可以重复。其实就是排列加上了限制条件。

题目细节

对角线是什么，如何判断对角线是否会攻击到呢，也就是如何判断对角线的限制条件

关于 \ 对角线

  • 这条对角线的，行号减列号是相等的，也就是x-y是相等的。

  • 那就是每一个x-y，只能用一次，不能重复

    关于 / 对角线

  • 这条对角线的，行号加列号是相等的，也就是x+y是相等的。

  • 那就是每一个x+y，只能用一次，不能重复

    �代码实现，完整注释

    1. class Solution {
    2.   //存一下数字n，省着下传了
    3.   private int n;
    4.   //记录一个列号是否用过
    5.   private Map<Integer,Boolean> columnUsed = new HashMap<>();
    6.   //记录一个左\对角线的值是否用过.row - col
    7.   private Map<Integer,Boolean> leftDiagonalUsed = new HashMap<>();
    8.   //记录一个右/对角线的值是否用过 row + col
    9.   private Map<Integer,Boolean> rightDiagonalUsed = new HashMap<>();
    11.   //记录当前的选择列
    12.   private List<Integer> chosen = new ArrayList<>();
    13.   //我们的最终要返回的答案,未格式化版本
    14.   private List<List<Integer>> answer = new ArrayList<>();
    16.   public List<List<String>> solveNQueens(int n) {
    17.       //保存n
    18.       this.n = n;
    19.       //执行DFS
    20.       dfs(0);
    21.       //格式化的result
    22.       List<List<String>> result = new ArrayList<>();
    23.       //这一层循环，每一次循环代表的是一个棋牌的摆放方式
    24.       for(List<Integer> oneAnswer : answer){
    25.           //这一次循环代表的是，一个棋盘的一行的Q的位置
    26.           List<String> oneResult = new ArrayList<>();
    27.           for(Integer qIndex : oneAnswer){
    28.               //首先用一个char数组表示一行，然后全填满.
    29.               char[] row = new char[n];
    30.               Arrays.fill(row, '.');
    31.               row[qIndex] = 'Q';
    32.               String oneRowResult = new String(row);
    33.               oneResult.add(oneRowResult);
    34.           }
    35.           result.add(oneResult);
    36.       }
    37.       return result;
    39.   }
    41.   public void dfs(Integer row){
    42.       //递归终止条件。当0~(n-1)行都放完了，到n了就终止了
    43.       if(row == n){
    44.           answer.add(new ArrayList<>(chosen));
    45.           return;
    46.       }
    47.       //写核心逻辑，在一行中，考虑所有列，放在那一列上。
    48.       //也就是在0~(n-1)列中选一列没有用过的
    49.       for(int column = 0; column < n; column++){
    50.           //如果：1.这一列没有被用过 2.左右对角线都是可以使用的
    51.           if(!columnUsed.getOrDefault(column,false) && !leftDiagonalUsed.getOrDefault(row - column,false) && !rightDiagonalUsed.getOrDefault(row + column,false)){
    52.               //使用当前列，放入选择
    53.               chosen.add(column);
    54.               //记录该列为已使用
    55.               columnUsed.put(column,true);
    56.               //记录当前左右对角线为已使用。
    57.               leftDiagonalUsed.put(row - column,true);
    58.               rightDiagonalUsed.put(row + column,true);
    59.               //这一行已经放完了，去放下一行
    60.               dfs(row +1);
    62.               //都放完了要还原现场。回溯！
    63.               //设置列使用为false，变为没使用过
    64.               columnUsed.put(column,false);
    65.               //设置左右对角线未使用
    66.               leftDiagonalUsed.put(row - column,false);
    67.               rightDiagonalUsed.put(row + column,false);
    68.               //当前选择里把放在末尾的这一列去掉
    69.               chosen.remove(chosen.size()-1);
    71.           }
    72.       }
    73.   }
    74. }