Practice › Recursion & Backtracking
Sudoku Solver
Hard · Recursion & Backtracking · Asked at Amazon, Microsoft, Google, Uber
Fill the empty cells (.) so that every row, every column and every 3×3 box contains the digits 1–9 exactly once. If the puzzle has more than one solution, print the one found by filling the empty cells row by row, left to right, trying digits 1 to 9 in increasing order (classic backtracking).
Input
9 lines of 9 characters each (1–9 or .).
Output
The solved grid: 9 lines of 9 digits.
Constraints
- The puzzle has at least one solution
Backtracking: find the next empty cell, try each digit that does not clash with its row, column and box, recurse, and undo on failure. Boolean arrays for rows/columns/boxes make the clash check O(1).
Example 1
Input
53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79
Output
534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179
Example 2
Input
..395.847 .842...6. 596..4231 9..4....2 .3..91..8 845327... ...7.81.. .78.62.9. ...54...3
Output
123956847 784213965 596874231 961485372 237691458 845327619 459738126 378162594 612549783
Hints
- Keep three boolean tables: digit d used in row r, in column c, and in box (r/3)*3 + c/3.
- Fill the empty cells in row-major order. For each, try digits 1..9 that are free in its row, column and box; recurse; undo on failure.
Approach
Classic backtracking. Read the grid and mark the given digits in row, col and box tables. go(pos) (pos = 0..80) skips filled cells; for an empty cell it tries d = 1..9 in increasing order where all three tables allow it, places d, marks the tables, and recurses; if the recursion fails, it unmarks and tries the next digit. The first full grid found is printed — trying digits in increasing order makes the answer unique even if the puzzle has several solutions.
Complexity: Exponential in the number of blanks in the worst case, fast for normal puzzles · O(81) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int g[9][9];
bool rowU[9][10], colU[9][10], boxU[9][10];
bool go(int pos) {
if (pos == 81) return true;
int r = pos / 9, c = pos % 9, b = (r / 3) * 3 + c / 3;
if (g[r][c]) return go(pos + 1);
for (int d = 1; d <= 9; d++) {
if (rowU[r][d] || colU[c][d] || boxU[b][d]) continue;
g[r][c] = d;
rowU[r][d] = colU[c][d] = boxU[b][d] = true;
if (go(pos + 1)) return true;
rowU[r][d] = colU[c][d] = boxU[b][d] = false;
g[r][c] = 0;
}
return false;
}
int main() {
for (int r = 0; r < 9; r++) {
string line;
cin >> line;
for (int c = 0; c < 9; c++) {
g[r][c] = line[c] == '.' ? 0 : line[c] - '0';
if (g[r][c]) rowU[r][g[r][c]] = colU[c][g[r][c]] = boxU[(r / 3) * 3 + c / 3][g[r][c]] = true;
}
}
go(0);
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) cout << g[r][c];
cout << "\n";
}
return 0;
}Python solution
import sys
lines = sys.stdin.read().split()
g = [[0 if ch == "." else int(ch) for ch in lines[r]] for r in range(9)]
row = [[False] * 10 for _ in range(9)]
col = [[False] * 10 for _ in range(9)]
box = [[False] * 10 for _ in range(9)]
for r in range(9):
for c in range(9):
d = g[r][c]
if d:
row[r][d] = col[c][d] = box[(r // 3) * 3 + c // 3][d] = True
empty = [(r, c) for r in range(9) for c in range(9) if g[r][c] == 0]
def go(i):
if i == len(empty):
return True
r, c = empty[i]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if row[r][d] or col[c][d] or box[b][d]:
continue
g[r][c] = d
row[r][d] = col[c][d] = box[b][d] = True
if go(i + 1):
return True
row[r][d] = col[c][d] = box[b][d] = False
g[r][c] = 0
return False
go(0)
print("\n".join("".join(map(str, rw)) for rw in g))Java solution
import java.util.*;
public class Main {
static int[][] g = new int[9][9];
static boolean[][] rowU = new boolean[9][10], colU = new boolean[9][10], boxU = new boolean[9][10];
static boolean go(int pos) {
if (pos == 81) return true;
int r = pos / 9, c = pos % 9, b = (r / 3) * 3 + c / 3;
if (g[r][c] != 0) return go(pos + 1);
for (int d = 1; d <= 9; d++) {
if (rowU[r][d] || colU[c][d] || boxU[b][d]) continue;
g[r][c] = d;
rowU[r][d] = colU[c][d] = boxU[b][d] = true;
if (go(pos + 1)) return true;
rowU[r][d] = colU[c][d] = boxU[b][d] = false;
g[r][c] = 0;
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int r = 0; r < 9; r++) {
String line = sc.next();
for (int c = 0; c < 9; c++) {
g[r][c] = line.charAt(c) == '.' ? 0 : line.charAt(c) - '0';
if (g[r][c] != 0) rowU[r][g[r][c]] = colU[c][g[r][c]] = boxU[(r / 3) * 3 + c / 3][g[r][c]] = true;
}
}
go(0);
StringBuilder sb = new StringBuilder();
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) sb.append(g[r][c]);
sb.append('\n');
}
System.out.print(sb);
}
}