递归搜索

// 8皇后问题
function queen (n, decisions = []) {
  if (decisions.length === n) {
    return [decisions]
  }
  let r = []
  const start = decisions[decisions.length - 1] || -1
  for (let i = start + 1; i < n * n; i++) {
    if (decisions.indexOf(i) === -1) {
      // 进一步优化，先判断x，y轴的都符合条件，在开启递归
      if (decisions.every(j => compatible(j, i, n))) {
        r = r.concat(queen(n, decisions.concat(i)))
      }
    }
  }
  return r
}
function compatible (p, q, n) {
  const [x1, y1] = [~~(p / n), p % n]
  const [x2, y2] = [~~(q / n), q % n]
  return x1 !== x2 && y1 !== y2 && Math.abs(x1 - x2) !== Math.abs(y1 - y2)
}
// function is_goal (n, decisions) {
//   for (let i = 0; i < n; i++) {
//     for (let j = i + 1; j < n; j++) {
//       if (i === j) { continue }
//       const p = decisions[i]
//       const q = decisions[j]
//       if (!compatible(p, q, n)) {
//         return false
//       }
//     }
//   }
//   return true
// }
console.log(queen(8));

深度遍历

深度遍历就是指，优先子集遍历，这样的话，就是栈结构，先入后出

也就是说程序的递归其实，就是栈调用的顺序，有时候就会报内存不足，栈溢出的错误

广度优先搜索