![[Swift]LeetCode37. 解数独 | Sudoku Solver,第1张](/aiimages/%5BSwift%5DLeetCode37.+%E8%A7%A3%E6%95%B0%E7%8B%AC+%7C+Sudoku+Solver.png "[Swift]LeetCode37. 解数独 | Sudoku Solver,第1张")
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-Boxes of the grID. @H_301_25@Empty cells are indicated by the character ‘.‘.
A sudoku puzzle...
...and its solution numbers marked in red.
Note:
The given board contain only digits1-9 and the character ‘.‘. You may assume that the given Sudoku puzzle will have a single unique solution. The given board size is always 9x9. 编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 @H_301_25@空白格用 ‘.‘ 表示。
一个数独。
答案被标成红色。
Note:
给定的数独序列只包含数字1-9 和字符 ‘.‘ 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的。 264ms
1 class Solution { 2 func solveSudoku(_ board: inout [[Character]]) { 3 guard board.count != 0 || board[0].count != 0 else { 4 return 5 } 6 helper(&board) 7 } 8 9 private func helper(_ board: inout [[Character]]) -> Bool {10 let m = board.count,n = board[0].count11 12 for i in 0..<m {13 for j in 0..<n {14 if board[i][j] == "." {15 for num in 1...9 {16 if isValID(board,i,j,Character(String(num))) {17 board[i][j] = Character(String(num))18 19 if helper(&board) {20 return true21 } else {22 board[i][j] = "."23 }24 }25 }26 return false27 }28 }29 }30 31 return true32 }33 34 private func isValID(_ board: [[Character]],_ i: Int,_ j: Int,_ num: Character) -> Bool {35 let m = board.count,n = board[0].count36 37 // check row38 for x in 0..<n {39 if board[i][x] == num {40 return false41 }42 }43 44 // check col45 for y in 0..<m {46 if board[y][j] == num {47 return false48 }49 }50 51 // check square52 for x in i / 3 * 3..<i / 3 * 3 + 3 {53 for y in j / 3 * 3..<j / 3 * 3 + 3 {54 if board[x][y] == num {55 return false56 }57 }58 }59 60 return true61 }62 }
328ms
1 class Solution { 2 func isValIDSudoku(_ board: inout [[Character]],row: Int,column: Int,char: Character) -> Bool { 3 for i in 0..<9 { 4 if board[i][column] == char { 5 return false 6 } 7 8 if board[row][i] == char { 9 return false10 }11 12 if board[3 * (row / 3) + i / 3][3 * (column / 3) + i % 3] == char {13 return false14 }15 }16 return true17 }18 19 func solve(_ board: inout [[Character]]) -> Bool {20 let digits: [Character] = ["1","2","3","4","5","6","7","8","9"]21 for i in 0..<9 {22 for j in 0..<9 {23 guard board[i][j] == "." else { continue }24 25 for char in digits {26 guard isValIDSudoku(&board,row: i,column: j,char: char) else { continue }27 28 board[i][j] = char29 if solve(&board) {30 return true31 } else {32 board[i][j] = "."33 }34 }35 36 return false37 }38 }39 return true40 }41 42 func solveSudoku(_ board: inout [[Character]]) {43 solve(&board)44 }45 }
460ms
1 class Solution { 2 func solveSudoku(_ board: inout [[Character]]) { 3 solve(&board) 4 } 5 6 func solve(_ board: inout [[Character]]) -> Bool{ 7 for i in 0..<9{ 8 for j in 0..<9{ 9 if board[i][j] == "."{10 for k in "123456789"{11 if valID(board,k){12 board[i][j] = k13 if solve(&board){14 return true15 }16 board[i][j] = "."17 }18 }19 return false20 }21 }22 }23 return true24 }25 26 func valID(_ board: [[Character]],_ k: Character) -> Bool{27 for m in 0..<9{28 if board[i][m] != "." && board[i][m] == k{29 return false30 }31 32 if board[m][j] != "." && board[m][j] == k{33 return false34 }35 36 var rowIndex = i / 3 * 3 + m / 337 var colindex = j / 3 * 3 + m % 338 if board[rowIndex][colindex] != "." && board[rowIndex][colindex] == k{39 return false40 }41 42 43 }44 return true45 }46 47 48 }
520ms
1 class Solution { 2 var count: Int = 0 3 func solveSudoku(_ board: inout [[Character]]) { 4 // var result = board 5 solve(row: 0,col: 0,board: &board) 6 } 7 8 func solve(row: Int,col: Int,board: inout [[Character]]) -> Bool { 9 for i in 0 ..< 9 {10 for j in 0 ..< 9 {11 if board[i][j] == "." {12 let possibilitIEs = getPossibilitIEs(row: i,col: j,board: board)13 for current in possibilitIEs {14 count += 115 board[i][j] = current16 if solve(row: i,board: &board) {17 return true18 } else {19 board[i][j] = "."20 }21 }22 return false23 }24 }25 }26 return true27 }28 29 func getPossibilitIEs(row: Int,board: [[Character]]) -> [Character] {30 var taken : [Character] = []31 for i in 0 ..< 9 {32 if board[row][i] != "." {33 taken.append(board[row][i])34 }35 }36 for i in 0 ..< 9 {37 if board[i][col] != "." {38 taken.append(board[i][col])39 }40 }41 let cubeR = (row/3)*342 let cubeC = (col/3)*343 for i in cubeR ..< cubeR + 3 {44 for j in cubeC ..< cubeC + 3 {45 if board[i][j] != "." {46 taken.append(board[i][j])47 }48 }49 }50 let all:[Character] = ["1","9"]51 var available: [Character] = []52 for each in all {53 if !taken.contains(each) {54 available.append(each)55 }56 }57 // print("row:\(row) col:\(col) available:\(available)")58 return available59 }60 }
636ms
1 class Solution { 2 func solveSudoku(_ board: inout [[Character]]) { 3 dfs(&board,0,0) 4 } 5 6 func dfs(_ board: inout [[Character]],_ x: Int,_ y: Int) -> Bool { 7 if x > 8 || y > 8 { 8 return true 9 }10 11 if board[x][y] == "." {12 for k in 1...9 {13 if isValID(&board,x,y,Character.init("\(k)")) {14 board[x][y] = Character.init("\(k)")15 var nextX = x16 var nextY = y + 117 if nextY == 9 {18 nextY = 019 nextX += 120 }21 if dfs(&board,nextX,nextY) {22 return true23 }24 board[x][y] = "."25 }26 }27 return false28 } else {29 var nextX = x30 var nextY = y + 131 if nextY == 9 {32 nextY = 033 nextX += 134 }35 return dfs(&board,nextY)36 }37 }38 39 func isValID(_ board: inout [[Character]],_ x: Int,_ y: Int,_ k: Character) -> Bool {40 for i in 0..<9 {41 if board[i][y] == k || board[x][i] == k {42 return false43 }44 }45 46 for i in 0..<3 {47 for j in 0..<3 {48 if board[3*(x/3)+i][3*(y/3)+j] == k {49 return false50 }51 }52 }53 return true54 }55 }
668ms
1 class Solution { 2 3 func solveSudoku(_ board: inout [[Character]]) { 4 5 solveSudoku2(&board) 6 } 7 8 func solveSudoku2(_ board: inout [[Character]]) -> Bool { 9 for i in 0 ..< board.count {10 for j in 0 ..< board[0].count {11 if board[i][j] == "." {12 13 14 for n in ["1","9"] {15 var tempBoard = board16 if canPlace(board,Character(n),j) {17 tempBoard[i][j] = Character(n)18 19 if isSolved(tempBoard) {20 board = tempBoard21 return true22 } else {23 if solveSudoku2(&tempBoard) {24 board = tempBoard25 return true26 }27 }28 }29 }30 31 return false32 }33 }34 }35 36 return true37 }38 39 40 func canPlace(_ board: [[Character]],_ ch: Character,_ j: Int) -> Bool {41 if board[i].contains(ch) {42 return false43 }44 45 for ii in 0 ..< board.count {46 if board[ii][j] == ch {47 return false48 }49 }50 51 var iMax = 352 53 if i <= 2 {54 iMax = 355 } else if i <= 5 {56 iMax = 657 } else {58 iMax = 959 }60 61 var jMax = 362 63 if j <= 2 {64 jMax = 365 } else if j <= 5 {66 jMax = 667 } else {68 jMax = 969 }70 71 for ii in iMax - 3 ..< iMax {72 for jj in jMax - 3 ..< jMax {73 if board[ii][jj] == ch {74 return false75 }76 }77 }78 79 return true80 }81 82 func isSolved(_ board: [[Character]]) -> Bool {83 for i in 0 ..< board.count {84 for j in 0 ..< board[0].count {85 if board[i][j] == "." {86 return false87 }88 }89 }90 91 return true92 }93 }
692ms
1 class Solution { 2 func solveSudoku(_ board: inout [[Character]]) { 3 guard board.count != 0 || board[0].count != 0 else { 4 return 5 } 6 helper(&board) 7 } 8 9 private func helper(_ board: inout [[Character]]) -> Bool {10 let m = board.count,n = board[0].count36 37 // check row38 for x in 0..<n {39 if board[i][x] == num {40 return false41 }42 }43 44 // check col45 for y in 0..<m {46 if board[y][j] == num {47 return false48 }49 }50 51 // check square52 for x in i / 3 * 3..<i / 3 * 3 + 3 {53 for y in j / 3 * 3..<j / 3 * 3 + 3 {54 if board[x][y] == num {55 return false56 }57 }58 }59 60 return true61 }62 }总结
以上是内存溢出为你收集整理的[Swift]LeetCode37. 解数独 | Sudoku Solver全部内容，希望文章能够帮你解决[Swift]LeetCode37. 解数独 | Sudoku Solver所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）