Project 1: Sudoku Solver

Build a Sudoku solver that uses constraint propagation and search.

Project Overview

Attribute Value
Difficulty Level 1: Beginner
Time Estimate Weekend
Main Language Python
Alternative Languages JavaScript, C++
Knowledge Area Discrete math and constraints
Tools CLI or simple UI
Main Book “Programming Challenges” by Skiena & Revilla

What you’ll build: A solver that reads Sudoku puzzles and outputs solved grids with reasoning steps.

Why it teaches math: Sudoku is pure constraint logic. You learn how to formalize rules and prune search.

Core challenges you’ll face:

  • Representing constraints efficiently
  • Implementing deduction rules
  • Backtracking when logic stalls

Real World Outcome

You will input a Sudoku grid and receive the solved grid with a trace of deductions and guesses.

Example Output:

$ python sudoku.py puzzle.txt
Solved in 42 steps
Guesses: 3
Solution written to solved.txt

Verification steps:

  • Check each row/column/box contains digits 1-9
  • Solve puzzles of varying difficulty

The Core Question You’re Answering

“How do I formalize logical constraints so a computer can solve a puzzle like a human?”

This is constraint reasoning in its simplest form.

Concepts You Must Understand First

Stop and research these before coding:

  1. Constraint propagation
    • How do you reduce possibilities using known values?
    • Book Reference: “Programming Challenges” by Skiena & Revilla, Ch. 2
  2. Search trees
    • Why does backtracking find solutions efficiently?
    • Book Reference: “Algorithmic Thinking” by Daniel Zingaro, Ch. 9
  3. State representation
    • How do you encode candidates for each cell?
    • Book Reference: “Problem Solving with Algorithms” by Brad Miller, Ch. 3

Questions to Guide Your Design

  1. Deduction rules
    • Will you implement only single-candidate rules or more advanced ones?
    • How will you detect contradictions?
  2. Search strategy
    • Which empty cell should you guess first?
    • How will you track and undo guesses?

Thinking Exercise

Constraint Elimination

Take a partially filled row with digits {1,2,3,5,7} already present. List which digits remain possible for an empty cell in that row.

Questions while working:

  • How does this change if the column already has {4,6,8}?
  • Why does early elimination reduce search?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What is constraint propagation?”
  2. “Why is backtracking effective for Sudoku?”
  3. “How do you choose the next variable to assign?”
  4. “How do you detect an invalid state early?”
  5. “What is the complexity of a brute-force solver?”

Hints in Layers

Hint 1: Starting Point Start with a representation that stores candidate sets for each cell.

Hint 2: Next Level Always pick the cell with the fewest candidates to guess.

Hint 3: Technical Details Track changes in a stack so you can undo quickly.

Hint 4: Tools/Debugging Add a mode that prints the candidate grid after each step.

Books That Will Help

Topic Book Chapter
Constraint propagation “Programming Challenges” by Skiena & Revilla Ch. 2
Backtracking “Algorithmic Thinking” by Daniel Zingaro Ch. 9
State representation “Problem Solving with Algorithms” by Brad Miller Ch. 3

Implementation Hints

  • Keep grid and candidates separate for clarity.
  • Apply deterministic rules until stuck, then guess.
  • Validate after each assignment to catch contradictions.

Learning Milestones

  1. First milestone: You can solve easy puzzles with pure deduction.
  2. Second milestone: You can solve harder puzzles with backtracking.
  3. Final milestone: You can explain why heuristics reduce search.