Basic Solver

Strategies

The first step is to put together a basic solver. In Sudoku, there are 3 Regions - Row, Column and Box, but you probably know that already if you are reading this. Other terminology I might use are Cell (a single cell in the puzzle), Possibility (one of a number of  candidate values in a cell, sometimes known as pencil marks), Sure (the value that must go in a cell) and Given (the Sures given in a starter puzzle). To start with I'll pick a limited number of Sudoku Strategies at various level of difficulties. I won't go into what these are in detail, as you can probably find that elsewhere in specialist sites, so briefly here are the implemented strategies for the basic solver.
  • NakedSets  - a collection of cells where the number of Possibilities equals the number of number cells. In this case, theses possibilities can be removed from other cells in the same region. These are often referred to as doubles or triplets, but in ExcelDoku we can deal with any number in a set. 
  • HiddenSets - These are a more complicated version of NakedSets. However, it's my experience that allowing any size of naked sets means that you dont need to check for hidden sets. In other words, i propose that for every hidden set, a more complex naked set will exist. This may be an invalid proposition, but I have never found a hidden set that cannot be solved in another way. Appreciate any insight that proves me wrong. I will not therefore implement a hidden set algorithm.
  • BoxReduce - Where a possibility only occurs on one Row or Column of a Box, and not in any other Box that the Row or Column intersects, then the possibilities can be removed from other rows and columns in the target Box
  • LineReduce  - the converse of the BoxReduce where the possibilities can be removed from the row or column, rather than the Box, because there is no other place in the box that the Possibilities could occur
  • SingleChoice - There is only one possibilitity left for a given cell
  • Xwing - this is a harder strategy, which can look outside a region. In summary, if the same pair of possibilities appear at the 4 corners of a rectangle, and those possibilities do not appear elsewhere on the rows that intersect with these 4 corners, then they can be removed from the cells in the columns that intersect with the 4 corners. You can also reverse rows and columns to apply the same rule.
  • Swordfish- this is a more complex version of xwing, where up to 3 cells participate in forming the xwing.
  • XYwing - This is where a set of 3 cells forming a Y, with exactly 3 possibilities between them can force the elimination of a possibility from related cells
  • Brute - This is not a strategy as such, but a technique that is used only in the generation of puzzles. Possibilities are randomly selected and 'tried out' in each cell until the puzzle is solved. Once the puzzle is generated using 'brute', 'sures' are removed while it is still solvable using human strategies (not brute) in order to be left with a starter puzzle, with the required number of 'givens' and level of difficulty.

Structure

This is the structure of the solving mechanism, implemented as a method of the cSudGrid class. You can see that it recurses until there is no change to the grid (indicated by IsDirty). Because we need to be able to generate (and therefore solve) according to a difficulty target, any change caused by the later, more complex strategies, causes an re-iteration through the simpler strategies. So far I have only implemented xWing and xyWing of the more complex strategies. Still to implement swordfish and the other fishy strategies.


Public Sub solveIterate()
    ' this will iterate until all strategies have been triesd - the deeper it goes the more difficult the solution
    Dim cs As cSudSolver
    
    'convert single sures
    cleanupSures
    If isSolved Or isScrewedUp Then Exit Sub
    ' this one is a technique for doing all naked sets at once, includig reducing single choices.
    ' havent found a hidden set that doesnt have a harder naked set so dont even bother with them
        Set cs = New cSudSolver
        With cs
            .init Me
            .magicSetEliminations
        End With
        accumulateStats
        Set cs = Nothing
        If isDirty Then solveIterate
    
        
    'Hard  - outside the box eliminations/wings
    If isSolved Or isScrewedUp Then Exit Sub
        xWing
        If isDirty Then solveIterate
    
    
End Sub

Note that I will not give all the code in these pages. You can download the latest state of the ExcelDoku , which includes the complete code, from the downloads page.

Next Steps

Now that we have implemented a viable solver the next step is implement a brute force strategy and create the first generator attempt.

You want to learn Google Apps Script?

Learning Apps Script, (and transitioning from VBA) are covered comprehensively in my my book, Going Gas - from VBA to Apps script, All formats are available from O'Reilly, Amazon and all good bookshops. You can also read a preview on O'Reilly

If you prefer Video style learning I also have two courses available. also published by O'Reilly.
Google Apps Script for Developers and Google Apps Script for Beginners.