Problem overview
The method solveSudoku receives a 9x9 board as a [][]byte. Each cell holds a digit character from '1' to '9' or '.' for an empty cell. The method must fill every empty cell so that each row, each column and each of the nine 3x3 boxes contains every digit from 1 to 9 exactly once, and return the completed grid. The puzzle has exactly one solution.
Because the board is a slice of byte slices, a clue like 5 is the byte '5', not the integer 5. That detail shapes the code: the digits are tried as characters, and the empty marker is the byte '.'.
Approach: try a digit, recurse, undo
A person solving a puzzle by hand writes a digit, continues, and erases it when it leads to a contradiction. Backtracking does exactly that. Walk through the cells in row-major order: left to right along a row, then on to the next row. At a clue, move on. At an empty cell, try each digit from '1' to '9'. If a digit breaks no rule against the digits already on the board, write it in and solve the rest of the board. If the rest can't be solved, erase the digit and try the next one.
The alternative is to fill all empty cells with every possible combination and check the board at the end. That is hopeless: with 50 empty cells there are 9^50 combinations. Backtracking rejects a bad digit the moment it is placed, which cuts off every board that would have started with it.
The recursion has two ways to end. Walking past the last cell (row 9) means every cell was filled legally, so the board is a solution. The solution is then copied into a field called result, and every pending call sees that it is no longer nil and returns.
Step by step
- Store the answer in a field. The
Solutionstruct gets a fieldresultof type[][]byte.solveSudokuresets it tonilfirst, so a second call on the same struct starts clean. - Start the search at (0, 0) and return
this.resultafterwards. The recursive helper returns nothing; the answer reaches the caller through the field. - Write
backtracking(row, col, board). Its first check returns whenresultis already set, which unwinds all pending calls once a solution exists. The second check,row == 9, means the walk has passed the last cell, so it saves the board and returns. - Compute the next cell with
getNextCelland keep its row and column innew_rowandnew_col. - Skip clues. If the cell isn't
'.', continue with the next cell and return. Clues must never be overwritten. - Try each digit. A loop from
byte('1')to'9'proposes candidates. Each one is checked withisValid; only a legal digit is written to the board, followed by the recursive call. - Undo the guess by writing
'.'back after the recursive call returns. This is the backtracking step: the board is exactly as it was before the guess, ready for the next digit. - Write
saveBoardto copy the finished grid intoresult, one fresh row at a time. A snapshot is needed because the board keeps changing while the recursion unwinds. - Write
getNextCell. At column 8 it returns[]int{row + 1, 0}; otherwise[]int{row, col + 1}. From the last cell, (8, 8), it yields row 9, the signal for "solved". - Write
isValid. It scans all 81 cells. A cell that already holds the candidate digit is a conflict if it shares the row or column with the target, or lies in the same 3x3 box. Dividing a coordinate by 3 gives its box index (0, 1 or 2), and two cells share a box when both box indices match.
The solution in Go
type Solution struct {
result [][]byte
}
func (this *Solution) isValid(board [][]byte, row int, col int, val byte) bool {
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
usedValue := board[i][j] == val
sameRowOrCol := row == i || col == j
sameRowBox := row/3 == i/3
sameColBox := col/3 == j/3
sameBox := sameRowBox && sameColBox
if usedValue && (sameRowOrCol || sameBox) {
return false
}
}
}
return true
}
func (this *Solution) getNextCell(row int, col int) []int {
if col == 8 {
return []int{row + 1, 0}
}
return []int{row, col + 1}
}
func (this *Solution) saveBoard(board [][]byte) {
this.result = make([][]byte, len(board))
for i := 0; i < len(board); i++ {
this.result[i] = append([]byte{}, board[i]...)
}
}
func (this *Solution) backtracking(row int, col int, board [][]byte) {
if this.result != nil {
return
}
if row == 9 {
this.saveBoard(board)
return
}
new_row := this.getNextCell(row, col)[0]
new_col := this.getNextCell(row, col)[1]
if board[row][col] != '.' {
this.backtracking(new_row, new_col, board)
return
}
for val := byte('1'); val <= '9'; val++ {
if this.isValid(board, row, col, val) {
board[row][col] = val
this.backtracking(new_row, new_col, board)
board[row][col] = '.'
}
}
}
func (this *Solution) solveSudoku(board [][]byte) [][]byte {
this.result = nil
this.backtracking(0, 0, board)
return this.result
}
The Go details worth knowing:
- Bytes, not runes.
val := '1'would makevalarune(anint32), andboard[row][col] = valwould not compile because the board holds bytes.byte('1')gives the loop variable the right type. The untyped constants'9'and'.'adapt tobytein comparisons and assignments. - Pointer receivers. The methods use
*Solutionso that settingthis.resultchanges the caller's struct. With a value receiver, each method would modify its own copy and the answer would be lost. (thisis a legal receiver name; Go code usually uses a short name such ass.) - Slices are shared. The board is passed down the recursion as a slice header, but every call sees the same rows, so writing
board[row][col]is visible everywhere. That is what makes the guess-and-undo pattern work, and it is also whysaveBoardmust copy. - Copying a row.
append([]byte{}, board[i]...)appends the row's bytes to a new empty slice, producing an independent copy. Assigningboard[i]directly would copy only the slice header and still share the storage. - The input is restored. Because every guess is undone, the board passed in ends up as it started, with the empty cells still
'.'. The solution exists only in the returnedresult. - The result stays
nilfor an unsolvable board. The method then returnsnil. The lesson's puzzles always have a solution.
Complexity
Let E be the number of empty cells. Time: each empty cell tries up to 9 digits, and each isValid call scans 81 cells, so the worst case is on the order of 81 * 9^E. Real puzzles run far below that bound, because most digits are rejected right away and whole branches vanish with them.
Space: the recursion is at most 81 calls deep, and the saved copy holds 81 bytes, so extra space is O(1) for a 9x9 board.
Edge cases and common mistakes
- Forgetting the undo. If
board[row][col] = '.'is missing, a wrong guess stays on the board and poisons every later check. - Letting the checks match the target cell.
isValidis only called for empty cells, so the target cell holds'.'and never equals a digit. That is why scanning all 81 cells, target included, is safe. - Returning the live board instead of a copy. Without
saveBoard, the returned grid would be the board that the recursion has already wiped back to its starting state. - Wrong box test. Comparing
row/3 == i/3alone includes the whole band of three rows. Both the row band and the column band must match. - Not stopping after the solution. Without the
result != nilcheck, the loops keep exploring after a solution is found, then overwriteresultwith every further complete board, which wastes time and, for a puzzle with several solutions, returns the last one instead of the first. - A full board. If there are no empty cells, the walk passes every clue and reaches row 9, so the board is saved as it is.
Testing
For the puzzle whose first row is 53..7...., the returned grid's first row is 534678912 and its last row is 345286179. After the call, the first row of the board you passed in is still 53..7..... Building a [][]byte from strings is easy: []byte("53..7....") converts one row.