Capstone Project: A Puzzle-Solving Agent

# puzzle_base.py
 
from abc import ABC, abstractmethod
 
class Puzzle(ABC):
    """A shared interface both puzzle types implement, for a consistent CLI."""
 
    @abstractmethod
    def is_solved(self) -> bool:
        pass
 
    @abstractmethod
    def solve(self):
        """Returns a solution (format varies by puzzle type)."""
        pass
 
    @abstractmethod
    def display(self) -> str:
        pass

# eight_puzzle.py
 
import heapq
from puzzle_base import Puzzle
 
GOAL_STATE = (1, 2, 3, 4, 5, 6, 7, 8, 0)      # 0 represents the blank tile
 
def manhattan_distance(state, goal=GOAL_STATE, size=3):
    """Module 2, Ch.3's admissible heuristic, reused directly."""
    total = 0
    for i, tile in enumerate(state):
        if tile == 0:
            continue
        goal_index = goal.index(tile)
        row1, col1 = divmod(i, size)
        row2, col2 = divmod(goal_index, size)
        total += abs(row1 - row2) + abs(col1 - col2)
    return total
 
def get_neighbors(state, size=3):
    """All states reachable by sliding a tile into the blank space."""
    neighbors = []
    blank_index = state.index(0)
    row, col = divmod(blank_index, size)
 
    moves = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)}
    for move_name, (dr, dc) in moves.items():
        new_row, new_col = row + dr, col + dc
        if 0 <= new_row < size and 0 <= new_col < size:
            new_index = new_row * size + new_col
            new_state = list(state)
            new_state[blank_index], new_state[new_index] = new_state[new_index], new_state[blank_index]
            neighbors.append((move_name, tuple(new_state)))
    return neighbors
 
 
class EightPuzzle(Puzzle):
    def __init__(self, initial_state):
        self.initial_state = tuple(initial_state)
        self.solution_path = None
 
    def is_solved(self):
        return self.initial_state == GOAL_STATE
 
    def solve(self):
        """A* search (Module 2, Ch.3), reused directly against this puzzle."""
        frontier = [(manhattan_distance(self.initial_state), 0, self.initial_state, [])]
        visited = {}
 
        while frontier:
            f, g, state, path = heapq.heappop(frontier)
 
            if state == GOAL_STATE:
                self.solution_path = path
                return path
 
            if state in visited and visited[state] <= g:
                continue
            visited[state] = g
 
            for move_name, next_state in get_neighbors(state):
                new_g = g + 1      # every move costs 1
                new_f = new_g + manhattan_distance(next_state)
                if next_state not in visited or visited[next_state] > new_g:
                    heapq.heappush(frontier, (new_f, new_g, next_state, path + [move_name]))
 
        return None      # unsolvable configuration
 
    def display(self):
        rows = [self.initial_state[i:i+3] for i in range(0, 9, 3)]
        return "\n".join(" ".join(str(t) if t != 0 else "_" for t in row) for row in rows)
 
 
puzzle = EightPuzzle([1, 2, 3, 4, 0, 6, 7, 5, 8])
solution = puzzle.solve()
print(f"Solved in {len(solution)} moves: {solution}")

# sudoku_solver.py
 
from puzzle_base import Puzzle
 
def get_related_cells(cell):
    """All cells sharing a row, column, or 3x3 box with `cell` (row, col)."""
    row, col = cell
    related = set()
    for c in range(9):
        related.add((row, c))
    for r in range(9):
        related.add((r, col))
    box_row, box_col = 3 * (row // 3), 3 * (col // 3)
    for r in range(box_row, box_row + 3):
        for c in range(box_col, box_col + 3):
            related.add((r, c))
    related.discard(cell)
    return related
 
 
class SudokuSolver(Puzzle):
    def __init__(self, grid):
        """grid: 9x9 list of lists, 0 = empty cell."""
        self.grid = [row[:] for row in grid]
        self.variables = [(r, c) for r in range(9) for c in range(9) if grid[r][c] == 0]
        self.domains = {
            (r, c): (set(range(1, 10)) if grid[r][c] == 0 else {grid[r][c]})
            for r in range(9) for c in range(9)
        }
 
    def is_solved(self):
        return all(self.grid[r][c] != 0 for r in range(9) for c in range(9))
 
    def _is_consistent(self, assignment, cell, value):
        for related_cell in get_related_cells(cell):
            if assignment.get(related_cell) == value:
                return False
        return True
 
    def _forward_check(self, assignment, domains, cell, value):
        new_domains = {k: set(v) for k, v in domains.items()}
        for related_cell in get_related_cells(cell):
            if related_cell not in assignment and value in new_domains[related_cell]:
                new_domains[related_cell].discard(value)
                if not new_domains[related_cell]:
                    return None      # dead end
        return new_domains
 
    def _most_constrained_variable(self, assignment, domains):
        unassigned = [v for v in self.variables if v not in assignment]
        return min(unassigned, key=lambda v: len(domains[v]))
 
    def _backtrack(self, assignment, domains):
        if len(assignment) == len(self.variables):
            return assignment
 
        cell = self._most_constrained_variable(assignment, domains)      # MRV heuristic
 
        for value in sorted(domains[cell]):
            if self._is_consistent(assignment, cell, value):
                assignment[cell] = value
                new_domains = self._forward_check(assignment, domains, cell, value)
 
                if new_domains is not None:
                    result = self._backtrack(assignment, new_domains)
                    if result is not None:
                        return result
 
                del assignment[cell]
 
        return None
 
    def solve(self):
        initial_assignment = {
            (r, c): self.grid[r][c] for r in range(9) for c in range(9) if self.grid[r][c] != 0
        }
        result = self._backtrack(initial_assignment, self.domains)
 
        if result:
            for (r, c), value in result.items():
                self.grid[r][c] = value
        return result
 
    def display(self):
        return "\n".join(" ".join(str(v) if v != 0 else "." for v in row) for row in self.grid)
 
 
example_grid = [
    [5,3,0, 0,7,0, 0,0,0], [6,0,0, 1,9,5, 0,0,0], [0,9,8, 0,0,0, 0,6,0],
    [8,0,0, 0,6,0, 0,0,3], [4,0,0, 8,0,3, 0,0,1], [7,0,0, 0,2,0, 0,0,6],
    [0,6,0, 0,0,0, 2,8,0], [0,0,0, 4,1,9, 0,0,5], [0,0,0, 0,8,0, 0,7,9],
]
sudoku = SudokuSolver(example_grid)
sudoku.solve()
print(sudoku.display())

# explainer.py
 
def explain_naked_single(grid, cell):
    """
    A classic Sudoku human-solving RULE (Module 3, Ch.6's rule-based
    reasoning): if a cell has only ONE possible value remaining after
    eliminating everything already used in its row/column/box, explain why.
    """
    from sudoku_solver import get_related_cells
 
    row, col = cell
    used_values = {grid[r][c] for r, c in get_related_cells(cell) if grid[r][c] != 0}
    possible = set(range(1, 10)) - used_values
 
    if len(possible) == 1:
        value = possible.pop()
        return (f"Cell ({row},{col}) must be {value}: it's the only value "
                f"not already used in its row, column, or 3x3 box.")
    return f"Cell ({row},{col}) has {len(possible)} possible values — not a naked single."

# main.py
 
from eight_puzzle import EightPuzzle
from sudoku_solver import SudokuSolver, example_grid
from explainer import explain_naked_single
 
def run_eight_puzzle_demo():
    print("\n=== 8-Puzzle Solver (A* Search) ===")
    puzzle = EightPuzzle([1, 2, 3, 4, 0, 6, 7, 5, 8])
    print("Initial state:")
    print(puzzle.display())
 
    solution = puzzle.solve()
    if solution:
        print(f"\nSolved in {len(solution)} moves: {' -> '.join(solution)}")
    else:
        print("\nNo solution found.")
 
 
def run_sudoku_demo():
    print("\n=== Sudoku Solver (CSP: Backtracking + Forward Checking + MRV) ===")
    sudoku = SudokuSolver(example_grid)
    print("Initial grid:")
    print(sudoku.display())
 
    result = sudoku.solve()
    if result:
        print("\nSolved grid:")
        print(sudoku.display())
        print("\nExample explanation for one originally-empty cell:")
        print(explain_naked_single(example_grid, (0, 2)))
    else:
        print("\nNo solution found.")
 
 
def main():
    run_eight_puzzle_demo()
    run_sudoku_demo()
 
 
if __name__ == "__main__":
    main()

$ python main.py
 
=== 8-Puzzle Solver (A* Search) ===
Initial state:
1 2 3
4 _ 6
7 5 8
 
Solved in 2 moves: down -> right
 
=== Sudoku Solver (CSP: Backtracking + Forward Checking + MRV) ===
Initial grid:
5 3 . . 7 . . . .
...
Solved grid:
5 3 4 6 7 8 9 1 2
...

# test_puzzles.py
 
import pytest
from eight_puzzle import EightPuzzle, GOAL_STATE
from sudoku_solver import SudokuSolver
 
def test_eight_puzzle_already_solved():
    puzzle = EightPuzzle(list(GOAL_STATE))
    assert puzzle.is_solved()
 
def test_eight_puzzle_finds_solution():
    puzzle = EightPuzzle([1, 2, 3, 4, 0, 6, 7, 5, 8])
    solution = puzzle.solve()
    assert solution is not None
    assert len(solution) > 0
 
def test_sudoku_solves_valid_puzzle():
    grid = [
        [5,3,0, 0,7,0, 0,0,0], [6,0,0, 1,9,5, 0,0,0], [0,9,8, 0,0,0, 0,6,0],
        [8,0,0, 0,6,0, 0,0,3], [4,0,0, 8,0,3, 0,0,1], [7,0,0, 0,2,0, 0,0,6],
        [0,6,0, 0,0,0, 2,8,0], [0,0,0, 4,1,9, 0,0,5], [0,0,0, 0,8,0, 0,7,9],
    ]
    solver = SudokuSolver(grid)
    result = solver.solve()
    assert result is not None
    assert solver.is_solved()
 
    # Verify every row contains 1-9 with no repeats
    for row in solver.grid:
        assert sorted(row) == list(range(1, 10))

$ pytest test_puzzles.py -v
test_puzzles.py::test_eight_puzzle_already_solved PASSED
test_puzzles.py::test_eight_puzzle_finds_solution PASSED
test_puzzles.py::test_sudoku_solves_valid_puzzle PASSED