棋盘与网格搜索

N 皇后如何用三个约束数组剪枝？

• 决策: 每一行放一个皇后, 逐行放置, 行冲突天然消除;
• 列冲突: 布尔数组 cols[col];
• 主对角线冲突: 同一主对角线上 row - col 恒定, 范围为 $[-n+1, n-1]$, 平移后索引为 row - col + n - 1;
• 副对角线冲突: 同一副对角线上 row + col 恒定, 范围为 $[0, 2n-2]$;
• 终止: 行号到达 $n$ 时说明每行都放好, 记录结果;

const solveNQueens = (n) => {
  const res = [];
  const state = Array.from({ length: n }, () => Array(n).fill("."));
  const cols = Array(n).fill(false);
  const diags1 = Array(2 * n - 1).fill(false);
  const diags2 = Array(2 * n - 1).fill(false);

  const dfs = (row) => {
    if (row >= n) {
      res.push(state.map((line) => line.join("")));
      return;
    }
    for (let col = 0; col < n; col++) {
      const diag1 = row - col + n - 1;
      const diag2 = row + col;
      if (cols[col] || diags1[diag1] || diags2[diag2]) continue;
      state[row][col] = "Q";
      cols[col] = diags1[diag1] = diags2[diag2] = true;
      dfs(row + 1);
      state[row][col] = ".";
      cols[col] = diags1[diag1] = diags2[diag2] = false;
    }
  };

  dfs(0);
  return res;
};

• 复杂度: 时间 $O(n!)$, 空间 $O(n^2)$;
• 要点: 三个布尔数组把"逐格检查冲突"的 $O(n)$ 判定降为 $O(1)$;

解数独如何回溯求解？

• 决策: 对每个空格依次尝试 1 到 9;
• 合法性: 同行、同列、同 3×3 宫内不重复;
• 剪枝: 全部候选都失败时立即返回 false, 让上层换一个数字;
• 终止: 遍历完棋盘没有空格, 说明已找到唯一解;
• 与 N 皇后的区别: 数独只需一个可行解, 找到即整体提前返回, 不做全量枚举;

const solveSudoku = (board) => {
  const isValid = (row, col, val) => {
    for (let i = 0; i < 9; i++) {
      if (val === board[row][i] || val === board[i][col]) return false;
    }
    const startRow = Math.floor(row / 3) * 3;
    const startCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++)
      for (let j = 0; j < 3; j++) if (val === board[startRow + i][startCol + j]) return false;
    return true;
  };

  const backtrack = () => {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] !== ".") continue;
        for (let k = 1; k < 10; k++) {
          if (!isValid(i, j, String(k))) continue;
          board[i][j] = String(k);
          if (backtrack()) return true;
          board[i][j] = ".";
        }
        return false; // 1-9 全部无效
      }
    }
    return true;
  };

  backtrack();
};

• 复杂度: 时间 $O(9^m)$ ($m$ 为空格数), 空间 $O(9^2)$;

单词搜索如何回溯求解？

• 决策: 从当前格向上下左右四个方向移动;
• 状态: visited 标记当前路径上已使用的格子;
• 剪枝: 越界、已访问、字符不匹配都直接跳过;
• 终止: 匹配到单词最后一个字符时返回真;
• 回退: 从某个格子出发失败后, 必须把 visited[row][col] 复位, 供其他起点复用;

const exist = (board, word) => {
  const rows = board.length;
  const cols = board[0].length;
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));

  const backtrack = (row, col, index) => {
    if (word[index] !== board[row][col]) return false;
    if (index === word.length - 1) return true;
    visited[row][col] = true;
    for (const [dx, dy] of directions) {
      const nextRow = row + dy;
      const nextCol = col + dx;
      if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) continue;
      if (visited[nextRow][nextCol]) continue;
      if (backtrack(nextRow, nextCol, index + 1)) return true;
    }
    visited[row][col] = false; // 回退供其他起点复用
    return false;
  };

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) if (backtrack(i, j, 0)) return true;
  }
  return false;
};

• 复杂度: 时间 $O(mn \cdot 2^l)$ ($l$ 为单词长度), 空间 $O(mn)$;

棋盘类与网格类搜索的状态设计有何区别？

问题	状态载体	剪枝依据
N 皇后	行号 + 三个布尔数组	列与两条对角线是否占用
解数独	棋盘本身	行/列/宫是否重复
单词搜索	坐标 + visited 数组	越界、已访问、字符不匹配

• 共性: 都在"选择 → 递归 → 撤销"三步中维护增量状态, 避免每层全量重算;
• 差异: 棋盘类状态可原地修改, 网格类必须显式记录访问集合;