Algoritmalar
en

Sudoku Solver

Backtracking O(9^m) O(m)

Fills empty cells one at a time, trying digits 1–9 and backtracking whenever a digit breaks the rules.

5
6
7
8
9
1
6
7
1
9
5
3
4
8
1
9
8
3
4
5
6
7
5
9
7
6
1
4
2
3
4
6
8
5
3
7
9
7
1
3
9
2
4
8
5
6
9
6
1
5
3
7
2
8
4
8
7
1
9
6
3
5
3
4
5
8
6
1
7
9
Solving one preset puzzle — watch digits get tried, placed and undone.
1/94

Empty cell at (0, 1) — try to fill it.

InvariantEvery filled cell satisfies its row, column and box. A digit is only placed when it still holds.

sudoku.c
int valid(int g[9][9], int r, int c, int d) {
    for (int i = 0; i < 9; i++) {
        if (g[r][i] == d || g[i][c] == d)
            return 0;
        if (g[3*(r/3) + i/3][3*(c/3) + i%3] == d)
            return 0;
    }
    return 1;
}
 
int solve(int g[9][9]) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (g[r][c]) continue;
            for (int d = 1; d <= 9; d++) {
                if (valid(g, r, c, d)) {
                    g[r][c] = d;
                    if (solve(g)) return 1;
                    g[r][c] = 0;   /* backtrack */
                }
            }
            return 0;
        }
    }
    return 1;
}

How Sudoku Solver works

Find the next empty cell, try digits 1–9, recurse on the rest of the grid, and erase the digit when a dead end proves it wrong. Constraint checks keep the branching factor small.

When to use it

Constraint-satisfaction puzzles; the same skeleton solves scheduling and coloring instances.