原理简介

回溯法，又名试探法，是一种优选搜索算法，可以理解为试探性搜索算法。在搜索到某一步的时候，如果发现不能满足条件，那么就退回到上一步，在上一步重新选择。

回溯法是以深度优先方式来搜索问题的解，也就是里面的每一步可以理解为一个结点，这些步骤串起来就是一棵树，也就是解空间树。比如第一步只有 1 种做法，第二步有 4 种做法，那么第二步选择一种尝试之后，如果匹配，会假设当前步骤没有问题，继续往第 3 步深入探索，而不是先尝试第二步的其他选择。

当搜索解空间树中的任何一个结点的时候，判断该结点是不是包含问题的解。

  • 如果不包含，那么就把当前的结点以及剩下的节点步骤全部抛弃（也称为剪枝），然后往上一层的结点回溯，也就是退回上一步重新选择（之前的选择走不通）。
  • 如果包含，说明当前结点是可能获取到解的，继续进入下一层子树进行深度优先搜索。

8皇后问题

问题描述

八皇后问题，是一个著名的学习回溯法的案例，时间退回到 1848 年，国际西洋棋棋手马克斯·贝瑟尔提出了这样的一个问题：在 8 × 8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。

扩展成N皇后

求解思路

为了方便解析，我们将问题的规模缩小，变成四皇后问题，也就是在 4 x 4 的国际象棋上摆放 4 个皇后，下面是其中一种解法：

暴力的解法，自然是遍历所有的摆放方式，再判断每一种摆放方式是否符合规则。而回溯法则是不断试探，具体的做法如下：

  • 当我们选择第一个皇后的位置时，假设在第一行摆放，那么就有四种摆放的方法，我们需要遍历每一种摆放，首先肯定是选择第一个位置摆放。
  • 选中第一个皇后的位置之后，与其在同一行同一列同斜线的位置都不能选择，那么第二个皇后只能放到未被第一个皇后（同一行、同一列或同一斜线）的位置，这样的位置或许有多个，我们需要遍历每一个符合条件的，假设选择第一个符合的位置进行摆放，继续第三个皇后的摆放。
  • 摆放第三个皇后的时候，不能在第一个和第二个的（同一行、同一列或同一斜线）范围内，以此类推，再去挑选第四个。如果第四个不符合条件，重新挑选第四个皇后的位置，如果所有的位置都尝试过，则退回上一步，重新挑选第三个皇后的位置，如果第三个皇后还是没有符合的位置则再次回退至选择第二个皇后的位置，若第二个皇后也没有更多的选择则回退到第一个皇后，重新进行位置的选择。

代码实现

const solveNQueens = (n) => {
  const board = new Array(n);
  for (let i = 0; i < n; i++) {     // 棋盘的初始化
    board[i] = new Array(n).fill('.');
  }
  const res = [];
  const isValid = (row, col) => {  
    for (let i = 0; i < row; i++) { // 之前的行
      for (let j = 0; j < n; j++) { // 所有的列
        if (board[i][j] == 'Q' &&   // 发现了皇后，并且和自己同列/对角线
          (j == col || i + j === row + col || i - j === row - col)) {
          return false;             // 不是合法的选择
        }
      }
    }
    return true;
  };
  const helper = (row) => {   // 放置当前行的皇后
    if (row == n) {           // 递归的出口，超出了最后一行
      const stringsBoard = board.slice(); // 拷贝一份board
      for (let i = 0; i < n; i++) {
        stringsBoard[i] = stringsBoard[i].join(''); // 将每一行拼成字符串
      }
      res.push(stringsBoard); // 推入res数组
      return;
    }
    for (let col = 0; col < n; col++) { // 枚举出所有选择
      if (isValid(row, col)) {          // 剪掉无效的选择
        board[row][col] = "Q";          // 作出选择，放置皇后
        helper(row + 1);                // 继续选择，往下递归
        board[row][col] = '.';          // 撤销当前选择
      }
    }
  };
  helper(0);  // 从第0行开始放置
  return res;
};