面试题 08.12. 八皇后

注意： 主/副对角线
image.png

  1. var solveNQueens = function(n) {
  2.     let res = [];
  3.     let prev = [];
  4.     dfs(n, 0, prev, res)
  5.     // console.log(res)
  6.     // return res;
  7.     let queens = [];
  8.     for (let i=0; i < res.length; i++) {
  9.         let queen = generate(n, res[i])
  10.         queens.push(queen)
  11.     }
  12.     return queens
  13. };
  15. function dfs(n, row, prev, res) {
  16.     if (row == n) {
  17.         res.push(prev.slice());
  18.         return;
  19.     }
  20.     for (let col = 0; col < n; col++) {
  21.         if (verified(n, prev, col)) {
  22.             prev.push(col);
  23.             dfs(n, row+1, prev, res);
  24.             // 回溯
  25.             prev.pop();
  26.         }
  27.     }
  28. }
  30. function verified(n, path, col) {
  31.     // 行: 放置在prev.length
  32.     // 列
  33.     // 主对角线
  34.     // 副对角线
  35.     for (let row=0; row<path.length; row++) {
  36.         let diff = Math.abs(path[row] - col); // 当前行所在列与目标列的距离
  37.         if (diff == 0 || diff == path.length - row) return false;
  38.         //     不在一列         不在主副线上： 与目标列的距离不等于到目标行的巨鳖
  39.     }
  40.     return true;
  41. }
  43. function generate(n, path) {
  44.     let queen = Array.from({length: n}, (v, i) => {
  45.       let col = new Array(n).fill('.')
  46.       let index = path[i];
  47.       col[index] = 'Q'
  48.       return col.join('');
  49.     })
  50.     return queen
  51. }

面试题 08.13. 堆箱子

参考：

https://juejin.cn/post/6844903589652103181