Sudoku & Backtracking

1. Algorithm & Complexity

Sudoku is a 9×9 grid with some cells filled (digits 1–9). The goal is to fill all empty cells so that each row, column, and each 3×3 block contains all digits 1–9 exactly once.

Backtracking Algorithm

1. Parse the input into a 9×9 array grid. Maintain three 2D boolean arrays:
   • rowUsed[r][d] = is digit d used in row r?
   • colUsed[c][d] = is digit d used in column c?
   • boxUsed[b][d] = is digit d used in 3×3 box b?
2. Scan once to initialize these arrays for the given digits.
3. Define solve(r,c):
   • If r==9, all rows done → solution found.
   • If grid[r][c]!=0, advance to next cell: solve(r + (c+1)/9, (c+1)%9).
   • Else (empty):
     1. For each digit d=1…9:
        • If none of rowUsed[r][d], colUsed[c][d], boxUsed[boxId(r,c)][d] are true:
        • — place d in grid[r][c], mark them true, recurse;
        • — if recursion returns true, terminate; otherwise undo and try next d.
     2. If no digit fits, return false → backtrack.

Here boxId(r,c) = (r/3)*3 + (c/3).

Time Complexity

In the worst case (empty grid), we try up to 9 possibilities per empty cell. There are 81 cells, so the worst-case search is O(9⁸¹)—astronomical. In practice, constraint checks prune heavily, and typical puzzles solve instantly.

Memory Complexity

We store:

• the 9×9 grid → O(1)
• the three marker arrays (9×10 each) → O(1)
• recursion stack up to depth ≤81 → O(1)

All are constant-sized, so O(1) extra memory.

---

2. Easy Backtracking Examples

2.1 – Codeforces 1462C: Generate All Subsets

Given n distinct integers, print all 2ⁿ subsets.

Input:
3
1 2 3

Output:
[]
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> a, curr;

void dfs(int idx) {
    if (idx == n) {
        cout << "[";
        for (int i = 0; i < curr.size(); ++i) {
            if (i) cout << ",";
            cout << curr[i];
        }
        cout << "]\n";
        return;
    }
    // exclude a[idx]
    dfs(idx + 1);
    // include a[idx]
    curr.push_back(a[idx]);
    dfs(idx + 1);
    curr.pop_back();
}

int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    dfs(0);
    return 0;
}

2.2 – Codeforces 1511A: Generate All Permutations

Given n, print all permutations of 1..n.

Input:
3

Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> perm;
vector<bool> used;

void dfs() {
    if (perm.size() == n) {
        for (int x : perm) cout << x << ' ';
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (used[i]) continue;
        used[i] = true;
        perm.push_back(i);
        dfs();
        perm.pop_back();
        used[i] = false;
    }
}

int main() {
    cin >> n;
    used.assign(n+1, false);
    dfs();
    return 0;
}

---

3. Intermediate Backtracking Examples

3.1 – Codeforces 29A: Word Search in a Grid

Given an m×n grid of letters and a target word, determine if it exists by moving up/down/left/right without reuse.

Input:
3 4
ABCE
SFCS
ADEE
SEE

Output:
YES

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int m, n;
vector<string> grid;
string word;
bool seen[100][100];

bool dfs(int r, int c, int idx) {
    if (idx == word.size()) return true;
    if (r<0||r>=m||c<0||c>=n) return false;
    if (seen[r][c] || grid[r][c] != word[idx]) return false;
    seen[r][c] = true;
    static int dr[4] = {1,-1,0,0}, dc[4] = {0,0,1,-1};
    for (int d = 0; d < 4; ++d) {
        if (dfs(r+dr[d], c+dc[d], idx+1)) return true;
    }
    seen[r][c] = false;
    return false;
}

int main() {
    cin >> m >> n;
    grid.resize(m);
    for (int i = 0; i < m; ++i) cin >> grid[i];
    cin >> word;
    bool found = false;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dfs(i,j,0)) { found = true; break; }
        }
        if (found) break;
    }
    cout << (found ? "YES\n" : "NO\n");
    return 0;
}

3.2 – Codeforces 579A: Knight Placements

Count ways to place K non‐attacking knights on an N×N board.

Input:
4 2

Output:
6

#include <iostream>
#include <vector>
using namespace std;

int N, K, ans = 0;
vector<vector<bool>> used;
int dr[8] = {-2,-2,-1,-1,1,1,2,2}, dc[8] = {-1,1,-2,2,-2,2,-1,1};

bool safe(int r, int c) {
    for (int d = 0; d < 8; ++d) {
        int rr = r + dr[d], cc = c + dc[d];
        if (rr >= 0 && rr < N && cc >= 0 && cc < N && used[rr][cc])
            return false;
    }
    return true;
}

void dfs(int idx, int placed) {
    if (placed == K) { ++ans; return; }
    if (idx == N*N) return;
    int r = idx / N, c = idx % N;
    // skip this square
    dfs(idx+1, placed);
    // try to place
    if (safe(r,c)) {
        used[r][c] = true;
        dfs(idx+1, placed+1);
        used[r][c] = false;
    }
}

int main() {
    cin >> N >> K;
    used.assign(N, vector<bool>(N,false));
    dfs(0,0);
    cout << ans << '\n';
    return 0;
}

---

4. Hard Backtracking Example

4.1 – Codeforces 1077C: 16×16 Sudoku (“Hexadoku”)

Generalize Sudoku to a 16×16 grid with digits 1–9 and letters A–G. Same rules: each row, column, and 4×4 block must have all 16 symbols exactly once. This is solved by the same backtracking approach, just larger.

Input:
16 lines of 16 chars ('.' for empty), symbols '1'–'9','A'–'G'

Output:
Completed 16×16 grid

#include <iostream>
#include <vector>
using namespace std;

int N = 16;
vector<string> grid(16);
bool rowU[16][16], colU[16][16], boxU[16][16];

int id(char ch) {
    if (ch >= '1' && ch <= '9') return ch - '1';
    return 9 + (ch - 'A');
}

char rev(int x) {
    if (x < 9) return '1' + x;
    return 'A' + (x - 9);
}

int boxId(int r,int c){ return (r/4)*4 + (c/4); }

bool dfs(int idx) {
    if (idx == N*N) return true;
    int r = idx / N, c = idx % N;
    if (grid[r][c] != '.') return dfs(idx+1);
    for (int d = 0; d < N; ++d) {
        int b = boxId(r,c);
        if (rowU[r][d]||colU[c][d]||boxU[b][d]) continue;
        rowU[r][d]=colU[c][d]=boxU[b][d]=true;
        grid[r][c] = rev(d);
        if (dfs(idx+1)) return true;
        grid[r][c] = '.';
        rowU[r][d]=colU[c][d]=boxU[b][d]=false;
    }
    return false;
}

int main(){
    for(int i=0;i<16;i++){
        cin>>grid[i];
        for(int j=0;j<16;j++){
            if (grid[i][j] != '.') {
                int x = id(grid[i][j]), b = boxId(i,j);
                rowU[i][x] = colU[j][x] = boxU[b][x] = true;
            }
        }
    }
    dfs(0);
    for (auto &s : grid) cout << s << '\n';
    return 0;
}

All of these examples use the same backtracking pattern:

• Choose a cell/position → try all valid options → recurse → undo (backtrack).
• Use boolean-marker arrays (or bit-masks) to check constraints in O(1).