First Generated Puzzle


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.

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

        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
                For ix = 2 To .nAtOnce
                    Set sc = pGrid.nextrandomSure
                    If sc Is Nothing Then
                        Exit For
                    End If
                Next ix
                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
                    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,  follow me on twitter, or follow me on g+