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