.. and here is the codeThis is interesting in that it is not only recursive in of itself, but it also calls .Solve which resurses through with .Solveiterate.
Brute is implemented as method of the cPuzzle class. It will create a cloned instance of cSudGrid for each recursion, and destroy it if that path is not successful.
It also chooses which cells and which possibilities to try next, randomly, except that for efficiency reasons, the cells are kept sorted into least possibilities first order.
This will keep going, trying alternate paths and backtracking until it finds a solution to what starts as a blank Sudoku. Since there should always be a solution, it will only reach wrapup if something has gone wrong.
Private Sub Brute()
Dim ic As Long, indexOfCell As Long, ip As Long, iCollectionIndex As Long, iz As Long, indexInList As Long, idx As Long
Dim sc As cSudCell
'this one solves by brute force, and would be used for generating
' first find the next unsure cell
Set sc = pGrid.nextrandomUnSure
Debug.Assert Not sc Is Nothing
indexOfCell = sc.Index
' this instance of brute will deal solely with this cell, and recurse for the next one
' try every possibilty in a random order for this cell till one sticks
ip = pGrid.Item(indexOfCell).nextRandomPossibility
While ip <> 0
' clone a new grid for this particular route
iCollectionIndex = pGrid.CollectionIndex
newGrid pGrid
With pGrid
.Item(indexOfCell).makeSure ip
.solve
If .isSolved Then GoTo wrapup
' if still solvable then guess for the next cell along
If Not .isScrewedUp Then Brute
' the puzzle is solved...?
If isSolved Then GoTo wrapup
' if we get here then we have used a non viable guess, so backtrack by scrapping the current grid
pCollection.Remove (.CollectionIndex)
End With
' go back to the grid before we tried that abortive possibility and try another
Set pGrid = pCollection(iCollectionIndex)
ip = pGrid.Item(indexOfCell).nextRandomPossibility
Wend
wrapup:
' should only get here if all is solved
Debug.Assert isSolved
End Sub
Next stepsAs before the entire code will be is downloadable here. Now we have created a completed grid, the next step will be to remove items to the required level of difficulty, and we will have completed the generation of a puzzle. 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. 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 >