Faangprep Logo
Log inStart free
Browse curriculum

Sudoku Solver

A Sudoku solver fills the empty cells of a 9x9 board so that every row, column and 3x3 box contains the digits 1-9.

READY

5
3
4
8
9
1
2
6
7
2
9
4
8
1
9
8
3
4
7
8
5
9
7
4
2
3
4
6
8
5
3
7
1
1
3
9
2
4
8
5
1
5
7
2
8
2
8
4
1
9
6
3
2
8
6
1
9

Backtracks

0

 

24 blanks to fill. Scanning row by row for the first one.

Next

Try 1 at (0, 3).

Blanks

Intuition

Imagine trying to solve a Sudoku puzzle. You find an empty cell and try '1'. If it works, you move to the next. If you get stuck later, you erase '1' and try '2'.

This 'try and undo' process is Backtracking. We systematically explore valid numbers for each empty cell.

Concept

Key Concepts:

  • Backtracking: A depth-first search where we build a solution piece by piece and abandon a path ('backtrack') if it violates constraints.
  • Constraints: A number is valid if it's not already in the same Row, Column, or 3x3 Sub-box.
  • Recursion: We solve for one cell, then recursively solve for the rest.

How it Works

  1. Find the first empty cell (marked '.' or 0).
  2. Try digits 1 through 9.
  3. Check if the digit is valid (not in row, col, box).
  4. If valid, place it and recurse to solve the rest of the board.
  5. If recursion returns true, we found a solution!
  6. If recursion returns false, reset the cell (backtrack) and try the next digit.

Step-by-Step Breakdown

Example: Empty cell at (0, 2)

  • Try '1': Valid? No (exists in row).
  • Try '2': Valid? Yes. Place '2'.
  • Recurse to (0, 3).
  • ... If path fails, return to (0, 2), reset '2', try '3'.

When to Use

  • Constraint Satisfaction Problems (Sudoku, N-Queens, Crossword).
  • Finding one valid configuration among exponentially many options.

When NOT to Use

  • When an optimization or greedy approach exists (e.g., Shortest Path).
  • When the search space is too large for brute-force recursion.

How to Identify

"Find a valid arrangement", "Fill the grid", "Satisfy constraints".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

N-Queens

Next

Rat in a Maze

Frequently Asked Questions

How does a Sudoku solver work?

It recursively tries digits 1-9 for every empty cell. If a digit violates row, column, or 3x3 grid constraints, it backtracks and tries the next digit.

Why does backtracking beat brute force for Sudoku?

Brute force tries all combinations for all cells. Backtracking stops the MOMENT a cell fails, saving quadrillions of unnecessary attempts.

Sudoku Search Space?

The total possibilities are astronomical, but Backtracking with pruning typically solves a standard puzzle in milliseconds.