AI Sudoku Solver
This project explored constraint satisfaction problems by implementing a Sudoku solver in Python. Rather than using brute-force search, the solver applies inference algorithms to gradually narrow down possibilities until the puzzle is solved. My implementation included the AC-3 algorithm for arc consistency, an improved inference technique, and backtracking search to solve puzzles of easy, medium, and hard difficulty.
I began by modeling Sudoku as a CSP. The constraints were each cell in the 9x9 grid could contain digits 1-9 as long as each row, column and 3x3 block contained each digit only once. The first step was ensuring arc consistency, or checking if pairs of relating cells supported the constraint. As per the AC-3 Algorithm, if a value in one cell had no supporting value in its neighbor, it was pruned. This could reduce puzzles enough to solve easy boards but not medium or hard boards.
The next step was to implement inference. Inference allowed the program to scan rows, columns and blocks for unique candidates. For example, if the digit 7 could only appear in one cell of a block because its possible rows and columns are limited, the 7 could safely be placed in said cell. This enhanced the solver to complete all medium difficulty puzzles.
Finally for hard puzzles, I combined inference with recursive backtracking. When stuck, the algorithm would select a cell with multiple candidates and guess one of them. From there it would continue solving until the guess led to a contradiction or made the puzzle unsolvable. In this case, the algorithm backtracked to its guess and tried the next option. This hybrid of inference plus search successfully solved the most difficult puzzles.
This project deepened my understanding of AI problem-solving frameworks by showing how CSPs combine logic-based reasoning and search. I gained hands-on experience with arc consistency, constraint propagation and recursive backtracking. These techniques make AI systems efficient on problems that would be impossible with brute force. Beyond Sudoku, these methods apply to real-word tasks such as scheduling, resource allocation, and planning, while also strengthening my skills in Python recursion and modular AI system design.
