Problem overview
The method isValidSudoku receives a 9 x 9 board, a [[Character]] in which each cell is a digit from "1" to "9" or "." for an empty cell. It returns true when no digit appears twice in the same row, the same column or the same 3 x 3 box. Only the filled cells are checked. The board doesn't have to be solvable: you check the digits that are already there, you don't solve the puzzle.
The first example is a well-known partly filled board with no repeated digit, so the answer is true. In the second, the 5 in the top left corner is replaced by an 8. Column 0 now holds two 8s, in rows 0 and 3, and so does the top left box, in rows 0 and 2, so the answer is false. The third board has the digits 1 to 8 in row 0 and a single 9 in row 4, column 8. Nothing repeats, so it is valid even though no solution exists: the last cell of row 0 could only be a 9, and column 8 already has one.
Approach: remember what each row, column and box has seen
Checking a cell means asking three questions: is this digit already in my row, in my column, in my box? Scanning the row, the column and the box again for every cell works on a board this small, but it looks at each cell many times over.
A better way keeps a memory. Create one set of digits per row, per column and per box: 27 sets in all. Then visit the cells once. For each filled cell, look the digit up in its three sets. If any of them has it, the digit repeats and the board is invalid. Otherwise add the digit to all three, so later cells can find it. A set lookup and an insertion take constant time, so the whole check is one pass over 81 cells.
The only piece of arithmetic is the box number. The boxes are numbered 0 to 8, left to right and then top to bottom. A cell in row r and column c is in box row r / 3 and box column c / 3, where / on two Int values drops the remainder. Three boxes fit in each band, so the box number is (r / 3) * 3 + c / 3. For example, the cell at row 4, column 7 has 4 / 3 = 1 and 7 / 3 = 2, so it lies in box 1 * 3 + 2 = 5, the right box of the middle band. The corners give 0 for (0, 0) and 8 for (8, 8).
Step by step
- Create the row sets.
rowsis an array of 9 emptySet<Character>, built with[Set<Character>](repeating: Set<Character>(), count: 9).rows[r]holds the digits seen so far in rowr. - Create
colsandboxesthe same way: nine empty sets each, one per column and one per box. - Loop over the rows and, inside, the columns, with
randcgoing over0..<9. This visits every cell, row by row. - Read the cell into
digit. - Skip empty cells. If
digitis".",continuewith the next cell. Empty cells never break a rule, however many there are. - Compute the box number as described above.
- Look for a repeat. If
rows[r],cols[c]orboxes[box]already containsdigit, returnfalse. Each set holds the digits of the cells visited before this one, so finding the digit there means it appears twice. - Remember the digit. Insert it into all three sets.
- Return
trueafter the loops. Every filled cell was checked against the earlier ones and nothing repeated.
The solution in Swift
class Solution {
func isValidSudoku(_ board: [[Character]]) -> Bool {
var rows = [Set<Character>](repeating: Set<Character>(), count: 9)
var cols = [Set<Character>](repeating: Set<Character>(), count: 9)
var boxes = [Set<Character>](repeating: Set<Character>(), count: 9)
for r in 0..<9 {
for c in 0..<9 {
let digit = board[r][c]
if digit == "." { continue }
let box = (r / 3) * 3 + c / 3
if rows[r].contains(digit) || cols[c].contains(digit) || boxes[box].contains(digit) {
return false
}
rows[r].insert(digit)
cols[c].insert(digit)
boxes[box].insert(digit)
}
}
return true
}
}
The Swift details worth knowing:
- Sets are value types.
repeating:count:fills the array with 9 copies of the empty set, which sounds like one shared set. In Swift, sets, like arrays and strings, are copied when they are assigned or stored, so each slot is an independent set. Inserting intorows[0]leavesrows[1]empty. In a language where collections are references, this construction would share one set. Character, notString. The cells areCharactervalues. A literal such as"."becomes aCharacterbecause the comparisondigit == "."has aCharacteron its left. The digits are never turned into numbers:"5"is only compared and stored as a character.board[r][c]. The board is an array of rows, so the row index comes first. Each row is itself an array of nine characters.insertmutates in place.rows[r].insert(digit)changes one element of therowsarray, which works becauserowsis declared withvar.- Integer division.
r / 3onInttruncates toward zero, so7 / 3is 2, not 2.33. - The one-line
continue. In Swift, the braces ofifare required, so a one-line form is writtenif digit == "." { continue }.
Complexity
Time: O(81), which is constant. The two loops visit 81 cells, and each visit does three set lookups and three insertions, each of which takes constant time.
Space: O(81), also constant. The 27 sets hold at most 9 digits each, and every filled cell adds a digit to three sets, so at most 243 entries exist at once. The size does not depend on any input, because the board always has the same shape.
Edge cases and common mistakes
- Counting empty cells. If
"."goes into the sets, the second empty cell in a row looks like a repeat. Skip them first. - A wrong box formula.
r / 3 + c / 3gives the same number for different boxes. For instance box (0, 1) and box (1, 0) would both be 1. Multiply the box row by 3. - Checking only one rule. A digit repeated in a box only can still be valid for rows and columns. For example, a 5 at row 3, column 3 and another at row 4, column 4 break only the box rule, and the lesson's code returns
falsefor them. - Same digit in unrelated cells. A 5 at row 0, column 0 and a 5 at row 1, column 3 share no row, column or box, so the board is still valid.
- Confusing valid with solvable. The method never tries to complete the puzzle. The third example is valid and has no solution.
Testing
- The first example board (the one with a 5 in the top left corner) gives
true. - The same board with an 8 in the top left corner gives
false. - The board with the digits 1 to 8 in row 0 and a 9 at row 4, column 8, gives
true. - A board of 81 dots gives
true. - A board with
5...5....in row 0 and dots elsewhere givesfalse: a repeat in a row. - A board with a 5 at the start of row 0 and another at the start of row 8 gives
false: a repeat in a column. - A board with a 5 at row 3, column 3 and another at row 4, column 4 gives
false: a repeat in a box only.
