|
| 1 | +#37. Sudoku Solver |
| 2 | + |
| 3 | +###2020-07-29 |
| 4 | + |
| 5 | +Write a program to solve a Sudoku puzzle by filling the empty cells. |
| 6 | + |
| 7 | +A sudoku solution must satisfy**all of the following rules**: |
| 8 | + |
| 9 | +1. Each of the digits`1-9` must occur exactly once in each row. |
| 10 | +2. Each of the digits`1-9` must occur exactly once in each column. |
| 11 | +3. Each of the the digits`1-9` must occur exactly once in each of the 9`3x3` sub-boxes of the grid. |
| 12 | + |
| 13 | +Empty cells are indicated by the character`'.'`. |
| 14 | + |
| 15 | + |
| 16 | +A sudoku puzzle... |
| 17 | + |
| 18 | + |
| 19 | +...and its solution numbers marked in red. |
| 20 | + |
| 21 | +**Note:** |
| 22 | + |
| 23 | +- The given board contain only digits`1-9` and the character`'.'`. |
| 24 | +- You may assume that the given Sudoku puzzle will have a single unique solution. |
| 25 | +- The given board size is always`9x9`. |
| 26 | + |
| 27 | + |
| 28 | +#Solution |
| 29 | + |
| 30 | +```swift |
| 31 | + |
| 32 | +classSolution { |
| 33 | +staticlet num: [Character]= ["1","2","3","4","5","6","7","8","9"] |
| 34 | +funcsolveSudoku(_board:inout [[Character]]) { |
| 35 | +var clo= [Set<Character>].init(repeating:Set<Character>(),count:9) |
| 36 | +var row= [Set<Character>].init(repeating:Set<Character>(),count:9) |
| 37 | +var block= [Set<Character>].init(repeating:Set<Character>(),count:9) |
| 38 | +for yin0..<9 { |
| 39 | +for xin0..<9 { |
| 40 | +let c= board[y][x] |
| 41 | + clo[y].insert(c) |
| 42 | + row[x].insert(c) |
| 43 | + block[x/3+ (y/3)*3].insert(c) |
| 44 | + } |
| 45 | + } |
| 46 | +_=fillGrid(index:0,board:&board,clo:&clo,row:&row,block:&block) |
| 47 | + } |
| 48 | + |
| 49 | + |
| 50 | +funcfillGrid(index:Int, |
| 51 | +board:inout [[Character]], |
| 52 | +clo:inout [Set<Character>], |
| 53 | +row:inout [Set<Character>], |
| 54 | +block:inout [Set<Character>])->Bool { |
| 55 | +guard index<81else { |
| 56 | +returntrue |
| 57 | + } |
| 58 | +let x= index%9 |
| 59 | +let y= index/9 |
| 60 | +if board[y][x]=="." { |
| 61 | +for cin Solution.num { |
| 62 | +if!clo[y].contains(c),!row[x].contains(c),!block[x/3+ (y/3)*3].contains(c) { |
| 63 | + board[y][x]= c |
| 64 | + clo[y].insert(c) |
| 65 | + row[x].insert(c) |
| 66 | + block[x/3+ (y/3)*3].insert(c) |
| 67 | +iffillGrid(index: index+1,board:&board,clo:&clo,row:&row,block:&block) { |
| 68 | +returntrue |
| 69 | + }else { |
| 70 | + clo[y].remove(c) |
| 71 | + row[x].remove(c) |
| 72 | + block[x/3+ (y/3)*3].remove(c) |
| 73 | + board[y][x]="." |
| 74 | + } |
| 75 | + } |
| 76 | + } |
| 77 | +returnfalse |
| 78 | + }else { |
| 79 | +returnfillGrid(index: index+1,board:&board,clo:&clo,row:&row,block:&block) |
| 80 | + } |
| 81 | + } |
| 82 | +} |
| 83 | + |
| 84 | +``` |