51. N 皇后

描述

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

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

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

提示：

1 <= n <= 9
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上
复制代码

题解

回溯法

回溯法（backtracking）是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便。
顾名思义，回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态 还原。

这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存
状态。
在具体的写法上，它与普通的深度优先搜索一样，都有 [修改当前节点状态]→[递归子节
点] 的步骤，只是多了回溯的步骤，变成了 [修改当前节点状态]→[递归子节点]→[回改当前节点
状态]。
回溯法。有两个小诀窍，一是按引用传状态，二是所有的状态修 改在递归完成后回改。
回溯法修改一般有两种情况，一种是修改最后一位输出，比如排列组合；一种是修改访问标
记，比如矩阵里搜字符串。

解析

类似于在矩阵中寻找字符串，通过修改状态矩阵来进行回溯。

从提示可以知道不同的是，每一行、列、左斜、右斜建立访问数组，来记录它们是否存在皇后。
即满足条件的结果中每一行、列左斜、右斜有且仅有一个皇后。

实现步骤为：
1、创建记录节点状态棋盘，其中 ‘ . ‘ 表示空，’ Q ‘ 表示皇后，初始化空棋盘；
2、然后，调用 backtrack()backtrack() 方法：
[修改当前节点状态]→[递归子节点]→[回改当前节点
状态]。

coding

/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
   let ans = [];
   if( n === 0) return ans;
   const board = Array.from({length: n}, ()=> Array(n).fill('.')); // 定义棋盘大小， 并且初始化棋盘
   const colum = Array.from({length: n}, ()=> false);
   backtrack(ans, board, 0, n);
   return ans;
};

const backtrack = function(ans, board, row, n) {
   if(row === n) {
       ans.push(Array2List(board));
       return
   }
   for(let col = 0; col < n; col ++) {
       if(!isValid(board, row, col, n)) continue;
       board[row][col] = 'Q'; // 修改当前节点状态
       backtrack(ans, board, row + 1, n); // 递归子节点
       board[row][col] = '.'; // 回改当前节点状态
   }
}
const isValid = function(board, row, col, n) {
   // 检查列中是否有皇后相互冲突
   for (let i = 0; i < row; i++) {
       if (board[i][col] === 'Q') return false;
   }
   // 检查左斜收否有皇后相互冲突
   for (let i = row-1, j = col+1; i >=0 && j < n; i--, j++) {
       if(board[i][j] == 'Q') return false;
   }
   // 检查左斜是否有皇后相互冲突
   for(let i = row - 1, j = col - 1; i >=0 && j >=0; i--, j--) {
       if(board[i][j] === 'Q') return false;
   }
   return true
}
const Array2List = function(board) {
   const list = [];
   board.map((item, index, arr) => {
       list.push(item.join(''));
   })
   return list;
}


复制代码