Problem overview
The method solveSudoku receives a 9x9 board as a string[][]. Each cell is a digit character '1' to '9' or '.' for an empty cell. The method fills every empty cell so that each digit 1 to 9 appears exactly once in every row, every column and every one of the nine 3x3 boxes, and returns the finished board. The input is guaranteed to have exactly one solution.
In the example, the first row 5 3 . . 7 . . . . becomes 5 3 4 6 7 8 9 1 2. Notice that cells hold strings, not numbers, so the digit 5 is the string "5".
Approach: guess, check, undo
A person solves Sudoku by logic. A program can do something simpler: walk through the cells in order and, at each empty one, try the digits 1 to 9. A digit is allowed only if it does not clash with the digits already in that row, column and box. After placing a digit, move on to the next cell. If a later cell has no allowed digit at all, an earlier guess was wrong: return, erase the guess, and try the next digit there.
This is backtracking, with the same shape as other lessons in this chapter: place a choice, recurse, remove the choice. Rejecting a digit as soon as it clashes cuts off enormous parts of the search, since a wrong guess is usually discovered within a few cells.
The cells are visited in row-major order: left to right along a row, then on to the next row. Reaching row 9, one past the last row, means every cell was filled legally, so the board is a solution.
The lesson stores the solution in a field, result, rather than returning it up the recursion. Once result is set, every pending call sees it and returns at once.
Step by step
- Declare the field
result: string[][] | null = null, and reset it tonullat the start ofsolveSudoku. The recursive helpers share it throughthis. - Start the search at the top-left cell with
this.backtracking(0, 0, board). - Return
this.result. - Declare
backtrackingwithrow,colandboard. Each call deals with one cell. - Stop early. If
this.resultis already set, return. Ifrow == 9, callthis.saveBoard(board)and return. - Find the next cell with
this.getNextCell(row, col), destructured intonewRowandnewCol. - Skip given cells. If the cell is not
'.', it is a clue: continue with the next cell and return. - Try each digit
valfrom 1 to 9. - Check the digit with
this.isValid(board, row, col, String(val)). The board holds strings, so the number is converted. - Place it with
board[row][col] = String(val). - Recurse to the next cell.
- Undo by writing
'.'back, so the board is as it was before the next digit is tried. - Write
saveBoard, which setsthis.resultto an empty array and pushes a copy of each row,[...board[i]]. - Write
getNextCell. At column 8 the next cell is[row + 1, 0]; otherwise it is[row, col + 1]. From the last cell this gives row 9, the signal that the board is complete. - Write
isValid. Visit all 81 cells withiandj. For each, compute whether it holds the digit, whether it shares a row or column with the target, and whether it shares the target's box. Box membership comparesMath.floor(row / 3)withMath.floor(i / 3), and the same for columns. If a cell holds the digit and shares a row, column or box, returnfalse. If no cell does, returntrue.
The solution in TypeScript
class Solution {
isValid(board: string[][], row: number, col: number, val: string): boolean {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const usedValue = board[i][j] == val;
const sameRowOrCol = row == i || col == j;
const sameRowBox = Math.floor(row / 3) == Math.floor(i / 3);
const sameColBox = Math.floor(col / 3) == Math.floor(j / 3);
const sameBox = sameRowBox && sameColBox;
if (usedValue && (sameRowOrCol || sameBox)) {
return false;
}
}
}
return true;
}
getNextCell(row: number, col: number): number[] {
if (col == 8) {
return [row + 1, 0];
}
return [row, col + 1];
}
saveBoard(board: string[][]) {
this.result = [];
for (let i = 0; i < board.length; i++) {
this.result.push([...board[i]]);
}
}
backtracking(row: number, col: number, board: string[][]) {
if (this.result !== null) {
return;
}
if (row == 9) {
this.saveBoard(board);
return;
}
let [newRow, newCol] = this.getNextCell(row, col);
if (board[row][col] != '.') {
this.backtracking(newRow, newCol, board);
return;
}
for (let val = 1; val <= 9; ++val) {
if (this.isValid(board, row, col, String(val))) {
board[row][col] = String(val);
this.backtracking(newRow, newCol, board);
board[row][col] = '.';
}
}
}
result: string[][] | null = null;
solveSudoku(board: string[][]): string[][] {
this.result = null;
this.backtracking(0, 0, board);
return this.result;
}
}
TypeScript details worth knowing:
- Why
saveBoardcopies. The board keeps changing as the recursion unwinds and undoes its guesses. By the timesolveSudokureturns, the originalboardis back to its starting state. The copy, made with spread on each row, is what keeps the solution. A single[...board]would not be enough: it copies the outer array, but the rows would still be shared withboard. - Digits are strings. The comparison
board[i][j] == valworks because both sides are strings. Comparing"5"with the number 5 using==would also be true in JavaScript, since==converts types, but that habit hides mistakes, so the lesson converts withString(val)instead. - Array destructuring.
let [newRow, newCol] = this.getNextCell(row, col)unpacks the two-element array the function returns. - The union type.
string[][] | nullsays the field holds either a board ornull. This compiles with strict mode off, so returningthis.resultasstring[][]is accepted. The type is erased at run time. - Early return from a
voidmethod. A barereturn;leaves the method, which is how the "already solved" check unwinds every pending call.
Complexity
Time: exponential in the number of empty cells. In theory each empty cell has up to 9 candidates, so there are at most 9 to the power of the number of empty cells ways to fill the board. Pruning with isValid makes ordinary puzzles solve in a tiny fraction of that: the example solves in a few milliseconds. Each isValid call scans 81 cells, which is a constant.
Space: O(1) for a 9x9 board, since the recursion is at most 81 calls deep and the board has a fixed size. The result is one extra copy of the board.
Edge cases and common mistakes
- Forgetting the undo. If
board[row][col]keeps the failed guess, later cells are checked against digits that do not belong there, and valid solutions are missed. - Overwriting clues. The check
board[row][col] != '.'comes before the digit loop. Without it, given digits would be replaced. - Returning the board itself. The undo step empties the board again as the recursion finishes, so the answer must be copied into
resultat the moment of success. - Not stopping after a solution. Without the
this.result !== nullcheck, the loops keep trying digits after the solution has been found. The undo steps do not changeresult, but the extra search is wasted work. - Box arithmetic. Dividing a row index by 3 with
/gives a fraction in TypeScript, for example4 / 3is about 1.33, soMath.flooris needed to get the box number. Without it, almost no cells would count as sharing a box. - A board with no solution. The search tries everything and ends with
resultstillnull, sosolveSudokureturnsnull. The lesson's boards always have a solution.
Testing
- The example board, whose rows begin
53..7....and6..195..., gives a board whose rows begin534678912and672195348and end with345286179. - The result's rows, columns and boxes each hold the digits 1 to 9 once.
- After the call, the input board is back to its starting state, and the returned board is a different object.