37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3 x 3 sub-boxes of the grid.

The '.' character indicates empty cells.

Input:
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"]
]

Output:
[
  ["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"]
]

Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.

It is guaranteed that the input board has only one solution.

Analyze

该题有一个难点: 需要明确递归的队列是啥。

1. 在这里递归队列是数独中的 . 的下标。
2. 接着根据该队列进行递归操作, 对横向、竖向、3 x 3 内的位置信息作记录。

• 若横向、纵向、3 x 3 的位置没有使用过, 则将相应位置标记为已使用(true)
• 若横向、纵向、3 x 3 的位置已经使用过, 则进入下一个递归

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
  const obj = {}
  const used = []
  for (let x = 0; x < 9; x++) {
    for (let y = 0; y < 9; y++) {
      if (!obj[`rows ${x}`]) obj[`rows ${x}`] = {}
      if (!obj[`columns ${y}`]) obj[`columns ${y}`] = {}
      const blockX = Math.floor(x / 3)
      const blockY = Math.floor(y / 3)
      if (!obj[`block ${blockX}${blockY}`]) obj[`block ${blockX}${blockY}`] = {}
      if (board[x][y] !== '.') {
        obj[`rows ${x}`][board[x][y]] = true
        obj[`columns ${y}`][board[x][y]] = true
        obj[`block ${blockX}${blockY}`][board[x][y]] = true
      } else {
        used.push({
          x,
          y
        })
      }
    }
  }

  dfs(board, 0, obj, used)

  return board
};

var dfs = function(board, pos, obj, used) {
  if (pos === used.length) {
    for (let m = 0; m < 9; m++) {
      for (let n = 1; n <= 9; n++) {
        if (typeof obj[`rows ${m}`][n] === 'number') {
          board[m][obj[`rows ${m}`][n]] = String(n)
        }
      }
    }
    return
  }
  const { x, y } = used[pos]
  // data source
  for (let i = 1; i <= 9; i++) {
    const blockX = Math.floor(x / 3)
    const blockY = Math.floor(y / 3)
    if (
      (obj[`rows ${x}`][String(i)] === undefined || obj[`rows ${x}`][String(i)] === false)
      && !obj[`columns ${y}`][String(i)]
      && !obj[`block ${blockX}${blockY}`][String(i)]
    ) {
      obj[`rows ${x}`][String(i)] = y
      obj[`columns ${y}`][String(i)] = true
      obj[`block ${blockX}${blockY}`][String(i)] = true
      dfs(board, pos + 1, obj, used)
      obj[`rows ${x}`][String(i)] = false
      obj[`columns ${y}`][String(i)] = false
      obj[`block ${blockX}${blockY}`][String(i)] = false
    }
  }
}