解数独-37

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

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

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

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sudoku-solver
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

又是一道 hard 难度的题，我感觉这题整体的思路不难找，但是要写很多代码，抽了几个函数以后代码量会少一点。

其实思路和 N 皇后问题类似，都是在每次递归求解下一项的时候（在这个问题里是求解下一个待填充的格子）需要保证以下几点：

当前行没有出现过这个数字。
当前列没有出现过这个数字。
当前所属的九宫格中没有出现过这个数字。

前置

首先对整个二维数组进行一次全面扫描，确立以下状态，用几个变量记录这些某个数字是否出现的状态：

rows 一个二维数组长度为 9，记录每一行中某个数字的出现状态，比如 rows[0][1] 代表第 0 行中是否出现过数字 1。
columns 一个二维数组长度为 9，记录每一列中某个数字的出现状态，比如 columns[0][1] 代表第 0 列中是否出现过数字 1。
grids 一个二维数组长度为 3，记录每个九宫格中某个数字的出现状态，比如 grids[0][1] 代表第 0 个九宫格中是否出现过数字 1。

grids 的分布如图所示：

每个数字分别代表 x, y，比如 21 代表 grids 中的 grids[1][2]，并且这个 grids[1][2] 的值还是一个数组，这个数组的第 i 项就代表 i 这个数字是否在这个九宫格中出现过。比如 grids[1][2][5] 代表 5 这个数字是否在 12 这个九宫格中出现过。

再用 pending 数组用来记录在第一次扫描中遇到的值为.的格子的坐标，作为待处理的坐标集合。

解题

首先对二维数组做一次扫描，确立上述的状态变量。

然后定义一个 helper 递归函数，整个函数只需要接受一个参数 startPendingIndex 代表当前在处理的是第几个 pending 队列中的坐标。

在每次递归的时候，都从 1 ~ 9 循环选取一个值，判断当前的值符合前面的三个条件，然后尝试选取该值并记录在 行、列、九宫格 中，递归进入下一个 pendingIndex，如果不满足条件的话，函数会回溯到当前位置，那么此时就把 行、列、九宫格 中记录的当前值的状态清空掉，继续循环。

代码

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
let solveSudoku = function (board) {
  let rows = initTwoDimensionalArray(9)
  let columns = initTwoDimensionalArray(9)
  let grids = initTwoDimensionalArray(3)

  // 待处理下标队列 第一次扫描的时候记录下来
  let pending = []

  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      let cell = board[y][x]
      if (cell === ".") {
        // 待填充的数独格子 记录在队列中
        pending.push([x, y])
        continue
      }
      // 记录下当前下标
      recordCell(x, y, cell)
    }
  }

  let helper = (startPendingIndex) => {
    if (startPendingIndex === pending.length) {
      return true
    }

    let [x, y] = pending[startPendingIndex]

    for (let i = 1; i <= 9; i++) {
      let cur = i.toString()
      if (isValid(x, y, cur)) {
        board[y][x] = cur
        recordCell(x, y, cur)
        if (helper(startPendingIndex + 1)) {
          return true
        } else {
          board[y][x] = "."
          restoreCell(x, y, cur)
        }
      }
    }
  }

  helper(0)

  function recordCell(x, y, cell) {
    rows[y][cell] = true
    columns[x][cell] = true
    let [gridX, gridY] = findGridIndex(x, y)
    if (!grids[gridY][gridX]) {
      grids[gridY][gridX] = new Map()
    }
    grids[gridY][gridX].set(cell, true)
  }

  function restoreCell(x, y, cell) {
    rows[y][cell] = false
    columns[x][cell] = false
    let [gridX, gridY] = findGridIndex(x, y)
    grids[gridY][gridX].set(cell, false)
  }

  function isValid(x, y, cell) {
    let isYConflict = rows[y][cell]
    let isXConflict = columns[x][cell]
    let [gridX, gridY] = findGridIndex(x, y)
    let grid = grids[gridY][gridX]
    let isGridConflict = grid && grid.get(cell)
    return !isYConflict && !isXConflict && !isGridConflict
  }
}

function initTwoDimensionalArray(length) {
  let ret = []
  for (let i = 0; i < length; i++) {
    ret.push([])
  }
  return ret
}

function findGridIndex(x, y) {
  return [Math.floor(x / 3), Math.floor(y / 3)]
}