Introduction
Being a self taught Sudoku puzzle solver, I do enjoy solving the puzzles themselves but the real challenge is working out the strategies you need to solve them. Sometimes, I can get stuck on a puzzle and it can get a bit boring just going through all the strategies to try and find the next number. It may be obvious and I just cannot see it. That’s why I wrote this program. I’ve converted all the strategies that I know into code which will never get bored and make mistakes.
Some puzzles I cannot solve though. I was pretty sure there was a strategy that I was missing, and this program would confirm it.
The User Interface
It’s a simple WPF program. It uses the MahApps library to provide a icon less window and also an easy implementation of a dark mode.
Note that there is no solve button. The code will attempt to solve the puzzle on the fly each time the user changes it.
The Code
The program structure follows a minimal MVVM design pattern.
The Model contains all the solving strategies and a single dimension array of 81 cells. The trick to solving Sudoku puzzles is not to find out where numbers go directly, but is to find out where they cannot and when there is only one possibility left that must be it. To that end, each cell contains a list of possible cell values which is then updated by the strategies. The list is actually a bit field which allows the use of boolean algebra to aid the required pattern matching. The other notable point is that instead of writing two functions to implement a strategy, one for rows and another very similar version for columns I simply write the rows version, rotate the puzzle then call the rows function again. The puzzle isn't actually rotated, the code simply changes the way each cell's [x, y] coordinates are converted into an array index.
The ViewModel also contains a list of 81 cells this time stored in an ObservableCollection. When a user changes the puzzle, a callback in the ViewModel is executed. It determines which action is required and calls the appropriate model function, be it Add, Edit, Delete etc. so that the puzzle can be recalculated. When the model function returns, the two cell lists are compared and the view model list updated if required which redraws the cell.
The View contains a custom layout panel SudokuGrid that is used to arrange the cells and the grid lines. I couldn’t find much information online about writing layout panels so I reverse engineered the UniformGrid using ILSpy. Turns out they are quite easy, if you’ve written a custom control before, a lot of it will be familiar. The grid is contained within a Viewbox which provides automatic rescaling.
Solving Strategies
These will probably be very familiar to fellow Sudoku solvers but being self taught, they will have different names and terminology. The 81 cells are also arranged in to nine cubes each containing nine cells. Rows and columns are what you’d expect.
1. Simple Cube, Row and Column Elimination
If the user types a number into the red cell, then that number is removed from the possibles of all cells in the blue area. If that results in a cell having only one possible left, then that is added to a stack and the code loops processing cells until there are no more cells on the stack.
2. Direction Elimination
If the possible values of cells are exclusive to a single row of 3 cells in a cube, then no cells in remaining six cells of the puzzle row can contain those exclusive possibles. This is a row, so the direction of influence of the exclusive values is horizontal. An identical process is used for columns in cubes (vertical direction). Possible values will be shown as red if their direction is horizontal and green if vertical.
In addition, if a cell has a possible value that has both vertical and horizontal directions, then that must be the cell’s value.
3. Single Possible Value
While cells in a row or column may have multiple possible values, if only one cell has a particular value, then that must be the value of the cell.
4. Pattern Match Elimination
This strategy is a bit more involved. None of the coloured cells shown below have a value, only possibles.
The four green cells in two cubes will have six in their list of possible values. The six can occur in either the top and bottom or bottom and top cells in different columns, both arrangements could be valid. That means we can infer that the red cells in the remaining cube must have six in their possible values and thus six can then be removed from the cell possibles in the blue area. The pattern of the green cells shown is Pattern.Lower2, other possible patterns of two cells within cube columns is Pattern.Upper2 and Pattern.TopAndBottom.
The four green cells don’t need to be in the same columns, they could be in any combination. The result would be the same. To accommodate this, the code aggregates the possible values of all rows of three cells within the three cubes. This gives a structure of three columns, one for each cube containing three sets of possible values. It’s this structure that is then used for pattern matching.
This strategy is applied to all three rows of cubes in the puzzle and to each column of three cubes.
5. Simple Trial and Error
I knew that I would always have to implement this strategy because you occasionally find a puzzle where four cells at the intersection of two rows and two columns can have two possible values but the arrangement of them is indeterminant. The puzzle can have more than one correct solution. You just have to pick one value, insert it and then let the logic strategies work out the rest.
As it turns out, this may be the strategy that I was missing all along. While the logic strategies are enough to solve simpler problems alone, adding this strategy has allowed the harder puzzles to be solved as well. Expert puzzle solvers may be able to do that in their heads, keeping track of the state of the puzzle but that is beyond me. It’s also why I’m not good at chess; I can’t plan that many moves ahead.
Calling the Strategies
The model method CalculatePossibleValues, shown below is called every time the user changes the puzzle. It starts by building a stack of cells to update. It will either contain a single cell when the user types a new value into an empty cell or for more complex operations like deleting will be loaded with all cells that have a value so far so the the model can be rebuilt. Cells may then be added to the stack by the various solving strategies when they have only one possible value left.
The code consists of two nested while loops that continue until no more cells are left in the stack. The inner loop contains strategies that influence the results of each other and as such continue to loop while any changes to the model have been made.
private void CalculatePossibleValues(Cell updatedCell, bool forceRecalculation)
{
Stack<Cell> cellsToUpdate = new Stack<Cell>(Cells.Count);
if (updatedCell.HasValue && !forceRecalculation)
cellsToUpdate.Push(updatedCell);
else
{
foreach (Cell cell in Cells)
{
if (cell.Origin == Origins.User)
cellsToUpdate.Push(cell);
else
cell.Reset();
}
}
do
{
while (cellsToUpdate.Count > 0)
{
Cell cell = cellsToUpdate.Pop();
if (!cell.HasValue)
{
cell.Value = cell.Possibles.First;
cell.Origin = Origins.Calculated;
}
SimpleEliminationForCell(cell, cellsToUpdate);
}
bool modelChanged;
do
{
modelChanged = DirectionElimination(cellsToUpdate);
CheckForSinglePossibles(cellsToUpdate);
modelChanged |= CubePatternMatchElimination(cellsToUpdate);
}
while ((cellsToUpdate.Count == 0) && modelChanged);
}
while (cellsToUpdate.Count > 0);
}
When this method returns the trial and error strategy will be called if that's appropriate for the change that the user initiated.
Round Up
Well, that’s it. This was my Covid lockdown project. The trouble with being self taught in any subject is that you can never really be sure of how much of the problem space you’ve covered. But this solution does seem at least reasonable. I hope you like it and maybe, you can reuse some of the techniques in your own code.
History
- 30th June 2020: Initial submission
- 4th February 2021: Update article for application release 1.2.0
