Sudoku Explain: Auditable Search Traces and a Reproducible Python Solver Comparison

Abstract

Sudoku provides a compact setting for studying constraint satisfaction and heuristic search, but an answer grid alone does not reveal which decisions were logically forced and which depended on assumptions. This paper presents Sudoku Explain, a local Python application that records rule applications, speculative assignments, contradictions, and branch restoration for interactive replay. The implementation combines established minimum-remaining-values selection with naked and hidden singles; it does not introduce a new solving algorithm. A separate set-based exact-cover implementation checks solution uniqueness. A controlled comparison evaluates four configurations on 60 generated puzzles with 44, 36, or 28 clues, using three repetitions per puzzle and configuration. All 720 runs returned valid solutions within the specified budgets. In the 28-clue group, median runtimes were 84.115 ms for row-order search and 1.808 ms for the full configuration; the median paired speedup was 39.39. A separate experiment audited 180 recorded traces, covering 8,196 assignment events, and measured a median recording-time ratio of 1.045 relative to unrecorded runs. These findings establish measured behavior for this implementation and synthetic dataset, rather than general solver superiority or educational effectiveness. The artifact provides an inspectable starting point for learning about symbolic AI and for extending the evaluation to harder external benchmarks.