Sudoku Solver
Sudoku Solver is a hard recursion & backtracking problem solved with the 2d matrix backtracking pattern.
The best approach, optimal (backtracking with constraint tables), runs in O(9^e) time and O(e) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (backtracking with scan checks) up.
Problem
Fill in the empty cells of a 9 x 9 Sudoku board so that the puzzle is solved. Empty cells are marked with '.'.
A solved board has each digit 1-9 exactly once in every row, in every column, and in each of the nine 3 x 3 boxes. The input always has exactly one solution. Modify board in place; nothing is returned.
Examples
Example 1
- Input
board = [[".","5","9","4",".",".","1","8","."],[".",".","4","8",".",".",".",".","."],["3","8",".","5",".",".",".",".","2"],["8","1","3",".",".","6",".",".","7"],[".","4",".",".","8","3","9",".","6"],["5","9","6","2",".",".","3",".","8"],["9",".","5",".","2",".",".",".","."],["4",".","7",".","1",".","6","9","."],[".","3",".",".","9","5","7",".","4"]]- Output
[["6","5","9","4","7","2","1","8","3"],["2","7","4","8","3","1","5","6","9"],["3","8","1","5","6","9","4","7","2"],["8","1","3","9","5","6","2","4","7"],["7","4","2","1","8","3","9","5","6"],["5","9","6","2","4","7","3","1","8"],["9","6","5","7","2","4","8","3","1"],["4","2","7","3","1","8","6","9","5"],["1","3","8","6","9","5","7","2","4"]]- Why
- 40 cells are given; the board is filled in place so every row, column and 3 x 3 box holds 1-9 once.
Example 2
- Input
board = [[".",".",".","1",".",".",".",".","."],[".",".",".",".",".",".","2","4","1"],[".",".",".","5","6","7",".",".","3"],[".","7","5","8","3",".","9",".","."],[".",".",".",".",".","4",".",".","."],[".","8","3","2",".","9",".",".","."],["5",".",".","9","2",".",".",".","4"],[".","9","2",".","7",".",".",".","6"],[".",".",".","6","8",".","3",".","9"]]- Output
[["8","3","9","1","4","2","7","6","5"],["7","5","6","3","9","8","2","4","1"],["2","1","4","5","6","7","8","9","3"],["4","7","5","8","3","6","9","1","2"],["9","2","1","7","5","4","6","3","8"],["6","8","3","2","1","9","4","5","7"],["5","6","8","9","2","3","1","7","4"],["3","9","2","4","7","1","5","8","6"],["1","4","7","6","8","5","3","2","9"]]- Why
- Only 30 clues, so the solver has to guess and undo several times before it reaches the unique solution.
Constraints
board.length == 9andboard[i].length == 9board[i][j]is a digit'1'-'9'or'.'for an empty cell.- The given puzzle has exactly one solution.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (backtracking with scan checks) | O(9^e · 27) | O(e) |
| Optimal (backtracking with constraint tables) | O(9^e) | O(e) |
1Brute force (backtracking with scan checks)
O(9^e · 27)Each of the e empty cells may try 9 digits, and every try costs a 27-cell scan (plus a scan for the next empty cell). Real puzzles prune far earlier.O(e)Recursion depth is at most the number of empty cells (at most 81).Find the next empty cell, try digits 1 to 9, and check each one by scanning its row, column and 3 x 3 box. Place a valid digit and recurse; if the recursion fails, clear the cell again. When no empty cell is left, the board is solved.
- solve(): scan for the first '.' cell. If there is none, return true.
- For each digit d: if isValid(r, c, d), set the cell to d; if solve() returns true, return true; otherwise reset the cell to '.'.
- If no digit worked, return false.
- isValid checks the 9 cells of the row, the 9 of the column and the 9 of the box.
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] != '.') {
continue;
}
for (char d = '1'; d <= '9'; d++) {
if (isValid(board, r, c, d)) {
board[r][c] = d;
if (solve(board)) {
return true;
}
board[r][c] = '.';
}
}
return false;
}
}
return true;
}
private boolean isValid(char[][] board, int r, int c, char d) {
int br = (r / 3) * 3, bc = (c / 3) * 3;
for (int k = 0; k < 9; k++) {
if (board[r][k] == d || board[k][c] == d) {
return false;
}
if (board[br + k / 3][bc + k % 3] == d) {
return false;
}
}
return true;
}
}class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
self.solve(board)
def solve(self, board: List[List[str]]) -> bool:
for r in range(9):
for c in range(9):
if board[r][c] != '.':
continue
for d in "123456789":
if self.isValid(board, r, c, d):
board[r][c] = d
if self.solve(board):
return True
board[r][c] = '.'
return False
return True
def isValid(self, board: List[List[str]], r: int, c: int, d: str) -> bool:
br, bc = (r // 3) * 3, (c // 3) * 3
for k in range(9):
if board[r][k] == d or board[k][c] == d:
return False
if board[br + k // 3][bc + k % 3] == d:
return False
return Trueclass Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}
private:
bool solve(vector<vector<char>>& board) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] != '.') continue;
for (char d = '1'; d <= '9'; d++) {
if (isValid(board, r, c, d)) {
board[r][c] = d;
if (solve(board)) return true;
board[r][c] = '.';
}
}
return false;
}
}
return true;
}
bool isValid(vector<vector<char>>& board, int r, int c, char d) {
int br = (r / 3) * 3, bc = (c / 3) * 3;
for (int k = 0; k < 9; k++) {
if (board[r][k] == d || board[k][c] == d) return false;
if (board[br + k / 3][bc + k % 3] == d) return false;
}
return true;
}
};function solveSudoku(board) {
solve(board);
}
function solve(board) {
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] !== '.') continue;
for (let x = 1; x <= 9; x++) {
const d = String(x);
if (isValid(board, r, c, d)) {
board[r][c] = d;
if (solve(board)) return true;
board[r][c] = '.';
}
}
return false;
}
}
return true;
}
function isValid(board, r, c, d) {
const br = Math.floor(r / 3) * 3, bc = Math.floor(c / 3) * 3;
for (let k = 0; k < 9; k++) {
if (board[r][k] === d || board[k][c] === d) return false;
if (board[br + Math.floor(k / 3)][bc + (k % 3)] === d) return false;
}
return true;
}2Optimal (backtracking with constraint tables)
O(9^e)Same search tree as the brute force in the worst case, but each try is O(1) instead of a 27-cell scan.O(e)The tables are fixed size (3 x 9 x 10); the empty-cell list and the recursion are at most 81 deep.Precompute which digits are already used in each row, column and box with three boolean tables, and collect the empty cells into a list once. Backtrack over that list by index: a placement check is three lookups, placing or removing a digit updates three flags, and no time is spent rescanning for the next empty cell.
- Fill row[9][10], col[9][10], box[9][10] from the given digits and list the empty cells.
- solve(k): if k == empties.size(), return true. Take cell (r, c) = empties[k] and b = (r / 3) * 3 + c / 3.
- For d in 1..9 not used in row[r], col[c] or box[b]: mark it, write it, and if solve(k + 1) succeeds return true; otherwise unmark it.
- If no digit fits, reset the cell to '.' and return false.
class Solution {
private final boolean[][] row = new boolean[9][10];
private final boolean[][] col = new boolean[9][10];
private final boolean[][] box = new boolean[9][10];
private final List<int[]> empties = new ArrayList<>();
public void solveSudoku(char[][] board) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == '.') {
empties.add(new int[] { r, c });
} else {
int d = board[r][c] - '0';
row[r][d] = true;
col[c][d] = true;
box[(r / 3) * 3 + c / 3][d] = true;
}
}
}
solve(board, 0);
}
private boolean solve(char[][] board, int k) {
if (k == empties.size()) {
return true;
}
int r = empties.get(k)[0], c = empties.get(k)[1], b = (r / 3) * 3 + c / 3;
for (int d = 1; d <= 9; d++) {
if (row[r][d] || col[c][d] || box[b][d]) {
continue;
}
row[r][d] = col[c][d] = box[b][d] = true;
board[r][c] = (char) ('0' + d);
if (solve(board, k + 1)) {
return true;
}
row[r][d] = col[c][d] = box[b][d] = false;
}
board[r][c] = '.';
return false;
}
}class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
self.row = [[False] * 10 for _ in range(9)]
self.col = [[False] * 10 for _ in range(9)]
self.box = [[False] * 10 for _ in range(9)]
self.empties = []
for r in range(9):
for c in range(9):
if board[r][c] == '.':
self.empties.append((r, c))
else:
d = int(board[r][c])
self.row[r][d] = True
self.col[c][d] = True
self.box[(r // 3) * 3 + c // 3][d] = True
self.solve(board, 0)
def solve(self, board: List[List[str]], k: int) -> bool:
if k == len(self.empties):
return True
r, c = self.empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if self.row[r][d] or self.col[c][d] or self.box[b][d]:
continue
self.row[r][d] = self.col[c][d] = self.box[b][d] = True
board[r][c] = str(d)
if self.solve(board, k + 1):
return True
self.row[r][d] = self.col[c][d] = self.box[b][d] = False
board[r][c] = '.'
return Falseclass Solution {
bool row[9][10] = {}, col[9][10] = {}, box[9][10] = {};
vector<pair<int, int>> empties;
public:
void solveSudoku(vector<vector<char>>& board) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == '.') {
empties.push_back({r, c});
} else {
int d = board[r][c] - '0';
row[r][d] = col[c][d] = box[(r / 3) * 3 + c / 3][d] = true;
}
}
}
solve(board, 0);
}
private:
bool solve(vector<vector<char>>& board, int k) {
if (k == (int)empties.size()) return true;
int r = empties[k].first, c = empties[k].second, b = (r / 3) * 3 + c / 3;
for (int d = 1; d <= 9; d++) {
if (row[r][d] || col[c][d] || box[b][d]) continue;
row[r][d] = col[c][d] = box[b][d] = true;
board[r][c] = (char)('0' + d);
if (solve(board, k + 1)) return true;
row[r][d] = col[c][d] = box[b][d] = false;
}
board[r][c] = '.';
return false;
}
};function solveSudoku(board) {
const row = Array.from({ length: 9 }, () => new Array(10).fill(false));
const col = Array.from({ length: 9 }, () => new Array(10).fill(false));
const box = Array.from({ length: 9 }, () => new Array(10).fill(false));
const empties = [];
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] === '.') {
empties.push([r, c]);
} else {
const d = Number(board[r][c]);
row[r][d] = col[c][d] = box[Math.floor(r / 3) * 3 + Math.floor(c / 3)][d] = true;
}
}
}
const solve = (k) => {
if (k === empties.length) return true;
const [r, c] = empties[k];
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
for (let d = 1; d <= 9; d++) {
if (row[r][d] || col[c][d] || box[b][d]) continue;
row[r][d] = col[c][d] = box[b][d] = true;
board[r][c] = String(d);
if (solve(k + 1)) return true;
row[r][d] = col[c][d] = box[b][d] = false;
}
board[r][c] = '.';
return false;
};
solve(0);
}Edge cases to test
- A board with only one empty cell
- Very few clues, where many guesses must be undone
- An empty cell whose candidates are cut down only by its box, not its row or column
Hints
Hint 1
Try every digit in the first empty cell, keep the ones that do not clash with its row, column and box, and recurse. If the recursion fails, erase the digit and try the next one.
Hint 2
Checking a placement by scanning 27 cells is slow. Keep three tables row[r][d], col[c][d], box[b][d] so the check is O(1). The box index is (r / 3) * 3 + c / 3.
Hint 3
Return true all the way up as soon as the last cell is filled, so the solved board is not undone.
FAQ
What is the best time complexity for Sudoku Solver?
Optimal (backtracking with constraint tables) runs in O(9^e) time and O(e) extra space. Same search tree as the brute force in the worst case, but each try is O(1) instead of a 27-cell scan.
Which pattern does Sudoku Solver use?
It is a recursion & backtracking problem that uses the 2d matrix backtracking pattern. Other problems with the same pattern: Word Search, Robot Room Cleaner.
Is there a brute force solution for Sudoku Solver?
Yes. Brute force (backtracking with scan checks) takes O(9^e · 27) time and O(e) space. Find the next empty cell, try digits 1 to 9, and check each one by scanning its row, column and 3 x 3 box.
Which edge cases should I test for Sudoku Solver?
A board with only one empty cell; Very few clues, where many guesses must be undone; An empty cell whose candidates are cut down only by its box, not its row or column.