Problem overview
Fill in a 9 by 9 Sudoku board so that every row, every column and every one of the nine 3 by 3 boxes contains each digit from 1 to 9 exactly once. The board is an Array<CharArray>: each cell is a Char, either a digit from '1' to '9' or '.' for an empty cell. solveSudoku(board) returns the completed board. The puzzle has exactly one solution.
For a typical puzzle whose first row is 53..7...., the solved first row is 534678912.
Approach
A person solves Sudoku by logic. A program can simply try digits and take them back when they lead nowhere. That is backtracking:
- Go through the cells in reading order: left to right, then top to bottom.
- If the cell already has a digit, move on.
- If it is empty, try the digits
'1'to'9'. For each digit that breaks no rule, write it in and continue with the next cell. - If the continuation fails, erase the digit (put
'.'back) and try the next one. - If we walk past the last cell, every cell is filled legally, and the board is a solution.
The same rules that define a solution also prune the search. A digit is rejected the moment it repeats in its row, column or box, so the program explores only boards that have no conflicts so far.
Step by step
- A place for the answer. The class property
var result: Array<CharArray>? = nullwill hold the solved board.solveSudokusets it tonullfirst, so a previous call can't leave an answer behind. Using a property lets the recursive helper report success without returning anything. - Start at the top-left. Call
this.backtracking(0, 0, board). - Return the result.
this.result!!converts the nullable property to a non-null value, and throws if it is stillnull. - Stopping checks in
backtracking. Ifresultis already set, return at once, which unwinds all pending calls. Ifrow == 9, the board is complete: callsaveBoard(board)and return. - Find the next cell with
getNextCell, which returns a two-element array, row first and column second. - Skip clues. If
board[row][col] != '.', recurse on the next cell and return. - Try digits. For an empty cell, loop over the character range
'1'..'9'. The variable is calledvalue, notval, becausevalis a Kotlin keyword. - Choose, explore, undo. If
isValid(board, row, col, value)holds, set the cell, recurse on the next cell and then set the cell back to'.'. - Write
saveBoard. It builds a new array withArray(board.size) { CharArray(0) }and then replaces each row withboard[i].copyOf(). A snapshot is needed because the board keeps being edited while the recursion unwinds. - Write
getNextCell. In column 8 the next cell is column 0 of the next row. Otherwise it is the next column of the same row. From the last cell the answer is row 9, which the helper treats as done. - Write
isValid. Scan all 81 cells. A conflict exists when a cell already holds the digit and shares a row, a column or a box with the target. Two cells share a box whenrow / 3 == i / 3andcol / 3 == j / 3, because integer division maps rows 0 to 2 to 0, rows 3 to 5 to 1 and rows 6 to 8 to 2.
The solution in Kotlin
class Solution {
fun isValid(board: Array<CharArray>, row: Int, col: Int, value: Char): Boolean {
for (i in 0 until 9) {
for (j in 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
}
fun getNextCell(row: Int, col: Int): IntArray {
if (col == 8) {
return intArrayOf(row + 1, 0)
}
return intArrayOf(row, col + 1)
}
fun saveBoard(board: Array<CharArray>) {
this.result = Array(board.size) { CharArray(0) }
for (i in board.indices) {
this.result!![i] = board[i].copyOf()
}
}
fun backtracking(row: Int, col: Int, board: Array<CharArray>) {
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 in '1'..'9') {
if (this.isValid(board, row, col, value)) {
board[row][col] = value
this.backtracking(newRow, newCol, board)
board[row][col] = '.'
}
}
}
var result: Array<CharArray>? = null
fun solveSudoku(board: Array<CharArray>): Array<CharArray> {
this.result = null
this.backtracking(0, 0, board)
return this.result!!
}
}
Kotlin details:
- Chars, not strings. A cell is a
Charwritten with single quotes:'.'and'5'. Comparingboard[i][j] == valuecompares two characters. ACharis not anInt, so'5'and5are different things. - A
Charrange.'1'..'9'is a range of characters, sofor (value in '1'..'9')visits'1','2'and so on up to'9'. - Nullable property. The type
Array<CharArray>?allowsnull. After the checkthis.result != nullKotlin still doesn't smart-cast a mutable property, which is whysaveBoardwrites throughthis.result!!. The!!operator throwsNullPointerExceptionif the value isnull. copyOf()on aCharArrayreturns a new array with the same contents. Without copying the rows, the saved board would share them with the working board, and the undo steps would erase the answer.- The board is restored. After the solved board is saved, the recursion unwinds, and every
board[row][col] = '.'line runs. WhensolveSudokureturns, the board you passed in is back to the original puzzle, and the answer is only in the returned array. - Property placement.
resultis declared below the methods that use it, which Kotlin allows inside a class.
Complexity
Worst-case backtracking over 81 cells is exponential, since each empty cell may try up to 9 digits. The rule checks prune the vast majority of branches, so a normal 9 by 9 puzzle finishes quickly. Each isValid call scans all 81 cells, a constant for this fixed size, so each step costs O(1). The recursion is at most 81 levels deep, and the extra memory is a constant: one copy of the board.
Edge cases and common mistakes
- Forgetting the undo. Without
board[row][col] = '.', failed guesses stay on the board and poison later attempts. - Not copying the solution. After the unwinding, the working board is back to the puzzle, so a saved reference to it would show the original clues.
- Not stopping after a solution. The early
result != nullcheck ends the search. Without it, the loops would continue trying digits and the code would keep doing pointless work. - A puzzle with no solution. The lesson guarantees one solution. If there were none,
resultwould staynulland!!would throwNullPointerException. A first row such as12345678.with a 9 at the bottom of the last column triggers it. - Box arithmetic. Compare
row / 3withi / 3andcol / 3withj / 3. Comparingrow % 3would match unrelated cells. - Treating digits as numbers. Writing
board[row][col] = 5doesn't compile. The cell needs aChar, such as'5'.
Testing
- A board whose first row is
53..7....and whose last row is....8..79returns a board with first row534678912and last row345286179. isValid(board, 0, 2, '5')on the original puzzle isfalse, because the first row already has a 5.isValid(board, 0, 2, '4')on the same puzzle istrue.