Sudoku
Overview:
For this implementation, I chose to implement a few different types of Sudoku solvers (brute force, greedy, and exact cover) to showcase the differences between them. Running the main method in each solver class will show a visualization of how the specific algorithm steps through the problem in the terminal. You can also change the delay variable to change how quickly each step is shown. A delay of 0 will not display a visualization. There are also short test classes written to test the code.
Implementations:
Brute force - The basic sudoku solver, essentially guess and check. Takes exponential time so don't expect to use this to solve anything bigger than a 25x25 board.
Greedy solution - Most standard sudoku puzzles have rows, columns, or boxes where only one number is possible for a given position at all times. This greedy solution takes advantage of that and is able to solve most standard puzzles in polynomial time.
Exact cover - This is an optimization of the brute force method by reducing sudoku into an
Exact Cover problem. I then used Knuth's Algorithm X as my implementation. While this is method still takes exponential time, it is a substantial optimizaion. The exact cover solver follows the same steps as the greedy solver, so it is not displayed below.