These are the notes for DSA episode 34, LeetCode 37, a hard backtracking problem that becomes easy once you have done N-Queens. Fill a 9 x 9 Sudoku so that every row, every column and every 3 x 3 box contains the digits 1 to 9 exactly once. The obvious way writes every digit in every empty square and checks the full grid at the end: it solves a grid with 6 blanks, but the real puzzle has 51 blanks, which means up to 9^51 grids, and it times out. The fix is the same as last episode: check each digit the moment it is written, using three boolean tables (rows, columns, boxes) and the box number (r / 3) * 3 + c / 3, and return true all the way up as soon as the grid is full. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
Every morning at the chai stall, Dadaji opens the newspaper to the Sudoku: a 9 x 9 grid with about 30 digits printed and the rest empty. When he can't work out a square for sure, he pencils in a guess that doesn't break any rule yet, and carries on. Ten squares later he is stuck (some square has no digit that fits), so he erases back to his guess and tries the next digit there. That is backtracking, done with a pencil and an eraser.
| At the chai stall | In the code |
|---|---|
| The newspaper grid | char[][] b, 9 x 9 |
| A printed digit (a "given") | a digit '1'..'9' already in b at the start |
| An empty square | '.' |
| Pencilling in a guess | b[r][c] = (char) ('0' + d) and marking the tables |
| "Is 4 already in this row/column/box?" | row[r][4] \|\| col[c][4] \|\| box[bx][4] |
| Erasing back to the guess | b[r][c] = '.' and un-marking, then return false |
Problem statement
Sudoku Solver (LeetCode 37). Write a program to solve a Sudoku puzzle by filling the empty cells. A solution must satisfy:
- Each of the digits 1-9 occurs exactly once in each row.
- Each of the digits 1-9 occurs exactly once in each column.
- Each of the digits 1-9 occurs exactly once in each of the nine 3 x 3 sub-boxes.
The '.' character marks empty cells. The board is changed in place. LeetCode guarantees exactly one solution. In the video our solveSudoku returns boolean, so we can also test a grid that already breaks the rules (false) and a grid that is already solved (true).
53..7.... 534678912
6..195... 672195348
.98....6. 198342567
8...6...3 859761423
4..8.3..1 → 426853791
7...2...6 713924856
.6....28. 961537284
...419..5 287419635
....8..79 345286179
Brute force: every digit in every blank, check at the end
Number the squares k = 0 .. 80 in reading order: square k is row k / 9, column k % 9. For an empty square try '1' to '9' and recurse to k + 1; when k == 81 the grid is full, and only then check every rule.
import java.util.*;
public class Main {
static char[][] grid(String... rows) {
char[][] b = new char[9][];
for (int i = 0; i < 9; i++) b[i] = rows[i].toCharArray();
return b;
}
static void show(char[][] b) {
for (char[] r : b) System.out.println(new String(r));
}
static boolean brute(char[][] b, int k) {
if (k == 81) return valid(b);
int r = k / 9, c = k % 9;
if (b[r][c] != '.') return brute(b, k + 1);
for (char d = '1'; d <= '9'; d++) {
b[r][c] = d;
if (brute(b, k + 1)) return true;
}
b[r][c] = '.';
return false;
}
static boolean valid(char[][] b) {
for (int i = 0; i < 9; i++) {
boolean[] R = new boolean[10], C = new boolean[10], X = new boolean[10];
for (int j = 0; j < 9; j++) {
int a = b[i][j] - '0', e = b[j][i] - '0';
int x = b[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3] - '0';
if (R[a] || C[e] || X[x]) return false;
R[a] = C[e] = X[x] = true;
}
}
return true;
}
public static void main(String[] args) {
char[][] b = grid("53..78912", "672195348", "198342567", "859761423", "4268.3791",
"713924856", ".61537284", "287419635", "3452861..");
System.out.println(brute(b, 0));
show(b);
}
}
Real output on a grid with only 6 empty squares:
true
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
Now Dadaji's real puzzle, with 51 empty squares:
import java.util.*;
public class Main {
static char[][] grid(String... rows) {
char[][] b = new char[9][];
for (int i = 0; i < 9; i++) b[i] = rows[i].toCharArray();
return b;
}
static void show(char[][] b) {
for (char[] r : b) System.out.println(new String(r));
}
static boolean brute(char[][] b, int k) {
if (k == 81) return valid(b);
int r = k / 9, c = k % 9;
if (b[r][c] != '.') return brute(b, k + 1);
for (char d = '1'; d <= '9'; d++) {
b[r][c] = d;
if (brute(b, k + 1)) return true;
}
b[r][c] = '.';
return false;
}
static boolean valid(char[][] b) {
for (int i = 0; i < 9; i++) {
boolean[] R = new boolean[10], C = new boolean[10], X = new boolean[10];
for (int j = 0; j < 9; j++) {
int a = b[i][j] - '0', e = b[j][i] - '0';
int x = b[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3] - '0';
if (R[a] || C[e] || X[x]) return false;
R[a] = C[e] = X[x] = true;
}
}
return true;
}
public static void main(String[] args) {
char[][] b = grid("53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
"7...2...6", ".6....28.", "...419..5", "....8..79");
long t0 = System.nanoTime();
System.out.println(brute(b, 0));
System.out.println((System.nanoTime() - t0) / 1000000 + " ms");
}
}
Real result: Time Limit Exceeded.
Why the brute force fails
| Empty squares | Full grids it can build |
|---|---|
| 6 | 9^6 = 5,31,441 (5.3 lakh) |
| 15 | 9^15 ≈ 2 × 10^14 (2 lakh crore) |
| 51 | 9^51 ≈ 4.6 × 10^48 (a 49-digit number) |
The first two empty squares of the puzzle are (0,2) and (0,3). Brute writes '1' in both: two 1s in row 0, already broken. But it fills 49 more squares, in every combination, before it checks. The same mistake as the N-Queens brute force: build everything, then check.
The key insight: check while placing, in O(1)
Keep three tables of booleans:
| Table | Meaning |
|---|---|
row[r][d] |
row r already contains digit d |
col[c][d] |
column c already contains d |
box[bx][d] |
3 x 3 box number bx already contains d |
Checking a digit is then one line and O(1):
if (row[r][d] || col[c][d] || box[bx][d]) continue;
If the digit is allowed: write it, mark all three tables, recurse. If that call fails, erase the square and un-mark the tables (the eraser). And unlike N-Queens, where we wanted every answer, Sudoku has one answer: the moment a recursive call returns true, return true at once, without erasing anything.
Before solving, mark every printed digit in the tables. If a printed digit is already in its row, column or box, the puzzle breaks the rules and has no solution: return false immediately.
The box number
Integer division by 3 turns a row into a box row (0, 1, 2) and a column into a box column (0, 1, 2). Number the boxes in reading order:
bx = (r / 3) * 3 + c / 3
0 0 0 | 1 1 1 | 2 2 2
0 0 0 | 1 1 1 | 2 2 2
0 0 0 | 1 1 1 | 2 2 2
------+-------+------
3 3 3 | 4 4 4 | 5 5 5
3 3 3 | 4 4 4 | 5 5 5
3 3 3 | 4 4 4 | 5 5 5
------+-------+------
6 6 6 | 7 7 7 | 8 8 8
6 6 6 | 7 7 7 | 8 8 8
6 6 6 | 7 7 7 | 8 8 8
Example: square (4, 7): 4 / 3 = 1, 7 / 3 = 2, 1 * 3 + 2 = 5, the middle-right box. Without the * 3, r / 3 + c / 3 gives box 1 (top-middle) and box 3 (middle-left) the same number, so two boxes share one table.
The search on Dadaji's puzzle
| Step | What happens |
|---|---|
(0,2) |
row 0 has 3 5 7, column 2 has 8, box 0 has 3 5 6 8 9 → allowed 1, 2, 4 → try 1 |
(0,3), (0,5), (0,6), (0,7) |
2, 4, 8, 9 |
(0,8) |
row 0 is missing only 6, but column 8 already has a 6 → no digit fits: dead end |
| Back up | (0,7) is erased, (0,6) tries its next allowed digit, 9 |
| ... | a few thousand calls later, k == 81: return true all the way up |
The optimal solution in Java
import java.util.*;
public class Main {
static char[][] grid(String... rows) {
char[][] b = new char[9][];
for (int i = 0; i < 9; i++) b[i] = rows[i].toCharArray();
return b;
}
static void show(char[][] b) {
for (char[] r : b) System.out.println(new String(r));
}
static boolean[][] row, col, box;
static boolean solve(char[][] b, int k) {
if (k == 81) return true;
int r = k / 9, c = k % 9;
if (b[r][c] != '.') return solve(b, k + 1);
int bx = (r / 3) * 3 + c / 3;
for (int d = 1; d <= 9; d++) {
if (row[r][d] || col[c][d] || box[bx][d]) continue;
b[r][c] = (char) ('0' + d);
row[r][d] = col[c][d] = box[bx][d] = true;
if (solve(b, k + 1)) return true;
b[r][c] = '.';
row[r][d] = col[c][d] = box[bx][d] = false;
}
return false;
}
static boolean solveSudoku(char[][] b) {
row = new boolean[9][10]; col = new boolean[9][10]; box = new boolean[9][10];
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (b[r][c] != '.') {
int d = b[r][c] - '0', bx = (r / 3) * 3 + c / 3;
if (row[r][d] || col[c][d] || box[bx][d]) return false;
row[r][d] = col[c][d] = box[bx][d] = true;
}
return solve(b, 0);
}
public static void main(String[] args) {
char[][] b = grid("53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
"7...2...6", ".6....28.", "...419..5", "....8..79");
System.out.println(solveSudoku(b));
show(b);
char[][] h = grid("8........", "..36.....", ".7..9.2..", ".5...7...", "....457..",
"...1...3.", "..1....68", "..85...1.", ".9....4..");
long t0 = System.nanoTime();
System.out.println(solveSudoku(h) + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
show(h);
char[][] x = grid("55.......", ".........", ".........", ".........", ".........",
".........", ".........", ".........", ".........");
System.out.println(solveSudoku(x));
char[][] s = grid("534678912", "672195348", "198342567", "859761423", "426853791",
"713924856", "961537284", "287419635", "345286179");
System.out.println(solveSudoku(s));
}
}
Real output:
true
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
true, 2 ms
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452
false
true
The second puzzle is the one Finnish mathematician Arto Inkala called "the world's hardest Sudoku" (2012). Plain backtracking with O(1) checks solves it in milliseconds (about 72,000 calls). The grid with two 5s in row 0 returns false, and the solved grid returns true with nothing to do.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
bool rowU[9][10], colU[9][10], boxU[9][10];
bool solve(vector<string>& b, int k) {
if (k == 81) return true;
int r = k / 9, c = k % 9;
if (b[r][c] != '.') return solve(b, k + 1);
int bx = (r / 3) * 3 + c / 3;
for (int d = 1; d <= 9; d++) {
if (rowU[r][d] || colU[c][d] || boxU[bx][d]) continue;
b[r][c] = char('0' + d);
rowU[r][d] = colU[c][d] = boxU[bx][d] = true;
if (solve(b, k + 1)) return true;
b[r][c] = '.';
rowU[r][d] = colU[c][d] = boxU[bx][d] = false;
}
return false;
}
bool solveSudoku(vector<string>& b) {
memset(rowU, 0, sizeof rowU); memset(colU, 0, sizeof colU); memset(boxU, 0, sizeof boxU);
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (b[r][c] != '.') {
int d = b[r][c] - '0', bx = (r / 3) * 3 + c / 3;
if (rowU[r][d] || colU[c][d] || boxU[bx][d]) return false;
rowU[r][d] = colU[c][d] = boxU[bx][d] = true;
}
return solve(b, 0);
}
int main() {
vector<string> b = {"53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
"7...2...6", ".6....28.", "...419..5", "....8..79"};
cout << boolalpha << solveSudoku(b) << '\n';
for (auto& row : b) cout << row << '\n';
vector<string> x = {"55.......", ".........", ".........", ".........", ".........",
".........", ".........", ".........", "........."};
cout << solveSudoku(x) << '\n';
}
Output: true, the solved grid, then false.
The same solution in Python
def solve_sudoku(b):
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):
if b[r][c] != ".":
d, bx = int(b[r][c]), (r // 3) * 3 + c // 3
if row[r][d] or col[c][d] or box[bx][d]:
return False
row[r][d] = col[c][d] = box[bx][d] = True
def solve(k):
if k == 81:
return True
r, c = divmod(k, 9)
if b[r][c] != ".":
return solve(k + 1)
bx = (r // 3) * 3 + c // 3
for d in range(1, 10):
if row[r][d] or col[c][d] or box[bx][d]:
continue
b[r][c] = str(d)
row[r][d] = col[c][d] = box[bx][d] = True
if solve(k + 1):
return True
b[r][c] = "."
row[r][d] = col[c][d] = box[bx][d] = False
return False
return solve(0)
puzzle = ["53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
"7...2...6", ".6....28.", "...419..5", "....8..79"]
b = [list(s) for s in puzzle]
print(solve_sudoku(b))
for row in b:
print("".join(row))
print(solve_sudoku([list("55.......")] + [list(".........") for _ in range(8)]))
Output: True, the solved grid, then False.
Three real bugs
Bug 1: bx = r / 3 + c / 3
import java.util.*;
public class Main {
static char[][] grid(String... rows) {
char[][] b = new char[9][];
for (int i = 0; i < 9; i++) b[i] = rows[i].toCharArray();
return b;
}
static void show(char[][] b) {
for (char[] r : b) System.out.println(new String(r));
}
static boolean[][] row, col, box;
static boolean solve(char[][] b, int k) {
if (k == 81) return true;
int r = k / 9, c = k % 9;
if (b[r][c] != '.') return solve(b, k + 1);
int bx = r / 3 + c / 3;
for (int d = 1; d <= 9; d++) {
if (row[r][d] || col[c][d] || box[bx][d]) continue;
b[r][c] = (char) ('0' + d);
row[r][d] = col[c][d] = box[bx][d] = true;
if (solve(b, k + 1)) return true;
b[r][c] = '.';
row[r][d] = col[c][d] = box[bx][d] = false;
}
return false;
}
static boolean solveSudoku(char[][] b) {
row = new boolean[9][10]; col = new boolean[9][10]; box = new boolean[9][10];
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (b[r][c] != '.') {
int d = b[r][c] - '0', bx = r / 3 + c / 3;
if (row[r][d] || col[c][d] || box[bx][d]) return false;
row[r][d] = col[c][d] = box[bx][d] = true;
}
return solve(b, 0);
}
public static void main(String[] args) {
char[][] b = grid("53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
"7...2...6", ".6....28.", "...419..5", "....8..79");
System.out.println(solveSudoku(b));
show(b);
}
}
Real output: false, and the puzzle unchanged. Boxes 1 and 3 share one table, and the printed 7 in box 1 and the printed 7 in box 3 now "clash", so solveSudoku gives up before solving.
Bug 2: ignoring the true that solve returns
import java.util.*;
public class Main {
static char[][] grid(String... rows) {
char[][] b = new char[9][];
for (int i = 0; i < 9; i++) b[i] = rows[i].toCharArray();
return b;
}
static void show(char[][] b) {
for (char[] r : b) System.out.println(new String(r));
}
static boolean[][] row, col, box;
static boolean solve(char[][] b, int k) {
if (k == 81) return true;
int r = k / 9, c = k % 9;
if (b[r][c] != '.') return solve(b, k + 1);
int bx = (r / 3) * 3 + c / 3;
for (int d = 1; d <= 9; d++) {
if (row[r][d] || col[c][d] || box[bx][d]) continue;
b[r][c] = (char) ('0' + d);
row[r][d] = col[c][d] = box[bx][d] = true;
solve(b, k + 1);
b[r][c] = '.';
row[r][d] = col[c][d] = box[bx][d] = false;
}
return false;
}
static boolean solveSudoku(char[][] b) {
row = new boolean[9][10]; col = new boolean[9][10]; box = new boolean[9][10];
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (b[r][c] != '.') {
int d = b[r][c] - '0', bx = (r / 3) * 3 + c / 3;
if (row[r][d] || col[c][d] || box[bx][d]) return false;
row[r][d] = col[c][d] = box[bx][d] = true;
}
return solve(b, 0);
}
public static void main(String[] args) {
char[][] b = grid("53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
"7...2...6", ".6....28.", "...419..5", "....8..79");
System.out.println(solveSudoku(b));
show(b);
}
}
Real output: false, and the original puzzle with all its dots. The solver did reach k == 81, but nobody listened: every call erased its square on the way back up.
Bug 3: not marking the printed digits
import java.util.*;
public class Main {
static char[][] grid(String... rows) {
char[][] b = new char[9][];
for (int i = 0; i < 9; i++) b[i] = rows[i].toCharArray();
return b;
}
static void show(char[][] b) {
for (char[] r : b) System.out.println(new String(r));
}
static boolean[][] row, col, box;
static boolean solve(char[][] b, int k) {
if (k == 81) return true;
int r = k / 9, c = k % 9;
if (b[r][c] != '.') return solve(b, k + 1);
int bx = (r / 3) * 3 + c / 3;
for (int d = 1; d <= 9; d++) {
if (row[r][d] || col[c][d] || box[bx][d]) continue;
b[r][c] = (char) ('0' + d);
row[r][d] = col[c][d] = box[bx][d] = true;
if (solve(b, k + 1)) return true;
b[r][c] = '.';
row[r][d] = col[c][d] = box[bx][d] = false;
}
return false;
}
static boolean solveSudoku(char[][] b) {
row = new boolean[9][10]; col = new boolean[9][10]; box = new boolean[9][10];
return solve(b, 0);
}
public static void main(String[] args) {
char[][] b = grid("53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
"7...2...6", ".6....28.", "...419..5", "....8..79");
System.out.println(solveSudoku(b));
show(b);
}
}
Real output:
true
531273456
623195178
498156263
812364563
434813721
756722316
165427289
247419635
369581879
true, but row 0 has two 3s and two 5s. The checks never knew about the printed digits.
Complexity
Let m = number of empty squares (51 here).
| Approach | Time | Extra space | Dadaji's puzzle |
|---|---|---|---|
| Every digit everywhere, check at the end | O(9^m · 81) | O(m) recursion | TLE |
| Backtracking + row/col/box tables | O(9^m) worst case; thousands of calls in practice | 3 tables of 9 x 10 (constant) + O(m) ≤ 81 recursion depth | milliseconds |
Sudoku on a general n² x n² board is NP-complete, so no known algorithm is fast in the worst case. On real 9 x 9 puzzles, each square usually allows only 2 or 3 digits, and a clash is caught one square in, so backtracking is fast. Because the board is always 9 x 9, many people call the space (and even the time) O(1).
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
bx = r / 3 + c / 3 |
false, puzzle unchanged |
two boxes share one table | bx = (r / 3) * 3 + c / 3 |
solve(b, k + 1); with the result ignored |
false, puzzle unchanged |
the solution is erased on the way back | if (solve(b, k + 1)) return true; |
| Givens not marked before solving | true, but rows with repeated digits |
printed digits invisible to the checks | mark every printed digit first |
(char) d instead of (char) ('0' + d) |
unprintable characters in the grid | character number 5 is not the digit '5' |
(char) ('0' + d) |
Tables sized [9][9] |
ArrayIndexOutOfBoundsException: Index 9 out of bounds for length 9 |
digits go up to 9 | [9][10] (or use d - 1) |
| Checking the whole grid after every digit | correct but slow | O(81) per check | O(1) tables |
Mini project: a Sudoku checker and hint giver
- Write
isValid(char[][] b)that reports the first rule a filled grid breaks, e.g.row 0 has two 3s. - Write
hint(char[][] b)that finds an empty square with exactly one allowed digit and prints it, e.g.(4, 4) must be 5. Repeating hints solves easy puzzles without any guessing.
Practice
- Valid Sudoku (LeetCode 36): check whether a partly filled board breaks a rule (no solving).
Solution
It is exactly the marking loop of solveSudoku:
static boolean isValidSudoku(char[][] b) {
boolean[][] row = new boolean[9][10], col = new boolean[9][10], box = new boolean[9][10];
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (b[r][c] != '.') {
int d = b[r][c] - '0', bx = (r / 3) * 3 + c / 3;
if (row[r][d] || col[c][d] || box[bx][d]) return false;
row[r][d] = col[c][d] = box[bx][d] = true;
}
return true;
}
- Count the calls. Add a static counter to
solve. How many calls for Dadaji's puzzle and for the hardest puzzle?
Solution
Counting every call (including the pass-through calls for printed squares): about 6,400 for Dadaji's puzzle and about 72,000 for Inkala's.
- Fewest options first. Instead of filling squares in reading order, always fill the empty square with the fewest allowed digits. Why is that faster?
Solution
A square with one option is forced (no guessing); a square with two options splits the search in two instead of nine. Choosing the most constrained square first keeps the recursion tree narrow. This is the "minimum remaining values" heuristic used by real constraint solvers.
- 4 x 4 Sudoku with digits 1-4 and 2 x 2 boxes: what is the box formula?
Solution
bx = (r / 2) * 2 + c / 2, tables [4][5], and k goes to 16.
Quick quiz
int bx = (7 / 3) * 3 + 2 / 3;
Which box is square (7, 2) in? 2, 3, 6 or 7?
Answer
6. 7 / 3 = 2 (box row 2), 2 / 3 = 0 (box column 0), 2 * 3 + 0 = 6: the bottom-left box.
Interview questions
- How do you check a digit in O(1)? Boolean tables for rows, columns and boxes.
- How do you number the boxes?
(r / 3) * 3 + c / 3. - Why return
trueimmediately? There is one solution; continuing (or erasing) would undo it. - What do you do with the printed digits? Mark them in the tables before solving, and reject the puzzle if they already clash.
- What is the time complexity? O(9^m) worst case for
mempty squares; Sudoku is NP-complete in general. Space is constant for 9 x 9. - How would you make it faster? Fill the most constrained square first; use bitmasks instead of boolean tables; propagate forced squares.
- How is this like N-Queens? Same shape: choose, check in O(1), recurse, un-choose. Different constraints, and stop at the first answer.
Glossary
| Term | Meaning |
|---|---|
| Sudoku | A 9 x 9 puzzle: every row, column and 3 x 3 box must contain 1-9 exactly once |
| Given | A digit printed in the puzzle at the start |
| Box (sub-box) | One of the nine 3 x 3 squares outlined in bold |
| Box number | (r / 3) * 3 + c / 3, from 0 (top-left) to 8 (bottom-right) |
| Integer division | Division that throws away the remainder: 7 / 3 = 2 in Java |
k / 9, k % 9 |
Row and column of square number k (0..80) |
| Backtracking | Choose, explore, and undo the choice when it leads nowhere |
| Pruning | Rejecting a digit immediately so nothing is built on top of it |
| In place | Changing the given array instead of making a new one |
| NP-complete | A family of problems for which no fast (polynomial) algorithm is known |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
- Writing every digit in every blank and checking the full grid means up to 9^51 grids: TLE.
- Check each digit as it is written with
row[r][d],col[c][d],box[bx][d]; the box number is(r / 3) * 3 + c / 3. - Mark the givens first;
if (solve(b, k + 1)) return true;so the solution is never erased. - Exponential worst case, milliseconds in practice; constant extra space.
Next episode: Word search in a grid.