Project 4: Puzzle Solver Suite

Milestone 1: Sudoku (backtracking with propagation)

Represent the board as nine lists of nine ints. A cell's peers are the 20 other cells in its row, column, and 3×3 box; write a helper that yields them, and both is_valid and candidates become one-liners. The solver is a depth-first search over choices (M33): pick an empty cell, try each candidate, recurse, and undo on failure. Two techniques make it fast:

• Constraint propagation (naked singles): repeatedly fill any cell with exactly one candidate. If some empty cell has zero candidates, this branch is dead: backtrack immediately.
• MRV (minimum remaining values): branch on the cell with the fewest candidates. A cell with two options splits the search in two; a cell with nine splits it nine ways.

count_solutions(grid, limit) reuses the same search but keeps going after the first solution, stopping at limit. Uniqueness is simply count_solutions(grid, 2) == 1: you never need to enumerate all solutions of an empty board (there are about 6.67 × 10²¹).

The same place-check-undo loop drives N-queens; step through it to watch pruning cut whole subtrees:

• parse_grid handles both formats and raises SudokuError on bad input
• is_valid, is_solved, and candidates pass
• solve solves the classic and hard puzzles without mutating the input
• Unsolvable and invalid boards return None
• count_solutions respects limit and detects a two-solution board

Milestone 2: Word ladder (BFS and bidirectional BFS)

Words are vertices; an edge joins two words that differ in one letter. Every edge costs 1, so BFS finds a shortest ladder: it explores all ladders of length k before any of length k + 1. Record a parents dict when you first discover each word and walk it backwards from end to rebuild the path. Generating neighbors by trying all 26 letters in every position costs O(26·L) set lookups per word, far cheaper than comparing against the whole dictionary.

Bidirectional BFS grows one frontier from each end, always expanding the smaller one a full layer at a time, and stops when they touch. If a single search explores b^d words, two half-depth searches explore about 2·b^d/2: on a real dictionary that is the difference between seconds and milliseconds.

• neighbors returns sorted one-letter variants that are in the dictionary
• BFS finds hit → … → cog in 5 words
• Bidirectional BFS returns ladders of the same (optimal) length
• Missing end words, disconnected words, equal words, and length mismatches are handled

Milestone 3: Weighted mazes (A*)

Entering a cell costs 1, or the digit's value for "mud" cells. With unequal costs BFS is no longer optimal, so use A*: a min-heap ordered by f = g + h, where g is the cost so far and h is the Manhattan distance to the goal. Because every step costs at least 1, Manhattan distance never overestimates the true remaining cost: it is admissible, and with an admissible (and here also consistent) heuristic the first time A* pops the goal its cost is optimal.

frontier = [(manhattan(start, goal), 0, start)]   # (f, g, cell)
while frontier:
    f, g, cell = heapq.heappop(frontier)
    if cell == goal: ...                         # rebuild the path from parents
    if g > best[cell]: continue                  # stale entry: skip it (lazy deletion)
    for nxt, step in maze.neighbors(cell): ...   # relax edges, push (g2 + h, g2, nxt)

• parse_maze pads ragged rows and rejects bad mazes
• Maze.cost and Maze.neighbors handle walls, digits, and the board edge
• Unit-cost mazes match BFS; weighted mazes take the cheaper detour
• Unreachable goals return None; render_path draws the route

Milestone 4: The 8-puzzle (invariants and A*)

Half of all 9! tile arrangements cannot be solved, and a naive search would explore all 181,440 reachable states before giving up. An invariant settles it instantly. Read the tiles row by row, ignoring the blank, and count inversions (pairs in the wrong order). A horizontal move does not change the reading order; a vertical move jumps one tile over two others, changing the count by −2, 0, or +2. So the parity of the inversion count never changes, and since the goal has 0 inversions, only boards with an even count are solvable.

For solvable boards, run A* where each state is a 9-tuple (hashable, so it can key a dict) and h is the sum of each tile's Manhattan distance to its home. Every move shifts one tile by one square, so h drops by at most 1 per move: admissible. The board (8, 6, 7, 2, 5, 4, 3, 0, 1) is one of the hardest: 31 moves.

• make_board validates permutations; inversions and is_solvable pass
• manhattan, apply_move, and apply_moves pass
• solve returns "" for the goal and None for unsolvable boards
• The hardest board solves in exactly 31 moves; random scrambles match BFS

Milestone 5: Knapsack and weighted interval scheduling (DP)

For 0/1 knapsack, best[i][w] is the best value using the first i items with capacity w: either skip item i (best[i-1][w]) or take it (best[i-1][w - weight] + value). Keep the full table so you can walk backwards: whenever best[i][w] != best[i-1][w], item i was taken.

For weighted interval scheduling, sort by end time. Let p(j) be the number of intervals that end no later than interval j starts; because the end times are sorted, bisect_right finds it in O(log n). Then best[j] = max(best[j-1], weight_j + best[p(j)]) and the whole thing runs in O(n log n). Greedy by earliest end time is optimal only when every weight is equal (M33); weights break it.

• Knapsack returns the textbook answer and consistent item indexes
• Knapsack matches brute force on 25 random instances
• Interval scheduling treats touching intervals as compatible and prefers one heavy interval
• Interval scheduling matches brute force on 25 random instances

Milestone 6: Benchmark CLI

time_call measures with time.perf_counter() (monotonic, high resolution) and reports the best of several runs, because the minimum is the run least disturbed by other processes. main uses argparse and returns an exit code instead of calling sys.exit, which keeps it testable.

solver                best ms
sudoku                  0.295
word_ladder             0.031
word_ladder_bidir       0.023
maze                    0.029
sliding                50.603
knapsack                0.019
intervals               0.009

• time_call returns a non-negative float
• main prints a header plus one row per solver and returns 0
• --only filters the rows