Have you ever written an algorithm, passed all the test cases, and then thought, I'm still not sure that I totally understand how this thing works!? Well, that occurred to me after finishing a Sudoku Back-Tracking Search (BTS) algorithm. The truth being, not that I didn't know how the program was working, but I didn't understand exactly how many attempts the solver would take to find a solution. So, I set out to write some timing scripts and record some statistics and thought, I can do so much better. And here is my first attempt.

Constraint Satisfaction Problems (CSP)

As for games, Sudoku is pretty straight forward and fits nicely as a CSP. The constraints being the numbers 1 through 9 occurring in each column, row, and square of a completed sudoku board. This means that a value in one square will affect the constraints of the rest of the board. Winning the game is simply satisfying the constraints of all possible positions. This is what the aforementioned solver attempts to do. Using some simple logical rules, it will attempt to find the easiest positions to solve, then update neighboring constraints. When the solver has found a board that contains positions that cannot possibly satisfy the constraints, the solver will backtrack and start again from a previous step. Play around with the visual editor to see how the solutions may vary in steps and time.

Depth & Speed

There are two toggles to play with on the game board. The first is depth. This is the more confusing of the two. Depth is how far ahead the algorithm will look forward in attempting to solve a sudoku board. That is how many moves ahead it will plan before failing back to its heuristic function to decide its success. For example, an infinite depth would mean that the solver simply tries every solution with every possible move until it finds the answer, but a shorter depth means it will try moves until an apprved depth, and then try to evaluate whether it is in a "good" game position. The second toggle is the speed. This one is likely much more entertaining. Simply toggle the speed to increase the speed of the solver, and decrease to slow. Below the board when solving, it will print the amount of steps remaining to solve. Make sure to use this if you're wondering how long this might take.

Heuristic Functions

The solver was a fun attempt, but really there is so much more to come. Eventually, I would like to add some choices for different heuristic algorithms. And what this really means is simple: For the solver to be as "efficient" as possible, it would be nice for the solver to understand what makes one board better or worse off than another. The current naive implementation says that more filled in squares makes for a better solution. However, I think we can do better, what if what makes a good sudoku board is not just the amount of squares completed, but also the amount of constraint options available left in the solution. Or, maybe having 9 of the same numbers in the current solution is better than having one of each number filled in. Anyways, this is all soon to come. For now, enjoy.