[路飞]_51.N 皇后

「这是我参与2022首次更文挑战的第23天，活动详情查看：2022首次更文挑战」

51. N 皇后

前言

N皇后以一道经典回溯题，是我第一次遇到的困难级别的题，是搁置了两年的没敢说理解的题。今天，搞定了

题目

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

给你一个整数 n ，返回所有不同的 **n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例1

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例2

输入： n = 1
输出： [["Q"]]

题解

回溯 + 递归

皇后彼此之间不能相互攻击的条件：

• 不在同一行
• 不在同一列
• 不在同一个斜对角线上

顺着思路一条一条来

• 假设 n=4n = 4n=4
• 第1步：在第1行第1个位置放一个皇后，根据【皇后彼此之间不能相互攻击的条件】，这一列只能放一个皇后，可以换行了
• 第2步：紧接第1步，第1行已经放皇后了，第2行要遵循【皇后彼此之间不能相互攻击】条件，找一个合适的位置放还后，这一列也只能放一个皇后，需要到第3行了
• 第3步：.....
• 第4步：.....

上述思路熟悉不熟悉，这一步的参数是上一步的结果；首先想到的是递归呀；根据上述思路先编辑大致代码

var solveNQueens = function (n) {
    // 从第1行开始
  dfs(0);
  function dfs(idx) {
      // 到第n行结束
    if (idx === n) {
      return;
    }
    for (let i = 0; i < n; i++) {
      dfs(idx+1)
    }
  }  
};

递归框架搭出来了，皇后放在哪里呢？怎么放呢？这些数据需要保存一下，因为皇后位置不同，会影响再放皇后时的位置。为了方便我们可以将皇后的位置先放在一个数组内，最后在加上放皇后的条件

var solveNQueens = function (n) {
    // 从第1行开始
  dfs(0,[]);
  function dfs(idx,path) {
      //path是记录皇后的位置的 
      // 比如 path = [0] :表示在0行0列有一个皇后，
      // path =[0,2]:表示在0行0列有1个皇后,在1行2列有1个皇后
    if (idx === n) {
      return;
    }
    // idx表示第几层，此处的for循环，为了找到这一层什么地方可以放皇后
    for (let i = 0; i < n; i++) {
      // 这里可以放皇后吗？x
      if (isCheck(path, i)) {
        //可以
        path.push(i);
        dfs(idx + 1, path);
        path.pop();
      }
    }
  }  
};

递归的时候在任意 kkk 层，从左到右枚举 [0,n] [0,n][0,n] 区间位置，条件判断该位置是否可以放皇后，如果可以，将该位置的坐标添加到 pathpathpath 保存起来，进入下一层。此处递归执行完毕，在此处回溯

条件判断该位置

这个条件是什么，代码中isCheckisCheckisCheck 该如何实现？

• 不在同一行
• 不在同一列
• 不在同一个斜对角线上

现在已经有的条件 pathpathpath 存放之前的皇后位置，当前层要放皇后的位置iii

• 不在同一行 : 这个条件不用看，因为递归的时候按层递归，一定不会出现在同一层
• 不在同一列 :这个条件也简单，只要 iii 不与 pathpathpath 数组任意元素相等即可,这点不懂的可以看看上文中 pathpathpath 定义
• 不在同一个斜对角线上，分类讨论，在 45045^0450 斜线上或者在 1350135^01350斜线上

x\y	0	1	2	3
0	0,0	0,1	0,2	0,3
1	1,0	1,1	1,2	1,3
2	2,0	2,1	2,2	2,3
3	3,0	3,1	3,2	3,3

看一下上面的表，两个红色对角线上的坐标有什么规律？

• 在 45045^0450 斜线上，[0,1],[1,0][0,1],[1,0][0,1],[1,0]坐标点上，纵横坐标之和相同
• 在 1350135^01350 斜线上，[0,2],[1,3][0,2],[1,3][0,2],[1,3]坐标点上，纵横坐标之差相同

所以根据上述思路可以写出isCheckisCheckisCheck 条件函数

function isCheck(select, idx) {
    // select 这是一个数组，数组下标表示层，数组元素表示下标层位置
    const len = select.length;
    // len这里表示第几层，因为如果皇后放在这里，这就应该就是select的最后一个元素
    for (let i = 0; i < len; i++) {
      const x = select[i];
      const y = i;

      // 皇后与另一位皇后在y坐标上冲突
      if (idx === x) return false;
      // 这个皇后与45度斜线上的皇后冲突了
      if (y + x === len + idx) return false;
      // 这个皇后与135度斜线上的皇后冲突了
      if (y - x === len - idx) return false;

      // 合并上述三个if
      //if (idx === x || x + y === len + idx || y - x === len - idx) return false;
    }
    return true;
  }

最后将符合条件的换后放置在数组中

 if (idx === n) {
      // 将数据放入
  const array = [];
  for (let i = 0; i < n; i++) {
    const k = path[i];
    line[k] = 'Q';
    array.push(line.join(''));
    line[k] = '.';
  }
  result.push(array);
  return;
}

根据上述思路编辑下面代码

完整代码如下

var solveNQueens = function (n) {
  let result = [];
  const line = Array(n).fill('.');
  dfs(0, []);

  return result;
  function dfs(idx, path) {
    if (idx === n) {
      // 将数据放入
      const array = [];
      for (let i = 0; i < n; i++) {
        const k = path[i];
        line[k] = 'Q';
        array.push(line.join(''));
        line[k] = '.';
      }
      result.push(array);
      return;
    }
    // idx表示第几层，此处的for循环，为了找到这一层什么地方可以放皇后
    for (let i = 0; i < n; i++) {
      // 这里可以放皇后吗？x
      if (isCheck(path, i)) {
        //可以
        path.push(i);
        dfs(idx + 1, path);
        path.pop();
      } 
    }
  }
  function isCheck(select, idx) {
    // select 这是一个数组，数组下标表示层，数组元素表示下标层位置
    const len = select.length;
    // len这里表示第几层，因为如果皇后放在这里，这就应该就是select的最后一个元素
    for (let i = 0; i < len; i++) {
      const x = select[i];
      const y = i;

      // 皇后与另一位皇后在y坐标上冲突
      if (idx === x) return false;
      // 这个皇后与45度斜线上的皇后冲突了
      if (y + x === len + idx) return false;
      // 这个皇后与135度斜线上的皇后冲突了
      if (y - x === len - idx) return false;

      // 合并上述三个if
      //if (idx === x || x + y === len + idx || y - x === len - idx) return false;
    }
    return true;
  }
};