一天一大 lee(N 皇后)难度:困难-Day20200903

输入：4
输出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  let _result = Array.from({length:n,()=>Array(n).fill('.')}),
    tmp = [];

  dfs(tmp)

  function dfs(tmp) {
    if (tmp.length === n) {
      for (let i = 0; i < n; i++) {
        const s = Array(n).fill('.').splice(tmp[i], 1, 'Q').join('')
        _result.push(s)
      }
      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 || x - y === x - Ny || x + y === x + Ny) {
        return false
      }
    }
    return true
  }

  return _result
}