n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
翻一下题目的意思：
出入 N，要在长宽为 N 的矩阵中放入 N 个 Q，且每个 Q 不能处在同行同列也不能处在对角线上
思路
第一下看示例的输出其实有点不符合直觉，第一反应应该是从第一位开始放 Q：
Q.....Q.........[0,2] -> [ [0,0],[1,2] ]
这个时候就知道为什么输出不是从开始就放 Q，因为如果在某些位置放置了 Q，后续可能不能放下 n 个 Q
那么此时就有两种方式开启行的枚举：
回溯到开始从新枚举就当前位回溯开始新的枚举如果采用第 1 种方式回溯，可能在当前起始填充位下存在正确的解法，直接切换了起始位就会造成解法丢失，则采用的第 2 种方法回溯
回溯第二个 Q，给其重新放置位置
Q......Q.Q......[0,3,1] -> [ [0,0],[1,3],[2,1] ]
还是放置不下 4 个 Q，说明枚举了第二个 Q 的位置还是不能满足条件，次数枚举了 Q 起始位置为[0,0]的组合，确定起始位置为[0,0]不存在正解
继续向后枚举起始位置
.Q.....QQ.....Q.[1,3,0,2] -> [ [0,1],[1,3],[2,0],[3,2] ]
得到一种解法，记录下拉继续枚举…
/** * @param {number} n * @return {string[][]} */ var solveNQueens = function(n) { let _result = [], tmp = [] dfs(tmp) function dfs(tmp) { if (tmp.length === n) { let item = [] for (let i = 0; i < n; i++) { const s = Array(n).fill('.') s.splice(tmp[i], 1, 'Q') item.push(s.join('')) } _result.push(item) return } for (let i = 0; i < n; i++) { if (isValid(tmp, i)) { // 遇到满足“不能相互攻击”的点就先占着后继续安放下一个Q tmp.push(i) dfs(tmp) // 回溯已经安放的Q tmp.pop() } } } // 判断新的位置是否满足“不能相互攻击” function isValid(tmp, Ny) { // 传入校验的坐标：[Nx,Ny] let Nx = tmp.length for (let x = 0; x < Nx; x++) { let y = tmp[x] // 不同列，因为所有做行一定不同行，不在斜对角上[注：斜对角判断] if (y === Ny || Nx - y === x - Ny || Nx + y === x + Ny) { return false } } return true } return _result }注：斜对角判断
a*b*A*c*d元素 A ->[1,1]的斜对角有：
a->[0,0] Nx+y === x+Ny -> 1+0 == 0+1b->[2,0] Nx-y === x-Ny -> 2-1 == 1-0c->[0,2] Nx-y === x-Ny -> 1-0 == 2-1d->[2,2] Nx+y === x+Ny -> 1+2 == 2+1坐标[Nx,Ny]的斜对角坐标[x,y]都满足 Nx-y=== x-Ny 或者 Nx+y===x+Ny
博客: 小书童博客
每天的每日一题，写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公号: 坑人的小书童
