Problem overview
The method isValidSudoku receives a 9 x 9 board as an Array[Array[Char]]. Each cell holds a digit from '1' to '9', or '.' when it is empty. 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: the task is to check the digits already placed, not to solve the puzzle.
The classic partly filled board, starting with the rows 53..7.... and 6..195..., is valid. Changing its top-left 5 to an 8 makes column 0 hold two 8s, and the top-left box holds two as well, so the answer becomes false. A board whose first row is 12345678. with a 9 alone in row 4, column 8 is valid, even though the last cell of row 0 could never be filled: no digit repeats yet.
Approach: remember what each row, column and box has seen
The direct way is to scan the row, the column and the box of every filled cell again and look for a twin. On a 9 x 9 board that is fast enough, but it looks at each cell many times over.
A cleaner way visits each cell once and keeps a record. There are 9 rows, 9 columns and 9 boxes, so keep 27 sets of digits: one per row, one per column, one per box. When a filled cell is reached, ask the three sets that cell belongs to whether they already contain its digit. If any does, the digit is a repeat and the board is invalid. If none does, add the digit to all three sets and move on. Every check is a set lookup, which takes constant time, so the whole board takes 81 cell visits.
The only tricky part is naming the 9 boxes. Number them left to right, then top to bottom. A cell at row r and column c is in box row r / 3 and box column c / 3, using integer division, which drops the remainder. Its box number is (r / 3) * 3 + c / 3. Cell (4, 7) gives 1 * 3 + 2 = 5, the right box of the middle band. Cell (0, 0) is in box 0 and cell (8, 8) in box 8.
Step by step
- Create the row sets.
Array.fill(9)(scala.collection.mutable.Set[Char]())builds an array of 9 empty mutable sets.rows(r)holds the digits seen so far in rowr. - Create
colsandboxesthe same way, so every cell has three sets to check. - Loop over the rows with
for (r <- 0 until 9). - Loop over the columns inside it with
for (c <- 0 until 9), so the cells are visited row by row. - Read the cell into a
valnameddigit. Indexing a nested array uses two pairs of parentheses:board(r)(c). - Skip empty cells. Only when
digit != '.'does the rest run. Scala has nocontinue, so the work sits inside theif. - Compute the box number with the formula above.
- Look for a repeat. If
rows(r),cols(c)orboxes(box)already contains the digit,return falseat once. - Record the digit in the row set, the column set and the box set, so later cells in the same row, column or box can find it.
- Finish with
true. If every filled cell was checked against the earlier ones and nothing repeated, the board is valid. The last expression is the method's value.
The solution in Scala
class Solution {
def isValidSudoku(board: Array[Array[Char]]): Boolean = {
val rows = Array.fill(9)(scala.collection.mutable.Set[Char]())
val cols = Array.fill(9)(scala.collection.mutable.Set[Char]())
val boxes = Array.fill(9)(scala.collection.mutable.Set[Char]())
for (r <- 0 until 9) {
for (c <- 0 until 9) {
val digit = board(r)(c)
if (digit != '.') {
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)
}
}
}
true
}
}
The Scala details worth a closer look:
- Mutable versus immutable sets. A plain
Setin Scala is immutable: it has no way to add an element in place.scala.collection.mutable.Setcan grow, which is what a record of seen digits needs. In a file of your own you could writeimport scala.collection.mutableand thenmutable.Set[Char](). Array.fillruns its second argument once per place. Because the set is created inside the second parameter list, each of the 9 slots gets its own set. Building one set first and filling the array with it would make all 9 slots share that set: adding a digit to one would show up in all the others.valarrays can still change.rowsis aval, so it can't be pointed at another array, but its elements are sets that change freely.addreturns aBoolean. It givestruefor a new element andfalsefor one already present. The solution ignores that value and usescontainsto check first, which makes the three checks easy to read.returninside afor. The loop body is a closure, and Scala 3.5 reports a warning, "Non local returns are no longer supported", for areturnthere. The program still compiles and returns the right answer. The recommended replacement isscala.util.boundarywithboundary.break, or awhileloop.- Characters compare directly.
digit != '.'compares aCharwith aChar. The digits stay characters throughout; they are never converted to numbers, because they are only compared for equality.
Complexity
Time: O(81), that is, constant. The loops visit 81 cells, and each visit does at most three set lookups and three insertions, each of which takes constant time on average.
Space: O(81), also constant. The 27 sets together hold at most 81 digits, one per filled cell in each of its three sets, so at most 3 * 81 entries.
Edge cases and common mistakes
- An empty board. A board of nothing but
'.'is valid. Empty cells never count, however many there are. - A repeat found by only one set. A 5 at the first cell of row 0 and another 5 at index 4 of the same row share a row but nothing else. Two 5s at (0, 0) and (8, 0) share only a column. Two 5s at (0, 0) and (1, 1) share only a box. Each of these boards returns
false, which is why all three sets must be checked. - Treating
'.'as a digit. Without thedigit != '.'test, the second empty cell in a row would look like a repeat and every board would be invalid. - A wrong box formula. Writing
r / 3 + c / 3gives the same number to different boxes: boxes 1 and 3 would both be 1. Multiplying the box row by 3 is what makes the 9 numbers distinct. - Sharing one set across the array. Creating a set once and passing it to
Array.fillmakes every row share it, so the second row would reject any digit that appeared in the first. - Solving the puzzle. A valid board can have no solution. The method only checks the digits already placed.
Testing
- The classic board (
53..7....down to....8..79) givestrue. - The same board with an 8 instead of the top-left 5 gives
false. - A board with
12345678.as its first row and a single 9 at row 4, column 8 givestrue. - A board of only
'.'givestrue. - Two 5s in the same row, at columns 0 and 4, give
false. - Two 5s in the same column, at rows 0 and 8, give
false. - Two 5s at (0, 0) and (1, 1), in the same box only, give
false.
