37.解数独

解数独

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

数独的解法需 遵循如下规则：数字 1-9 在每一行只能出现一次；数字 1-9 在每一列只能出现一次；数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 ‘.’ 表示。

提示：

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

解析

经典回溯法，逐个空格尝试填入 1-9，不满足则回溯。

/**
 * @param {character[][]} board
 * @return {void}
 */
var solveSudoku = function (board) {
  function isValid(board, row, col, num) {
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === num) return false;
      if (board[i][col] === num) return false;
      const r = Math.floor(row / 3) * 3 + Math.floor(i / 3);
      const c = Math.floor(col / 3) * 3 + (i % 3);
      if (board[r][c] === num) return false;
    }
    return true;
  }

  function solve(board) {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] !== ".") continue;
        for (let num = 1; num <= 9; num++) {
          const ch = String(num);
          if (isValid(board, i, j, ch)) {
            board[i][j] = ch;
            if (solve(board)) return true;
            board[i][j] = ".";
          }
        }
        return false; // 1-9 都不行，需要回溯
      }
    }
    return true; // 所有格子都填完了
  }

  solve(board);
};

回溯的关键：遇到空格就尝试 1-9，验证合法性后递归继续，所有数字都不行就回溯。