Problem overview
The method receives a 9 x 9 board as Array<CharArray>. Each cell holds a digit from '1' to '9' or '.' for an empty cell. It returns true when no digit appears twice in a row, in a column or in one of the nine 3 x 3 boxes. Only the filled cells count, and the board does not have to be solvable: you check the digits that are already there and do not solve anything.
The first example, the well-known board starting with 53..7...., is valid. Replace its top-left 5 with an 8 and it becomes invalid: column 0 then holds two 8s (rows 0 and 3), and so does the top-left box (rows 0 and 2). The third example, with 12345678. in row 0 and a single 9 at row 4, column 8, is valid even though it can't be completed, because no digit repeats.
Approach
For each filled cell you could scan its row, its column and its box again and look for a copy of the digit. On a 9 x 9 board that is fast enough, but it looks at every cell many times.
A faster way is to remember what you have seen. Keep one set of digits for each of the 9 rows, one for each of the 9 columns and one for each of the 9 boxes: 27 sets. Visit every cell once. If its digit is already in the set of its row, its column or its box, a digit repeats and the board is invalid. Otherwise add the digit to all three sets. Each cell takes constant time, so the whole board takes O(81) time and O(81) space, which is a fixed amount for a fixed board.
Step by step
- Row sets.
val rows = Array(9) { HashSet<Char>() }builds an array of 9 sets.rows[r]holds the digits seen so far in rowr. - Column and box sets. Build
colsandboxesthe same way. - Visit every cell with two nested loops:
rover0 until 9and, inside it,cover0 until 9. This goes row by row. - Read the cell into
val digit = board[r][c]. - Skip empty cells. If
digit == '.',continuewith the next cell. Empty cells can never break a rule. - Find the box.
r / 3is the box's row (0, 1 or 2) andc / 3its column. Boxes are numbered left to right, then top to bottom, so the number is(r / 3) * 3 + c / 3. - Check for a repeat. If
rows[r],cols[c]orboxes[box]already containsdigit, returnfalseat once. - Remember the digit by adding it to the three sets, so the cells after this one find it.
- If both loops finish, no digit repeated: return
true.
The solution in Kotlin
class Solution {
fun isValidSudoku(board: Array<CharArray>): Boolean {
val rows = Array(9) { HashSet<Char>() }
val cols = Array(9) { HashSet<Char>() }
val boxes = Array(9) { HashSet<Char>() }
for (r in 0 until 9) {
for (c in 0 until 9) {
val digit = board[r][c]
if (digit == '.') continue
val box = (r / 3) * 3 + c / 3
if (rows[r].contains(digit) || cols[c].contains(digit) || boxes[box].contains(digit)) {
return false
}
rows[r].add(digit)
cols[c].add(digit)
boxes[box].add(digit)
}
}
return true
}
}
Kotlin details worth knowing:
Array(9) { HashSet<Char>() }runs the lambda once per place, so every place gets its own set. Filling the array with one shared set would make all rows, columns or boxes use the same digits and report false repeats. The array reference is aval, but the sets inside it still change.- Digits are
Chars, not numbers.'5'is a character, and comparing with'.'uses single quotes. The code never turns the characters into numbers: aCharworks fine as a set element. - Integer division truncates.
7 / 3is2(the remainder is dropped), while7.0 / 3is2.3333333333333335. The box formula relies on this. 0 until 9excludes 9, so the indexes run 0 to 8.continueinside the inner loop skips to the nextc, not to the next row.- The
||chain stops at the first true check, so the later sets are not even read once a repeat is found.
The box number
The formula maps each cell to one of the nine boxes. Some values it gives:
| Cell (row, column) | Box |
|---|---|
| (0, 0) | 0 |
| (0, 8) | 2 |
| (3, 2) | 3 |
| (5, 3) | 4 |
| (4, 7) | 5 |
| (8, 8) | 8 |
For (4, 7): 4 / 3 is 1 and 7 / 3 is 2, so the box is 1 * 3 + 2 = 5, the right box of the middle band.
Complexity
Time: O(81). The loops visit 81 cells, and each visit does at most three set lookups and three insertions, each constant on average. Because the board size is fixed, this is constant time; for an n x n board it would be O(n²).
Space: O(81). The 27 sets hold at most 9 digits each, so at most 243 entries in total.
Edge cases and common mistakes
- Adding to the sets before checking. If you add the digit first, the check finds the digit you just added and every cell looks like a repeat.
- Treating
'.'as a digit. Without thecontinue, the second empty cell in a row would count as a repeated'.'and the empty board would be rejected. - Forgetting the box check. A board can have no repeats in any row or column and still be wrong. For example, a 5 at row 0, column 0 and another at row 1, column 1 share a box but no row or column.
- Using the wrong box formula.
r / 3 + c / 3looks plausible but gives 2 both for (0, 8) and for (6, 2), two cells in different boxes. The row must be multiplied by 3. - Trying to solve the puzzle. The third example is valid but has no solution. The method only looks at the digits already placed.
Testing
These boards were run against the solution above. Each board is written row by row, and the dots are empty cells.
| Board | Result |
|---|---|
Example 1 (53..7.... and so on) | true |
| Example 1 with an 8 in the top-left corner | false |
Example 3 (12345678., one 9 at row 4, column 8) | true |
| A 5 at (0, 0) and another at (3, 0): same column | false |
| A 5 at (0, 0) and another at (1, 1): same box only | false |
| A 5 at (0, 0) and another at (0, 2): same row and box | false |
| A 5 at (0, 0) and another at (8, 4): nothing shared | true |
| An empty board | true |
