We had managed to generate a completed puzzle from scratch in the previous section, following the first step of creating a viable solver. The next step is to take the completed puzzle and remove cells from it till we get to some target reduction, all the while checking that what we have left is still 'human solvable'. Although this is tricky, the technique is almost identical to the one used to generate the completed puzzle, except we are taking things away and checking they are still solvable rather than adding things. That means we can just pretty much re- use the recursion code so it shouldn't take too long. As far as generating according to different dimensions and difficulty or worrying too much about formatting is concerned, we will do that later.
The first target is to consistently generate a 3 x 3 grid, with 27 givens, and make sure they can be solved.
This is the very first puzzle generated by our solver.
So in this case we simply clear a cell one at a time until its no longer solvable, and backtrack if we havent reached the required number of cells. Again, this is a recursive Sub, which calls another recursive Sub (Solve). Another thing that is going on here is that actually we dont remove cells one at a time. We remove multiple cells at once, reducing the number if it results in an unsolvable grid. The purpose here of course is to minimize the number of time we have to go through a solving cycle.
Private Sub CoverIterate()
' create a puzzle from a completed grid
Dim iCollectionIndex As Long, sc As cSudCell, ix As Long
' remember where we were
iCollectionIndex = pGrid.CollectionIndex
Set sc = pGrid.nextrandomSure
If Not sc Is Nothing Then
' clear a sure and see if its still solvable
' optimization of multiple at the same time
For ix = 2 To .nAtOnce
Set sc = pGrid.nextrandomSure
If sc Is Nothing Then
Debug.Assert Not .isScrewedUp
If .isSolved Then
pGrid.nAtOnce = pGrid.nAtOnce + 1
' clear the solve effect
' reached target? .. TODO need to add something about difficulty
If .GridSureCount <= targetnCells Then
' we can still keep going
If Not isCovered Then
' check we are going to delete the top of the stack
Debug.Assert pGrid.CollectionIndex = pCollection.Count
Set pGrid = pCollection(iCollectionIndex)
pGrid.nAtOnce = pGrid.nAtOnce - 1
Loop Until isCovered Or sc Is Nothing
Now we have a viable solver and generator, we really want to soak test it by generating lots of puzzles and then solving them to see what is going to break. However, generating puzzles really is quite compute and memory intensive, so we will also use the soak test to profile the code. We will use the optimization project on this site which you can find on the downloads page to see where we need to tweak for performance.
For help and more information join our community, follow the blog, follow me on twitter, or follow me on g+
Services > Desktop Liberation - the definitive resource for Google Apps Script and Microsoft Office automation > Recursion > Sudoku Generator and Solver >