Sudoku Solver
A high-performance algorithmic solver built in Java. It utilizes backtracking and constraint satisfaction to process and solve any valid Sudoku puzzle in a matter of milliseconds.
The Challenge
Sudoku is a classic example of an exact cover problem. While a naive brute-force approach (trying every number in every empty square sequentially) might eventually solve easy puzzles, it drastically fails on more complex grids due to massive time complexity. The challenge was to implement an optimized, recursive search strategy that prunes invalid paths early, preventing unnecessary computational overhead.
Implementation Breakdown
Recursive Backtracking (DFS)
The core engine of the solver is driven by a Depth-First Search (DFS) backtracking algorithm. The program traverses the board, making educated guesses for empty cells. If a guess violates Sudoku rules later down the path, the algorithm "backtracks"—undoing the choice and trying the next viable option. This ensures all possibilities are explored methodically without retaining invalid branches in memory.
Constraint Validation
Implemented robust, constant-time `isValid()` checks before making any recursive call. The solver instantly verifies row, column, and 3x3 subgrid constraints, drastically shrinking the tree of possibilities and preventing computationally expensive wrong turns.
State Management
Modeled the Sudoku grid using efficient 2D array structures in Java. Carefully managed the mutability of the board state during the recursive descent, ensuring that when the algorithm backtracks, the state is cleanly restored without memory leaks or deep-copy overhead.
Outcomes & Takeaways
The resulting algorithm easily tackles puzzles classified as "Evil" in under a fraction of a second. This project deeply honed my skills in recursion, complexity analysis (Big O notation), and writing highly performant, logic-driven Java code.