Problem overview
The method SolveSudoku receives a 9 by 9 board as a char[,]. Each cell holds a digit from '1' to '9' or '.' for an empty cell. The method must fill the empty cells 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, and return the solved board. The puzzle is guaranteed to have exactly one solution.
For a typical puzzle that starts with the rows 53..7.... and 6..195..., the solved board begins 534678912 and 672195348. The digits that were given never change, and the dots turn into digits.
Approach: fill cells in order, undo wrong guesses
Solving by pure reasoning is hard to code, but a systematic search is simple. Walk through the cells in reading order: left to right along row 0, then row 1, and so on. At an empty cell, try the digits 1 to 9. A digit is allowed only if the same digit isn't already in that cell's row, column or 3 by 3 box. When a digit is allowed, write it into the board and continue with the next cell. If that path eventually gets stuck, because some later cell has no allowed digit, the recursion returns, the guess is erased, and the next digit is tried. That is backtracking.
Cells that already hold a digit are skipped. When the walk moves past the last cell, which is the same as reaching row 9, every cell has been filled legally, and the board is a solution.
One subtlety: the search undoes every guess while it unwinds, so by the time the recursion finishes, the board is back to its starting state. The solution is therefore copied into a separate array the moment it is found.
Step by step
- Add a field for the answer.
char[,] resultstores the solved board.SolveSudokusets it tonullfirst, so that a previous call can't leave an old answer behind. A non-nullvalue later means "already solved". - Start the search at the top-left cell with
Backtracking(0, 0, board). - Return
resultonce the search ends. - Declare
Backtracking. It takes a row, a column and the board and returns nothing; success is reported throughresult. - Stop early. If
resultis already set, return immediately, so every pending call unwinds without trying more digits. Ifrow == 9, the walk passed the last cell, so save the board withSaveBoardand return. - Compute the next cell, into
new_rowandnew_col, fromGetNextCell, which returns a two-element array. - Skip given digits. If the cell isn't
'.', continue with the next cell and return. - Try digits. A
charloop runs from'1'to'9'. - Check each digit with
IsValid. - Commit the digit by writing it into the board, recurse into the next cell, and then undo it by writing
'.'back. - Write
SaveBoard, which allocatesresultwith the board's dimensions and copies the cells row by row. - Write
GetNextCell. At column 8 it moves to column 0 of the next row, and otherwise it moves one column right. - Write
IsValid. Scan all 81 cells. A cell conflicts when it already holds the digit and shares a row, a column or a box with the target cell.
The solution in C#
class Solution {
public bool IsValid(char[,] board, int row, int col, int val) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
var usedValue = board[i, j] == val;
var sameRowOrCol = row == i || col == j;
var sameRowBox = row / 3 == i / 3;
var sameColBox = col / 3 == j / 3;
var sameBox = sameRowBox && sameColBox;
if (usedValue && (sameRowOrCol || sameBox)) {
return false;
}
}
}
return true;
}
public int[] GetNextCell(int row, int col) {
if (col == 8) {
return new int[]{row + 1, 0};
}
return new int[]{row, col + 1};
}
public void SaveBoard(char[,] board) {
this.result = new char[board.GetLength(0), board.GetLength(1)];
for (int i = 0; i < board.GetLength(0); i++) {
Array.Copy(board, i * board.GetLength(1), this.result, i * board.GetLength(1), board.GetLength(1));
}
}
public void Backtracking(int row, int col, char[,] board) {
if (this.result != null) {
return;
}
if (row == 9) {
SaveBoard(board);
return;
}
int new_row = GetNextCell(row, col)[0];
int new_col = GetNextCell(row, col)[1];
if (board[row, col] != '.') {
this.Backtracking(new_row, new_col, board);
return;
}
for (char val = '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] = '.';
}
}
}
char[,] result;
public char[,] SolveSudoku(char[,] board) {
this.result = null;
this.Backtracking(0, 0, board);
return this.result;
}
}
The C# details worth a closer look:
- Two-dimensional arrays. A
char[,]is indexedboard[row, col], with a comma. The jagged formboard[row][col]belongs tochar[][]and doesn't compile on a rectangular array.GetLength(0)is the number of rows andGetLength(1)the number of columns. - Characters are numbers. A
charconverts implicitly tointby its character code:'5'is 53, not 5. InIsValid, thecharargumentvalis widened to anint, andboard[i, j] == valcompares the character code of the cell with it, so the comparison is correct. To get the digit's value, subtract:'5' - '0'is 5. - A
charloop variable.for (char val = '1'; val <= '9'; ++val)works becausecharsupports++and comparison, and the digits '1' to '9' have consecutive codes. Array.Copyon 2D arrays. It treats a multidimensional array as one flat run of cells in row-major order, so rowistarts at offseti * board.GetLength(1)in both arrays, and copyingGetLength(1)cells copies exactly one row.- Allocation.
new char[9, 9]creates all 81 cells at once, filled with the character code 0. It makes a new array: the caller'sboardand the returnedresultare different objects. var. EachvarinIsValidis inferred asboolfrom its right-hand side, androw / 3uses integer division, which maps rows 0 to 2 to 0, rows 3 to 5 to 1 and rows 6 to 8 to 2.- Naming. The names
new_rowandnew_colfollow the lesson; idiomatic C# would writenewRowandnewColfor local variables.
Complexity
Time: exponential in the worst case. With E empty cells, there are up to 9 to the power E ways to fill them, and the rules cut most branches early. Each IsValid call costs a constant number of steps, 81 cell checks. For a standard 9 by 9 puzzle, the search is fast in practice, because most guesses fail within a few cells.
Space: constant besides the answer. The recursion is at most 81 calls deep, the board is modified in place, and the saved result is one more 9 by 9 array.
Edge cases and common mistakes
- Forgetting the undo. Without
board[row, col] = '.', a failed guess stays on the board and blocks the correct digit for other cells. - Returning the board instead of a copy. The undo step erases every guess while the recursion unwinds, so the board itself ends up as the original puzzle again. The copy in
SaveBoardkeeps the solution. - Comparing with a number. Checking a cell against
5instead of'5'never matches, because the cell holds the character code 53. - Overwriting given digits. The
!= '.'check must come before the digit loop. - Not stopping after the first solution. The
result != nullcheck ends the search at once. Without it, the search would keep trying digits after a solution was found. - Box arithmetic. Two cells share a box only when both
row / 3 == i / 3andcol / 3 == j / 3hold. Testing only one of them would reject digits in the same band of three rows but a different box. - The target cell itself. It is empty during the check, so it can't count as a conflict.
Testing
- For the puzzle with first row
53..7...., the solved first row is534678912and the last row is345286179. - After the call, the board you passed in holds the original puzzle again, and the returned array holds the solution.
- A puzzle that is already complete comes back unchanged.