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.
Page Content
hide
The first puzzle
This is the very first puzzle generated by our solver.
The code
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 Do Set sc = pGrid.nextrandomSure If Not sc Is Nothing Then ' clear a sure and see if its still solvable newGrid pGrid With pGrid ' optimization of multiple at the same time .Item(sc.Index).clearSure For ix = 2 To .nAtOnce Set sc = pGrid.nextrandomSure If sc Is Nothing Then Exit For Else sc.clearSure End If Next ix .solve Debug.Assert Not .isScrewedUp If .isSolved Then pGrid.nAtOnce = pGrid.nAtOnce + 1 ' clear the solve effect .revertToGiven ' reached target? .. TODO need to add something about difficulty If .GridSureCount <= targetnCells Then makeCovered Else ' we can still keep going CoverIterate End If End If End With If Not isCovered Then ' check we are going to delete the top of the stack Debug.Assert pGrid.CollectionIndex = pCollection.Count pCollection.Remove (pGrid.CollectionIndex) Set pGrid = pCollection(iCollectionIndex) pGrid.nAtOnce = pGrid.nAtOnce - 1 End If End If Loop Until isCovered Or sc Is Nothing End Sub
Soak test
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 or follow me on Twitter.