### 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    }  }}