As a personal algorithms project, I created a Sodoku solving program in Python, and implemented a display using Tkinter. The program currently layers strategies in decreasing complexity, first attempting to use more “sophisticated” approaches before falling back to approximations.
First, the board tries to find unique candidates, instances in which cells may have many legal moves, but when considering their neighbors, are the only possibility for certain numbers within their block. By a simple process of elimination, the program can guarantee a correct placement.
This GIF shows the deduction of unique candidates. The red circles highlight the position of numbers that prevent moves along the red lines (and inside the respective blocks) for the number in question; the green circles identify the tiles that remain.
The program attempts to fill as many unique candidates as it can, and it is possible to solve an entire board based on this strategy alone. However, if no unique candidates exist, the board will attempt to reason which tiles have the fewest legal moves, and which of those moves are best, in a strategy called best guess, a form of backtracking.
Best guess depends on tiles with a large amount of conflicts, and therefore a low amount of legal moves. First, the program reduces the potential for dead-ends by finding the best cell, or the tile with the lowest amount of possibilities.
If the best cell can fit only one number, then there is no “guess” involved, and the number is placed. If there is more than one possibility, then the tile will iterate through its possibilities. If it finds that the placement it tried did not lead to the solution, then it will try the next, until it is forced to move onto a different tile.
This best cell strategy is further refined by also considering the best numbers out of the choices available to the cell. Instead of solely depending on the location of the tile, the prevalence of each number on the board is considered; the possibilities are placed in ascending order of quantity, such that numbers that have fewer placements are considered first. Best numbers characterizes a sort of “breadth first” approach, considering that the program will always attempt to keep the quantity of all numbers relatively equal, rather than striding to get 9 of each at a time.
The code can be found on my Github.