37-SudokuSolver.md

解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

思路： 解数独是一个经典的问题，它要求找到一个满足特定规则的数字填充方案。数独是一个 9x9 的网格，其中部分格子预先填有数字，而其他格子是空白的，通常用 '.' 表示。解决数独的算法需要满足以下条件：

每一行的数字 1-9 只能出现一次。 每一列的数字 1-9 只能出现一次。 每一个 3x3 的子网格（宫）内的数字 1-9 只能出现一次。

解决数独问题的一种方法是使用深度优先搜索（DFS）结合递归回溯策略。步骤如下：

1. 初始化：创建行、列和宫的数据结构来跟踪已经使用的数字。
2. DFS 搜索：从左上角开始，逐个单元格进行搜索。
3. 找到空白单元格：当遇到空白单元格时，尝试填充所有可能的数字（1-9）。
4. 检查有效性：对于尝试填充的每个数字，检查它在同一行、列和宫中是否唯一。
5. 递归回溯：如果当前数字有效，则递归地尝试填充下一个单元格。如果导致矛盾，则回溯，尝试下一个数字。
6. 重复过程：继续这个过程直到找到解决方案或回溯到起点。

时间复杂度是 O(9^N)，其中 N 是数独中空白单元格的数量。这是因为最坏的情况下，每个空白单元格都需要尝试 9 次。 空间复杂度是 O(1)，因为我们仅使用了额外的一行、一列和一个宫的布尔数组，其大小与数独的大小无关。

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
const solveSudoku = board => {
  let row = new Array(9),
    col = new Array(9),
    cell = new Array(9);
  let i, j;
  for (i = 0; i < 9; ++i) {
    row[i] = new Array(9);
    col[i] = new Array(9);
    cell[i] = new Array(9);
  }

  for (i = 0; i < 9; ++i) {
    for (j = 0; j < 9; ++j) {
      if (board[i][j] === '.') {
        continue;
      }
      let temp = +board[i][j] - 1;
      row[i][temp] = col[temp][j] = cell[~~(j / 3) + ~~(i / 3) * 3][temp] = true;
    }
  }

  const dfs = (d) => {
    if (d >= 81) {
      return true;
    }
    let i = ~~(d / 9),
      j = d % 9;
    if (board[i][j] !== '.') {
      return dfs(d + 1);
    }

    for (let k = 0; k < 9; ++k) {
      if (!(row[i][k] || col[k][j] || cell[~~(j / 3) + ~~(i / 3) * 3][k])) {
        board[i][j] = String(k + 1);
        row[i][k] = col[k][j] = cell[~~(j / 3) + ~~(i / 3) * 3][k] = true;
        if (dfs(d + 1)) {
          return true;
        }
        board[i][j] = '.';
        row[i][k] = col[k][j] = cell[~~(j / 3) + ~~(i / 3) * 3][k] = false;
      }
    }

    return false;
  };

  dfs(0);
};