StrategiesThe 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.
StructureThis 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 StepsNow that we have implemented a viable solver the next step is implement a brute force strategy and create the first generator attempt.
For help and more information join our community, follow the blog, follow me on twitter, or follow me on g+ 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. |
Services > Desktop Liberation - the definitive resource for Google Apps Script and Microsoft Office automation > Recursion > Sudoku Generator and Solver >