[Swift]LeetCode36. 有效的数独 | Valid Sudoku

概述Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain

Determine if a 9x9 Sudoku board is valID. Only the filled cells need to be valIDated according to the following rules:

Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-Boxes of the grID must contain the digits 1-9 without repetition.

A partially filled sudoku which is valID.

The Sudoku board Could be partially filled,where empty cells are filled with the character ‘.‘.

Example 1:

input:[  ["5","3",".","7","."],["6","1","9","5",[".","8","6",["8","3"],["4","1"],["7","2","6"],"4","5"],"9"]]Output: true

Example 2:

input:[  ["8",  ["6",  [".",  ["8",  ["4",  ["7","9"]]Output: falseExplanation: Same as Example 1,except with the 5 in the top left corner being     modifIEd to 8. Since there are two 8‘s in the top left 3x3 sub-Box,it is invalID.

Note:

A Sudoku board (partially filled) Could be valID but is not necessarily solvable. Only the filled cells need to be valIDated according to the mentioned rules. The given board contain only digits 1-9 and the character ‘.‘. The given board size is always 9x9.

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

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

示例 1:

输入:[  ["5","9"]]输出: true

示例 2:

输入:[  ["8","9"]]输出: false解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。     但由于位于左上角的 3x3 宫内有两个 8 存在,因此这个数独是无效的。

说明:

一个有效的数独（部分已被填充）不一定是可解的。 只需要根据以上规则，验证已经填入的数字是否有效即可。 给定数独序列只包含数字 1-9 和字符 ‘.‘ 。 给定数独永远是 9x9 形式的。

48ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3         var rowSet = Set<Character>() 4         var colSet = Set<Character>() 5         var cube = Set<Character>() 6          7          8         for i in 0..<9 { 9             rowSet.removeAll()10             colSet.removeAll()11             for j in 0..<9 {12                 let rowval = board[i][j]13                 let colval = board[j][i]14                 if rowval != "." {15                     if rowSet.contains(rowval) {return false}16                     rowSet.insert(rowval)17                 }18                 if colval != "." {19                     if colSet.contains(colval) {return false}20                     colSet.insert(colval)21                 }22             }23             24         }25         print("here")26         for i in 0..<3 {27             for j in 0..<3 {28                 cube.removeAll()29                 let row = i * 330                 let col = j * 331                 for x in row..<(row + 3) {32                     for y in col..<(col + 3) {33                     let val = board[x][y]34                         if val != "." {35                         if cube.contains(val) {return false}36                         cube.insert(val)37                         }38                     }39                 }  40             }41         }42         43         return true44     }45 }

52ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3         guard board.count == 9,board[0].count == 9 else { return false } 4          5         var rowSet = Set<Character>() 6         var columnSet = Set<Character>() 7         for i in 0..<board.count { 8              9             for j in 0..<board[0].count {10                 if board[i][j] != "." {11                     if !rowSet.insert(board[i][j]).inserted { return false }12                 }13                 if board[j][i] != "." {14                     if !columnSet.insert(board[j][i]).inserted { return false }15                 }16             }17             rowSet.removeAll()18             columnSet.removeAll()19         }20         21         for i in 0..<3 {22             for j in 0..<3 {23                 for m in i * 3..<i * 3 + 3 {24                     for n in j * 3..<j * 3 + 3 {25                         if board[m][n] != "." {26                             if !rowSet.insert(board[m][n]).inserted { return false }27                         }28                     }29                 }30                 rowSet.removeAll()31             }32         }33         34         return true35     }36 }

52ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3         //check row 4         for i in 0..<board.count { 5             let row = board[i] 6             var nums = [Character]() 7  8             for j in 0..<row.count { 9                 if row[j] != "." {10                     if nums.contains(row[j]) == false {11                         nums.append(row[j])12                     } else {13                         return false14                     }15                 }16             } 17         }18         19         //check col20         for i in 0..<board.count {21             var cols = [Character]()22             let row = board[i]23             for j in 0..<row.count {24                 if board[j][i] != "." {25                     if cols.contains(board[j][i]) == false {26                         cols.append(board[j][i])    27                     } else {28                         return false29                     }30                 }31             }32         }33         34         //check sub board35         for i in strIDe(from: 0,to: board.count,by: 3) {36             for j in strIDe(from: 0,by: 3) {37                 var subBoard = [Character]()38                 for n in 0..<3 {39                     for m in 0..<3 {40                          if board[i + n][j + m] != "." {41                             if subBoard.contains(board[i + n][j + m]) == false {42                                 subBoard.append(board[i + n][j + m])43                             } else {44                                 return false45                             }46                         }47                     }48                 }49             }50         }51         return true52     }53 }

56ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3         func isValID(_ board: [[Character]],_ row: Int,_ col: Int,_ c: Character) -> Bool { 4             func isExistInRow(_ board: [[Character]],_ c: Character) -> Bool { 5                 for i in 0..<board.count { 6                     if board[row][i] == c && i != col{ 7                         return true 8                     } 9                 }10                 return false11             }12             func isExistInCol(_ board: [[Character]],_ c: Character) -> Bool {13                 for i in 0..<board.count {14                     if board[i][col] == c && i != row{15                         return true16                     }17                 }18                 return false19             }20             func isExistInSmallgird(_ board: [[Character]],_ startRow: Int,_ startCol: Int,_ c: Character) -> Bool {21                 for i in 0..<3 {22                     for j in 0..<3 {23                         if board[i + startRow][j + startCol] == c && i + startRow != row && j + startCol != col {24                             return true25                         }26                     }27                 }28                 return false29             }30             let startRow = row - row % 331             let startCol = col - col % 332             return !isExistInCol(board,row,col,c) && !isExistInRow(board,c) && !isExistInSmallgird(board,startRow,startCol,c)33         }34         for i in 0..<9 {35             for j in 0..<9 {36                 if board[i][j] != Character.init(".") {37                     if isValID(board,i,j,board[i][j]) == false {38                         return false39                     }40                 }41             }42         }43         return true44     }45 }

56ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3         guard board.count > 0 && board[0].count > 0 else { 4             return false 5         } 6         let rowCount = board.count 7         let colCount = board[0].count 8         var rowFlag = Array<[Bool]>(repeating: Array<Bool>(repeating: false,count: colCount),count: rowCount) 9         var colFlag = Array<[Bool]>(repeating: Array<Bool>(repeating: false,count: rowCount)10         var cellFlag = Array<[Bool]>(repeating: Array<Bool>(repeating: false,count: rowCount)11         12         13         for i in 0..<rowCount {14             for j in 0..<colCount {15                 let num = Int(board[i][j].unicodeScalars.first!.value)16                 if num >= 49 && num <= 57 {17                     let c = num - 4918                     if rowFlag[i][c] || colFlag[c][j] || cellFlag[3 * (i / 3) + j / 3][c] {19                         return false20                     }21                     rowFlag[i][c] = true22                     colFlag[c][j] = true23                     cellFlag[3 * (i / 3) + j / 3][c] = true24                 }25                 26             }27         }28         return true29     }30 }

60ms

 1 class Solution { 2      3     enum BoardType { 4     case colon 5     case row 6     case subSquare 7 } 8      9 func isValIDSudoku(_ board: [[Character]]) -> Bool {10     11     func doesContains(index: (row: Int,col: Int),boardType: BoardType) -> Bool{12         switch boardType {13         case .colon:14             for i in index.row+1..<9 {15                 if board[index.row][index.col] == board[i][index.col] { return true }16             }17         case .row:18             let array = board[index.row][index.col + 1..<9]19             if array.contains(board[index.row][index.col]) { return true}20 21         case .subSquare:22             for squareRow in 0..<3 {23                 for squareCol in 0..<3 {24                         let x = index.row / 3 * 3 + squareRow25                         let y = index.col / 3 * 3 + squareCol26                     if board[index.row][index.col] == board[x][y] && index.row != x && index.col != y {27                         return true28                         29                     }30                 }31                32             }33             34         }35         return false36     }37     38     // check horizontal39     for row in 0..<9 {40         for col in 0..<9 {41             let character = board[row][col]42             if let number = Int(String(character)) {43                 // Check horizontal44                 if doesContains(index: (row,col),boardType: .row) { return false }45                 46                 // Check vertical47                 if doesContains(index: (row,boardType: .colon) { return false }48                 49                 // Check sub-square50                 if doesContains(index: (row,boardType: .subSquare) { return false }51             }52             53         }54     }55     56     return true57 }58 }

60ms

 1 class Solution { 2    func valID(_ board:[[Character]]) -> Bool { 3         //行 4         var lineList   = [Character]() 5         //列 6         var columnList = [Character]() 7          8         for i in 0..<9 { 9             for j in 0..<9 {10                 11               //扫描行12               var lineNum = board[i][j]13               if(!(lineNum==".")){14                    if(lineList.contains(lineNum)){15                        return false16                    }else{17                       lineList.append(lineNum)18                    }19               }  20                21             //扫描列    22             var columnNum = board[j][i]23             if(!(columnNum==".")){24                    if(columnList.contains(columnNum)){25                        return false26                    }else{27                       columnList.append(columnNum)28                    }29               } 30            }31             lineList.removeAll() 32             columnList.removeAll()33         }34         35         return true36     }37     38     func isValIDSudoku(_ board: [[Character]]) -> Bool {39                var valID = true   40                 valID = self.valID(board)41                 if(!valID){42                     return false43                 }44 45        var smallBoard = [[Character]]()46     47        //strIDe正向跳跃遍历48           for i in strIDe(from: 0,to: 9,by: 3) {49             for j in strIDe(from: 0,by: 3) {50 51                 var line0 = [board[i][j],board[i][j+1],board[i][j+2]]52                 var line1 = [board[i+1][j],board[i+1][j+1],board[i+1][j+2]]53                 var line2 = [board[i+2][j],board[i+2][j+1],board[i+2][j+2]]54                 smallBoard.append(line0)55                 smallBoard.append(line1)56                 smallBoard.append(line2)57                 58                 //检查 3*3 重复59                 var checkList = [Character]()60                 for List in smallBoard {61                     for item in List {62                        if(!(item==".")){63                             if(checkList.contains(item)){64                                  return false65                             }else{66                                 checkList.append(item)67                             }68                        }69                     }   70                 }71                 smallBoard.removeAll()72             }73        }74        return valID75    }76 }

76ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3         let boardInt = board.map({$0.map({$0 == "." ? 0 : Int(String($0))})}) 4  5         for  y in 0 ..< 9 { 6             var colmFlags = 0 7             var lineFlags = 0 8             var areaFlags = 0 9             let ay = Int(y / 3)10             let ax = Int(y % 3)11             12             for  x in 0 ..< 9 {13                 let yy = Int(x / 3)14                 let xx = Int(x % 3)15                 var m = boardInt[ay * 3 + yy][ax * 3 + xx]!16                 if m > 0 {17                     if (1 << m) & areaFlags != 0 {18                         return false19                     }20                     areaFlags |= (1 << m)21                 }22                 23                 m = boardInt[y][x]!24                 if m > 0 {25                     if (1 << m) & colmFlags != 0 {26                         return false27                     }28                     colmFlags |= (1 << m)29                 }30                 31                 m = boardInt[x][y]!32                 if m > 0 {33                     if (1 << m) & lineFlags != 0 {34                         return false35                     }36                     lineFlags |= (1 << m)37                 }38             }39         }40         return true41     }42 }

80ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3         var tempSet = Set<Character>() 4         var tempArray = Array<Character>() 5  6         var secondTempSet = Set<Character>() 7         var secondTempArray = Array<Character>() 8  9         for i in 0..<board.count {10             ///第1个条件11             tempArray = board[i].filter({ (x) -> Bool in12                 return x != "."13             })14             tempSet = Set(tempArray)15             if tempArray.count != tempSet.count {16                 return false17             }18             ///第2个条件19             for j in 0..<board.count {20                 if board[j][i] != "." {21                     secondTempArray.append(board[j][i])22                 }23             }24             secondTempSet = Set(secondTempArray)25             if secondTempArray.count != secondTempSet.count {26                 return false27              }28             secondTempSet.removeAll()29             secondTempArray.removeAll()30             ///第3个条件31             //3x3格子32             let column = (i * 3) % board.count   //列开始33             let row:Int = (Int)(i * 3 / board.count) * 3 //行开始34             for x in 0...2 {35                 secondTempArray.append(contentsOf: [board[row + x][column],board[row + x][column + 1],board[row + x][column + 2]])36             }37             secondTempArray = secondTempArray.filter({ (x) -> Bool in38                 return x != "."39             })40             secondTempSet = Set(secondTempArray)41             if secondTempArray.count != secondTempSet.count {42                 return false43             }44             secondTempSet.removeAll()45             secondTempArray.removeAll()46         }47         return true48     }49 }

196ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3         for i in 0..<9 { 4             if valIDRow(board,i) && valIDCol(board,i) && valIDBlock(board,i) {} else{ 5                 return false 6             } 7         } 8         return true 9     }10     11     func valIDCol(_ block: [[Character]],_ index: Int) -> Bool{12         var dict = [Character: Bool]()13         for i in 0..<9 {14             let abc = block[i][index] 15             if abc != "."{16                 if dict[abc] == true {17                     return false18                 }else {19                     dict[abc] = true20                 }21             }22         }23         return true24     }25     26     func valIDRow(_ block: [[Character]],_ index: Int) -> Bool{27         var dict = [Character: Bool]()28         for i in 0..<9 {29             let abc = block[index][i] 30             if abc != "."{31                 if dict[abc] == true {32                     return false33                 }else {34                     dict[abc] = true35                 }36             }37         }38         return true39     }40     41     func valIDBlock(_ block: [[Character]],_ index: Int) -> Bool{42         var dict = [Character: Bool]()43         let row = index / 3 * 344         let col = index % 3 * 345         for i in 0..<3 {46             for j in 0..<3 {47                 let abc = block[row + i][col + j]48                 if abc != "."{49                     if dict[abc] == true {50                         return false51                     }else {52                         dict[abc] = true53                     }54                 }55             }56         }57         return true58     }59 }

212ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3         var set = Set<String>() 4         for i in 0..<9{ 5             for j in 0..<9{ 6                 if board[i][j] == "."{ 7                     continue 8                 } 9                 if set.insert("\(board[i][j]) in row \(i)").inserted == false {10                  11                     return false12                 }13                 14                 if set.insert("\(board[i][j]) in col \(j)").inserted == false {15            16                     return false17                 }18                 19                 if set.insert("\(board[i][j]) in cube \(i/3) - \(j/3)").inserted == false {20          21                     return false22                 }23             }24         }25         return true26         27     }28 }

216ms

 1 class Solution { 2     var rows = [Set<Character>]() 3     var columns = [Set<Character>]() 4     var squares = [Set<Character>]() 5      6     func isValIDSudoku(_ board: [[Character]]) -> Bool { 7         for _ in 0..<9 { 8             rows.append(Set<Character>()) 9             columns.append(Set<Character>())10             squares.append(Set<Character>())11         }12         13         for (rowIndex,chararray) in board.enumerated() {14             for(columnIndex,char) in chararray.enumerated() {15                 if char == "." { continue }16                 17                 let squaresIndex = indexOfSquare(row: rowIndex,column: columnIndex)18                 if rows[rowIndex].contains(char) { print("row false"); return false }19                 if columns[columnIndex].contains(char) { print("column false"); return false}20                 if squares[squaresIndex].contains(char) {21                     print("squares false")22                     return false23                 }24                 25                 rows[rowIndex].insert(char)26                 columns[columnIndex].insert(char)27                 squares[squaresIndex].insert(char)28             }29         }30         31         return true32     }33     34     func indexOfSquare(row: Int,column: Int) -> Int {35         if row < 3 && column < 3 { return 0}36         if row >= 3 && row < 6 && column < 3 { return 1 }37         if row >= 6 && column < 3 { return 2 }38         if row < 3 && column >= 3 && column < 6 { return 3 }39         if row >= 3 && row < 6 && column >= 3 && column < 6 { return 4 }40         if row >= 6 && column >= 3 && column < 6 { return 5 }41         if row < 3 && column >= 6 { return 6 }42         if row >= 3 && row < 6 && column >= 6 { return 7 }43         if row >= 6 && column >= 6 { return 8 }44         45         return -146     }47 }48 49 extension Collection {50 51     subscript(optional i: Index) -> Iterator.Element? {52         return self.indices.contains(i) ? self[i] : nil53     }54 55 }

220ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3       var seen = Set<String>() 4        5       for i in 0..<9 { 6         for j in 0..<9 { 7           let currVal = board[i][j] 8            9           if currVal != "." {10             if seen.contains("\(currVal) at row \(i)") || 11                seen.contains("\(currVal) at col \(j)") || 12                seen.contains("\(currVal) at block \(3 * (i / 3)),\(j / 3)") {13               return false14             }15             else { // ValID,can be added16               seen.insert("\(currVal) at row \(i)")17               seen.insert("\(currVal) at col \(j)")18               seen.insert("\(currVal) at block \(3 * (i / 3)),\(j / 3)")19             } // End of else20           } // End of if21         }22       } // End of for23       24       return true25     }26 }

228ms

 1 class Solution { 2     func isValIDSudoku(_ board: [[Character]]) -> Bool { 3         let s = Sudoku(board: board) 4         return s.isValID() 5     } 6 } 7  8 struct Sudoku { 9     private let rows: [[Character]]10     11     init(board: [[Character]]) {12         self.rows = board13     }14     15     func row(at index: Int) -> [Character] {16         return rows[index]17     }18     19     func collumn(at index: Int) -> [Character] {20         return rows.reduce([Character](),{ (_remainder,characters) -> [Character] in21             let c = characters[index]22             return _remainder + [c]23         })24     }25     26     func square(at index: Int) -> [Character] {27         let c = index%328         let r = index/329         return square(row: r,collumn: c)30     }31     32     private func square(row: Int,collumn: Int) -> [Character] {33         let rowRange = (row * 3)..<((row * 3) + 3)34         let collumnRange = (collumn * 3)..<((collumn * 3) + 3)35         print("r:\(rowRange) c:\(collumnRange)")36         return rows[rowRange].reduce([Character](),characters) -> [Character] in37             let chars = characters[collumnRange]38             return _remainder + chars39         })40     }41     42     func isValID() -> Bool {43         let allRange = 0..<944         for index in allRange {45             let row = self.row(at: index)46             if isValID(sequence: row) == false {47                 print("invalID row \(index) : \(row)")48                 return false49             }50         }51         52         for index in allRange {53             let coll = self.collumn(at: index)54             if isValID(sequence: coll) == false {55                 print("invalID collumn \(index) : \(coll)")56                 return false57             }58         }59         60         for index in allRange {61             let square = self.square(at: index)62             if isValID(sequence: square) == false {63                 print("invalID square \(index) : \(square)")64                 return false65             }66         }67         68         return true69     }70     71     private func isValID(sequence: [Character]) -> Bool {72         var unique = Set<Character>()73         for c in sequence {74             if c == "." {75                 continue76             }77             78             if unique.contains(c) {79                 return false80             }81             82             unique.insert(c)83         }84         85         return true86     }87 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode36. 有效的数独 | Valid Sudoku全部内容，希望文章能够帮你解决[Swift]LeetCode36. 有效的数独 | Valid Sudoku所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。