@@ -174,8 +174,8 @@ class Solution {
174174
175175```
176176
177- ```
178177对于测试数组
178+ ```
179179[["5","3",".",".","7",".",".",".","."],
180180["6",".",".","1","9","5",".",".","."],
181181[".","9","8",".",".",".",".","6","."],
@@ -185,8 +185,80 @@ class Solution {
185185[".","6",".",".",".",".","2","8","."],
186186[".",".",".","4","1","9",".",".","5"],
187187[".",".",".",".","8",".",".","7","9"]]
188+ ```
189+ 顺序遍历调用` fillGrid ` 4209次，按权重遍历调用` fillGrid ` 103次
190+
188191
189- 顺序遍历调用fillGrid 4209次，按权重遍历调用fillGrid 103次
190192
193+
194+ 对权重遍历就行优化，提前得到每个空位有可能的值进行遍历，由于对集合进行遍历所以时间不稳定。最优时间可能在排名在100%
195+ ```
196+ Runtime: 36 ms, faster than 100.00% of Swift online submissions for Sudoku Solver.
197+ Memory Usage: 22.5 MB, less than 50.00% of Swift online submissions for Sudoku Solver.
191198```
192199
200+ ```
201+ class Solution {
202+
203+ static let num: Set<Character> = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
204+
205+ func solveSudoku(_ board: inout [[Character]]) {
206+ var clo = [Set<Character>].init(repeating: Set<Character>(), count: 9)
207+ var row = [Set<Character>].init(repeating: Set<Character>(), count: 9)
208+ var block = [Set<Character>].init(repeating: Set<Character>(), count: 9)
209+ var points = [(p: (x: Int, y: Int), c: Set<Character>)]()
210+ for y in 0..<9 {
211+ for x in 0..<9 {
212+ let c = board[y][x]
213+ guard c != "." else {
214+ points.append((p: (x: x, y: y), c: Set<Character>()))
215+ continue
216+ }
217+ clo[y].insert(c)
218+ row[x].insert(c)
219+ block[x/3 + (y/3) * 3].insert(c)
220+ }
221+ }
222+ for i in 0..<points.count {
223+ let (x, y) = points[i].p
224+ points[i].c = Solution.num.subtracting(clo[y].union(row[x]).union(block[x/3 + (y/3) * 3]))
225+ }
226+ points.sort(by: { $0.c.count < $1.c.count })
227+ _ = fillGrid(index: 0,
228+ point: points,
229+ board: &board,
230+ clo: &clo,
231+ row: &row,
232+ block: &block)
233+ }
234+
235+
236+ func fillGrid(index: Int,
237+ point: [(p: (x: Int, y: Int), c: Set<Character>)],
238+ board: inout [[Character]],
239+ clo: inout [Set<Character>],
240+ row: inout [Set<Character>],
241+ block: inout [Set<Character>]) -> Bool {
242+ if index == point.count {
243+ return true
244+ }
245+ let (x, y) = point[index].p
246+
247+ for c in point[index].c.subtracting(clo[y].union(row[x]).union(block[x/3 + (y/3) * 3])) {
248+ board[y][x] = c
249+ clo[y].insert(c)
250+ row[x].insert(c)
251+ block[x/3 + (y/3) * 3].insert(c)
252+ if fillGrid(index: index + 1, point: point, board: &board, clo: &clo, row: &row, block: &block) {
253+ return true
254+ } else {
255+ clo[y].remove(c)
256+ row[x].remove(c)
257+ block[x/3 + (y/3) * 3].remove(c)
258+ board[y][x] = "."
259+ }
260+ }
261+ return false
262+ }
263+ }
264+ ```