[37] 解数独

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

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

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

Note:

给定的数独序列只包含数字 1-9 和字符 '.' 。

你可以假设给定的数独只有唯一解。

给定数独永远是 9x9 形式的。

数独问题，每一个格子都有1-9可以选，那最暴力的方法就是，对每一个格子都从1-9开始试，知道试出一个解为止。

之后我们再确定递归顺序，我们可以以行遍历，即从左到右，从上到下开始依次填空。

那么当遍历到一列结尾时，下一个遍历点是下一行的第一个格子；

当遍历到行越界时，说明整个格子已经被填完，找到了一个解，返回；

当格子中已经有预设的值时，跳过该格子，从下一个格子开始继续遍历；

那么，如何判断当前格子能填入某数字呢？很简单，判断行、列、九宫格内没有要填入的相同数字即为合法。

之后，就是回溯问题的普遍思路了：做选择、递归、取消选择。

function solveSudoku(board: string[][]): void {
  // board 为正方形，长宽相等
  const size = board.length;
  backtrack(0, 0);

  function backtrack(row: number, col: number): boolean {
    // 如果递归到行越界，说明已经把图遍历完成了，找到了一组完全可行的解
    if (row === size) return true;

    // 如果递归到某列结尾，将进入下一行的开头继续递归
    if (col === size) return backtrack(row + 1, 0);

    // 若此处已经有填入值，则跳过去找下一个空值点
    if (board[row][col] !== '.') {
      return backtrack(row, col + 1);
    }

    for (let i = 1; i <= 9; i++) {
      // 看此处是否满足数独条件，不满足直接跳过
      if (!isValid(row, col, String(i))) continue;

      // 做选择
      board[row][col] = String(i);
      // 递归
      const flag = backtrack(row, col + 1);
      // 发现一个解，剩余情况全部剪枝
      if (flag) return true;
      // 取消选择
      board[row][col] = '.';
    }
    return false;
  }

  function isValid(row: number, col: number, ch: string) {
    for (let i = 0; i < size; i++) {
      // 横行不能有相同字符
      if (board[row][i] === ch) return false;
      // 竖行不能有相同字符
      if (board[i][col] === ch) return false;
    }
    // 九宫格不能有相同字符
    const rowStart = Math.floor(row / 3) * 3;
    const colStart = Math.floor(col / 3) * 3;
    for (let i = rowStart; i < rowStart + 3; i++) {
      for (let j = colStart; j < colStart + 3; j++) {
        if (board[i][j] === ch) return false;
      }
    }
    return true;
  }
}