Create a Sudoku Puzzle Generator using VB.NET - Creating Puzzles
(Page 3 of 6 )
The Generate()method is called to create new puzzles. A brute force approach is actually employed to generate a complete, solved puzzle. The heart of this method is depicted in Listing 2.
Listing 2 Fill a new puzzle with numbers
'Fill Board with Numbers
oRnd = New Random
byNumCount = 1
Do
byCol = oRnd.Next(1, 10)
byRow = oRnd.Next(1, 10)
If (mbyary_SudokuBoard(byCol, byRow) = 0) Then
byOrgCurrSudokuNumIndex = byCurrSudokuNumIndex
bNoCollision = False
Do
If isCollision(byCol, byRow, mbyary_SudokuNumbers(byCurrSudokuNumIndex)) Then
byCurrSudokuNumIndex = (byCurrSudokuNumIndex + 1) Mod (NUM_OF_REGIONS + 1)
If (byCurrSudokuNumIndex = 0) Then byCurrSudokuNumIndex = 1
Else
mbyary_SudokuBoard(byCol, byRow) = mbyary_SudokuNumbers(byCurrSudokuNumIndex)
bNoCollision = True
End If
Loop Until bNoCollision OrElse _
(byOrgCurrSudokuNumIndex = byCurrSudokuNumIndex)
If bNoCollision Then
byNumCount += 1
Else
'Backtrack a bit. Find a box that has been filled in and clear it so that we can
'regenerate another available solution for it.
Do
byCol = oRnd.Next(1, 10)
byRow = oRnd.Next(1, 10)
If (mbyary_SudokuBoard(byCol, byRow) <> 0) Then
mbyary_SudokuBoard(byCol, byRow) = 0
byNumCount -= 1
End If
Loop Until (mbyary_SudokuBoard(byCol, byRow) = 0)
End If
End If
Loop Until (byNumCount > MAX_NUM_OF_CELLS)
A row and column are randomly selected and used to retrieve the value of an element or cell in the mbyary_SudokuBoard array. If the cell is found to be empty (by the presence of the number 0), the next available number in the mbyary_SudokuNumbers array is selected. The isCollision() method is used to check the validity of the move and if legitimate, the cell is assigned the number and the solved cell count is increased by one. Collisions occur when the selected number is found more than once in the cell’s row, column, or immediate region. In the event of a collision, each remaining number in the mbyary_SudokuNumbers array is exhausted until a collision is undetected.
In the event that a collision is unavoidable, some backtracking is required. In this case, a previously assigned array cell is randomly selected and cleared and the count of solved cells is reduced by one. This event effectively signals the algorithm pursue a different solution path. Processing continues until all 81 cells are filled at which point the completed puzzle array, mbyary_SudokuBoard, is copied to the mbyary_OrgSudokuBoard array. The private method RemoveNumbers()is then called to randomly remove numbers from the completed puzzle array, based on the complexity chosen by the player. The method wraps up by copying the selected complexity to an unused element in the mbyary_SudokuBoard array. This element’s value is fundamental to setting up a loaded puzzle’s complexity.
At this point, since we are talking about generating puzzles, you should be aware that some Sudoku puzzles can have multiple solutions, based on the amount of numbers removed. The algorithm does not take this into account and simply generates one valid solution. Player input is validated against this one and only solution. Altering the algorithm to generate all possible solutions for a puzzle is left to you as an optional (and adventurous) exercise.
Next: Saving and Loading Puzzles >>
More Visual Basic.NET Articles
More By Pete Rodriguez