Problem overview
The method solveSudoku receives a 9 by 9 board, an Array[Array[Char]], where a digit character '1' to '9' is a clue and '.' is an empty cell. It must fill every empty cell so that each row, each column and each of the nine 3 by 3 boxes contains the digits 1 to 9 exactly once, and return the solved board. The puzzle is guaranteed to have exactly one solution.
The board uses Char values, written with single quotes: '5' and '.' are characters, while "5" would be a String.
Approach: fill the empty cells in order, undo wrong guesses
A human solves Sudoku by reasoning about which digit must go where. A program can instead search. Walk through the cells in reading order, left to right and top to bottom:
- If the cell already holds a clue, move on to the next cell.
- If it is empty, try the digits
'1'to'9'. Whenever a digit breaks no rule, write it in and continue with the next cell. - If the rest of the board can't be completed, the recursion returns, the digit is erased and the next candidate is tried.
- When the walk passes the last cell, the board is complete.
This is backtracking: guess, recurse, undo. Rejecting a digit that conflicts with a row, column or box cuts the search down so that it finishes quickly on ordinary puzzles.
The solved board has to be remembered somewhere, because the undo step erases the guesses while the recursion unwinds. The lesson stores a copy of the finished board in a field, result. A non-null result also tells every pending call to stop exploring.
Step by step
- Add the field
var result: Array[Array[Char]] = nullto the class, and setthis.result = nullat the start ofsolveSudokuso an earlier call can't leak into this one. - Start the search at the top-left cell with
this.backtracking(0, 0, board), then returnthis.result. - Declare
backtracking(row, col, board)returningUnit. - Stop when done. If
this.result != null, a solution has been captured, so return. Ifrow == 9, every cell has been passed, so callsaveBoard(board)and return. - Find the next cell once, with
getNextCell, and keep its row and column asnewRowandnewCol. - Skip clues. If
board(row)(col) != '.', continue with the next cell and return. - Try the digits with
for (value <- '1' to '9'). The loop variable is aChar, and it is namedvaluebecausevalis a keyword. - Guess: when
isValid(board, row, col, value)holds, writeboard(row)(col) = value. - Recurse into the next cell, then undo with
board(row)(col) = '.'. - Write
saveBoard. It allocatesnew Array[Array[Char]](board.length), whose slots start asnull, and fills each slot withboard(i).clone(). Cloning each row makes a separate copy that later undo steps can't change. - Write
getNextCell. At column 8 it returns the first column of the next row,Array(row + 1, 0); otherwiseArray(row, col + 1). From cell (8, 8) this gives row 9. - Write
isValid. Scan all 81 cells with two nested loops. A cell conflicts if it already holdsvalueand shares a row, a column or a box with (row,col). The box test comparesrow / 3withi / 3andcol / 3withj / 3: integer division maps rows 0-2 to 0, 3-5 to 1 and 6-8 to 2. If any cell conflicts, returnfalse; after the loops, returntrue.
The solution in Scala
class Solution {
def isValid(board: Array[Array[Char]], row: Int, col: Int, value: Char): Boolean = {
for (i <- 0 until 9) {
for (j <- 0 until 9) {
val usedValue = board(i)(j) == value
val sameRowOrCol = row == i || col == j
val sameRowBox = row / 3 == i / 3
val sameColBox = col / 3 == j / 3
val sameBox = sameRowBox && sameColBox
if (usedValue && (sameRowOrCol || sameBox)) {
return false
}
}
}
return true
}
def getNextCell(row: Int, col: Int): Array[Int] = {
if (col == 8) {
return Array(row + 1, 0)
}
return Array(row, col + 1)
}
def saveBoard(board: Array[Array[Char]]): Unit = {
this.result = new Array[Array[Char]](board.length)
for (i <- 0 until board.length) {
this.result(i) = board(i).clone()
}
}
def backtracking(row: Int, col: Int, board: Array[Array[Char]]): Unit = {
if (this.result != null) {
return
}
if (row == 9) {
saveBoard(board)
return
}
val newRow = getNextCell(row, col)(0)
val newCol = getNextCell(row, col)(1)
if (board(row)(col) != '.') {
this.backtracking(newRow, newCol, board)
return
}
for (value <- '1' to '9') {
if (this.isValid(board, row, col, value)) {
board(row)(col) = value
this.backtracking(newRow, newCol, board)
board(row)(col) = '.'
}
}
}
var result: Array[Array[Char]] = null
def solveSudoku(board: Array[Array[Char]]): Array[Array[Char]] = {
this.result = null
this.backtracking(0, 0, board)
return this.result
}
}
Scala details:
- Fields and member order.
var resultis declared after the methods that use it. In a Scala class the order of members doesn't matter for methods and fields, so this is fine. - Character ranges.
'1' to '9'is a range ofCharvalues. The body receives one character at a time. - Updating a cell.
board(row)(col) = valuechanges the board in place. The caller's array is modified during the search and restored by the undo steps. - Copies. Arrays are references. Without
clone()insaveBoard, the result would share rows with the working board and the undo steps would erase it. returninsidefor.isValidreturns from within nestedforloops. Scala 3.5 accepts it but warns that non-local returns are no longer supported (they work by throwing an exception that the method catches).
Complexity
The board has a fixed size, so the work is bounded by a constant, but that constant can be huge. In the worst case the search could try 9 digits in each of the 81 cells, and every isValid call scans 81 cells. Ordinary puzzles are solved quickly because most digits are rejected at once. The memory is small: the board, one saved copy and a recursion at most 81 cells deep.
Edge cases and common mistakes
- The input board is restored. After
solveSudokureturns, the board you passed in is back to its original clues and dots, because the undo step runs while the recursion unwinds. The returned array is a separate copy. For the puzzle in the example, the first row of the result is534678912. - No solution. If a puzzle can't be completed,
resultstaysnull, so the method returnsnull. For example, a first row12345678.with a 9 lower in the last column leaves the corner cell with no valid digit, and the result isnull. - A full board. If there are no dots, every cell is a clue and the walk goes straight to row 9, so the board is copied and returned.
- Comparing the cell with itself. The target cell is empty (
'.') while it is tested, so it never counts as a conflict. - Strings instead of characters. Assigning
"."to a cell of anArray[Array[Char]]does not compile: a cell holds aChar, not aString. - Forgetting the undo. A wrong guess would stay on the board and block the correct digit for good.
- Box mix-up. The box condition needs both
row / 3 == i / 3andcol / 3 == j / 3. Testing only one of them marks a whole band of boxes as conflicting.
Testing
- The example puzzle, whose first row is
53..7...., comes back with the first row534678912and the last row345286179. isValidon the first row, column 2, accepts'4'and rejects'5'(same row),'8'(same box) and'6'(same box).getNextCell(0, 8)is[1, 0], andgetNextCell(8, 8)is[9, 0].- Solving a board that is already complete returns an identical board.
