Valid Sudoku in Swift

Question

This is my solution to LeetCode – Valid Sudoku in Swift.

img

class Solution {
 func isValidSudoku(_ board: [[Character]]) -> Bool {
 let count = board.count
 var set = Set<Character>()
 for i in 0..<count{
 // firstly
 set = Set(board[i])
 var num = board[i].reduce(0 , {(result : Int, char : Character)
 in
 var cent = 0
 if String(char) == "."{
 cent = 1
 }
 return result + cent
 })
 if num > 0 , count - num != set.count - 1{
 return false
 }
 else if num == 0, set.count != count{
 return false
 }
 // secondly
 set = Set(board.reduce([Character]() , { resultArray, chars in
 return resultArray + [chars[i]]
 }))
 num = board.reduce(0 , {(result : Int, chars : [Character])
 in
 var cent = 0
 if String(chars[i]) == "."{
 cent = 1
 }
 return result + cent
 })
 if num > 0 , count - num != set.count - 1{
 return false
 }
 else if num == 0, set.count != count{
 return false
 }
 // thirdly
 let characters = board.flatMap{
 return 0ドル
 }
 let fisrtMiddle = ( i/3 ) * 27 + ( i % 3 ) * 3 + 1
 let secondMiddle = fisrtMiddle + 9
 let thirdMiddle = fisrtMiddle + 18
 let arrayThree = [characters[fisrtMiddle - 1], characters[fisrtMiddle], characters[fisrtMiddle + 1],
 characters[secondMiddle - 1], characters[secondMiddle], characters[secondMiddle + 1],
 characters[thirdMiddle - 1], characters[thirdMiddle], characters[thirdMiddle + 1]]
 set = Set(arrayThree)
 num = arrayThree.reduce(0 , {(result : Int, char : Character)
 in
 var cent = 0
 if String(char) == "."{
 cent = 1
 }
 return result + cent
 })
 if num > 0 , count - num != set.count - 1{
 return false
 }
 else if num == 0, set.count != count{
 return false
 }
 }
 return true
 }
}

How can I make it shorter in syntax and keep intuitive, like the following Python code?

def isValidSudoku(self, board):
 seen = sum(([(c, i), (j, c), (i/3, j/3, c)]
 for i, row in enumerate(board)
 for j, c in enumerate(row)
 if c != '.'), [])
 return len(seen) == len(set(seen))

The Python code is very Pythonic and short.

How to use Swift syntax power to make my code shorter?

I think Functional is a good choice. RxSwift is welcomed.

Answer 1

Naming

Some variable names should be more descriptive:

• What does set contain?
• What does num count?
• What is cent or arrayThree?

Simplifications

if String(char) == "." can be shorted to if char == ".", the conversion to a string is not needed because "." can be both a string literal and a character literal.

In

var num = board[i].reduce(0 , {(result : Int, char : Character)
 in
 var cent = 0
 if String(char) == "."{
 cent = 1
 }
 return result + cent
})

the closure can be shortened to

var num = board[i].reduce(0 , {(result, char) in
 char == "." ? result + 1 : result
})

without the need for a temporary variable.

In

set = Set(board.reduce([Character]() , { resultArray, chars in
 return resultArray + [chars[i]]
}))

an array is created with the elements in column #i, and put into a set. That can be simplified to

let column = board.map { 0ドル[i]} // Column #i
set = Set(column)

and column can then also be used in the following count of empty fields.

The creation of an array of all entries of a block can be simplified using array slices:

let firstRow = 3 * (i / 3)
let firstCol = 3 * (i % 3)
let block = board[firstRow..<firstRow+3].flatMap { 0ドル[firstCol..<firstCol+3]}

Generally, the check for duplicate digits in a row/column/block can be simplified if you filter out empty fields before creating the set, that makes counting the empty fields obsolete.

Comments

The comments

// firstly
// secondly
// thirdly

are not really helpful.

Putting it together

Summarizing the above suggestions so far, the code could look like this:

class Solution {
 func isValidSudoku(_ board: [[Character]]) -> Bool {
 for i in 0..<9 {
 // Check digits in row #i:
 let rowDigits = board[i].filter { 0ドル != "." }
 if rowDigits.count != Set(rowDigits).count {
 return false
 }
 // Check digits in column #i:
 let colDigits = board.map { 0ドル[i] }.filter { 0ドル != "." }
 if colDigits.count != Set(colDigits).count {
 return false
 }
 // Check digits in block #i:
 let firstRow = 3 * (i / 3)
 let firstCol = 3 * (i % 3)
 let blockDigits = board[firstRow..<firstRow+3].flatMap { 0ドル[firstCol..<firstCol+3]}
 .filter { 0ドル != "." }
 if blockDigits.count != Set(blockDigits).count {
 return false
 } 
 }
 return true
 }
}

An alternative approach

The Python solution can not be translated directly to Swift, one reason is that tuples are not Hashable and therefore cannot be put into a set. Also inhomogeneous collections are better avoided in Swift.

But we can enumerate the board in a similar fashion, and put each element into a set corresponding to its row, column, and block. The return value from the insert statement already indicates if an identical element was already present.

That leads to the following implementation:

class Solution {
 func isValidSudoku(_ board: [[Character]]) -> Bool {
 var rowSets = Array(repeating: Set<Character>(), count: 9)
 var colSets = Array(repeating: Set<Character>(), count: 9)
 var blockSets = Array(repeating: Set<Character>(), count: 9)
 for (i, row) in board.enumerated() {
 for (j, char) in row.enumerated() where char != "." {
 if !rowSets[i].insert(char).inserted {
 return false
 }
 if !colSets[j].insert(char).inserted {
 return false
 }
 let block = (i / 3) + 3 * (j / 3)
 if !blockSets[block].insert(char).inserted {
 return false
 }
 }
 }
 return true
 }
}

I haven't checked which one is more efficient, I leave that task to you :)

• dengApro: The latter one gets better performance. It takes 316 ms to pass 504 test case in Leetcode. And the prior one takes 356 ms. It is heard that functional languages are a bad fit for high performance computing: they’re high-level, rely on garbage collection, are pretty inflexible about memory layouts and don’t permit all the low-level optimizations you need to maximize performance.
• dengApro: Wondering where to find the syntax ‘set.inserted’ . I did not googled it yet. And not see it in doc. And it works
• Martin R: @dengApro: That overview page does not show the return values of the methods. If you go to Set.insert(_:) then you see that the method returns a tuple whose first member .inserted indicates if the member was already present or not.

Answer 2

Alternative solution

Here is the (current) fastest solution. It is pretty straightforward :

1- First off, let's model the Sudoku grid : A row is a set of unique digits from 0 to 9, represented by characters. The rows all together, will be represented by an array of those sets :

var rows = Array(repeating: Set<Character>(), count: 9)

rows is mutable since we'll be filling those initially empty sets.

2- The same goes for the columns :

var columns = Array(repeating: Set<Character>(), count: 9)

3- A 3x3 box will be modeled by a set of characters. Three boxes on the same horizontal line will be represented by an array of 3 boxes (3 sets of characters). 3 of those arrays make a whole Sudoku grid :

var boxes = Array(repeating: Array(repeating: Set<Character>(), count: 3), count: 3)

4- Then, we loop through all the "rows" and "columns" inside of board :

for row in 0..<9 {
 for column in 0..<9 {
 let value = board[row][column]
 ...
 }
}

5- If a cell is not empty :

let value = board[row][column]
if value != "." {
 ...
}

6- ... we try to insert it into a cell. A cell belongs to a row, a column, and a box. Three checks have to be made: If either the row, or the column, or the box already contains that character, return false.

To do this we use the pretty handy inserted element from the tuple returned by the insert(_:) method :

if !rows[row].insert(value).inserted
 || !columns[column].insert(value).inserted
 || !boxes[row/3][column/3].insert(value).inserted {
 return false
}

---

Here is the complete solution :

class Solution {
 func isValidSudoku(_ board: [[Character]]) -> Bool {
 var rows = Array(repeating: Set<Character>(), count: 9)
 var columns = Array(repeating: Set<Character>(), count: 9)
 var boxes = Array(repeating: Array(repeating: Set<Character>(), count: 3), count: 3)
 for row in 0..<9 {
 for column in 0..<9 {
 let value = board[row][column]
 if value != "." {
 if !rows[row].insert(value).inserted
 || !columns[column].insert(value).inserted
 || !boxes[row/3][column/3].insert(value).inserted {
 return false
 }
 }
 }
 }
 return true
 }
}

It's execution time is 204 ms on LeetCode :

100%

Compared to 212 ms for the alternative approach given in the accepted answer (which is faster than 70.73%)

---

Playing golf

If you're looking for a short, Pythony, solution, (not necessarily the fastest), then here is a solution :

class Solution {
 func isValidSudoku(_ board: [[Character]]) -> Bool {
 var seen: [String] = []
 for (i, row) in board.enumerated() {
 for case let (j, c) in row.enumerated() where c != "." {
 seen.append(contentsOf: ["r\(i)\(c)", "c\(j)\(c)", "b\(i/3)\(j/3)\(c)"])
 }
 }
 return seen.count == Set(seen).count
 }
}