SyntaxPilot
Courses/DSA and Coding Problems/Lesson 34
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 34 of 90

Sudoku solver (hard)

queued

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:

  1. Each of the digits 1-9 occurs exactly once in each row.
  2. Each of the digits 1-9 occurs exactly once in each column.
  3. 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

  1. Write isValid(char[][] b) that reports the first rule a filled grid breaks, e.g. row 0 has two 3s.
  2. 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

  1. 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;
    }
  1. 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.

  1. 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.

  1. 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

  1. How do you check a digit in O(1)? Boolean tables for rows, columns and boxes.
  2. How do you number the boxes? (r / 3) * 3 + c / 3.
  3. Why return true immediately? There is one solution; continuing (or erasing) would undo it.
  4. What do you do with the printed digits? Mark them in the tables before solving, and reject the puzzle if they already clash.
  5. What is the time complexity? O(9^m) worst case for m empty squares; Sudoku is NP-complete in general. Space is constant for 9 x 9.
  6. How would you make it faster? Fill the most constrained square first; use bitmasks instead of boolean tables; propagate forced squares.
  7. 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.