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

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

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

思路

  1. 任意一个空白位置的可选值受其相关已填数字的约束
  2. 维护将空白格的对应的「可选值」列表，根据可选值数量排序
  3. 若某个空白格可选值只有 1 个，则直接将其填充，并对其相关的空白格可选值更新
  4. 若空白格最少的可选值都超过一个，则尝试填充继续求解，无解则回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
var solveSudoku = function (board) {
  const VALS = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
  const findAnswer = (board) => {
    const rowMarked = VALS.map((_) => {
      return {}
    })
    const columnMarked = VALS.map((_) => {
      return {}
    })
    const gridMarked = VALS.map((_) => {
      return {}
    })
    for (let i = 0; i < 9; ++i) {
      for (let j = 0; j < 9; ++j) {
        if (board[i][j] !== '.') {
          if (rowMarked[i][board[i][j]]) {
            return false
          }
          rowMarked[i][board[i][j]] = true
        }
        if (board[j][i] !== '.') {
          if (columnMarked[i][board[j][i]]) {
            return false
          }
          columnMarked[i][board[j][i]] = true
        }
        const gridI = Math.floor(i / 3) * 3 + Math.floor(j / 3)
        const gridJ = (i % 3) * 3 + (j % 3)
        if (board[gridI][gridJ] !== '.') {
          if (gridMarked[i][board[gridI][gridJ]]) {
            return false
          }
          gridMarked[i][board[gridI][gridJ]] = true
        }
      }
    }
    const todoItems = []
    for (let i = 0; i < 9; ++i) {
      for (let j = 0; j < 9; ++j) {
        if (board[i][j] === '.') {
          todoItems.push({
            i: i,
            j: j,
            vals: VALS.filter(
              (val) =>
                !rowMarked[i][val] &&
                !columnMarked[j][val] &&
                !gridMarked[Math.floor(i / 3) * 3 + Math.floor(j / 3)][val]
            ),
          })
        }
      }
    }
    if (todoItems.length === 0) {
      return true
    }
    todoItems.sort((item1, item2) => item2.vals.length - item1.vals.length)
    if (todoItems[todoItems.length - 1].vals.length === 0) {
      return false
    }
    const exactFill = todoItems[todoItems.length - 1].vals.length === 1
    if (exactFill) {
      while (todoItems.length > 0 && todoItems[todoItems.length - 1].vals.length === 1) {
        const todoItem = todoItems.pop()
        board[todoItem.i][todoItem.j] = todoItem.vals[0]
      }
      return findAnswer(board)
    }
    const todoItem = todoItems.pop()
    for (const val of todoItem.vals) {
      const newBoard = JSON.parse(JSON.stringify(board))
      newBoard[todoItem.i][todoItem.j] = val
      if (findAnswer(newBoard)) {
        board[todoItem.i][todoItem.j] = val
        todoItems.forEach((item) => {
          board[item.i][item.j] = newBoard[item.i][item.j]
        })
        return true
      }
    }
    return false
  }
  findAnswer(board)
}