Create a Sudoku Puzzle Generator using VB.NET

Back in 1988, a game called Tetris became a worldwide phenomenon. At the time, I programmed my own PC version of it using Turbo Pascal. Recently, a friend of mine introduced me to Sudoku. Like Tetris, this puzzle game sparked a global fervor. I could download it for free from a number of sites, but what fun would that be? Instead, the learning experience and challenge would lie in coding it myself. Join me as I show you how to roll your own Sudoku puzzle generator.

For those of you that have never heard of it, Sudoku is a logic-based placement puzzle that garnered early popularity in Japan. The puzzle retained its current moniker from an abbreviation of the Japanese phrase, “the digits must remain single." The puzzle is comprised of a 9×9 cell grid sub-divided into 9 3×3 regions and several of these cells, called “clues," are pre-filled with the numbers 1 to 9. As its name implies, solving the puzzle entails filling the remaining empty cells with the numbers 1 to 9 so that they appear only once in each column, row, or region. Figure 1 shows a sample puzzle. For more in-depth information and links on Sudoku, I recommend going to the increasingly popular Wikipedia at http://en.wikipedia.org/wiki/Sudoku .


Figure 1. Screen Shot of Sudoku Generator


Puzzle Generator Features

I originally targeted the puzzle generator for mobile smart devices (as evident by the application’s small user interface footprint), due to the lure of playing it on my PDA or cell phone. Yet in writing this article, I decided to target the Window’s desktop so as not to convolute the review of the code with particulars about the Mobile Device API. In the near future, I’m looking forward to writing a second installment for the smart device platform. The application implements some pretty basic features. You can create new puzzles with varying degrees of difficulty, save and load them to and from disk for later enjoyment, or print them. The latter feature is especially useful if you prefer to leave your laptop at home and use a pencil to solve your puzzle the old-fashioned way. Check out the Enhancing the Puzzle Generator section below for some suggestions on how to further enhance the application.

{mospagebreak title=The User Interface}

Good application architecture usually calls for separation between the presentation and business (or logic) tier, and the generator incorporates this design approach. The design lends itself well to maintainability, scalability and reusability, which is important when we talk about porting the application to the mobile platform. For the most part, the user interface or UI handles player input and puzzle plotting. Available features and functions are exposed through the UI’s menu and any intensive processing is delegated to the cSudokuBoard class. Figure 2 displays the application’s File menu.


Figure 2. The Applications Main Menu

The File > New submenu is actually built dynamically. Listing 1 illustrates how this is done in the UI’s Load Event handler.

Listing 1 Build the New Submenu

‘Loop through puzzle complexity enumerated type and create dynamic menus and add

‘menu click event handler to each


Dim szAryNames As String() = System.Enum.GetNames(GetType(cSudokuBoard.enumComplexity))

Dim mnu As MenuItem


For Each sz As String In szAryNames


If Not String.Equals(sz, cSudokuBoard.enumComplexity.Uninitialized.ToString) Then


mnu = Me.mniNew.MenuItems.Add(sz)

AddHandler mnu.Click, AddressOf NewGameSelected


End If


Next ‘sz


Each element of the enumComplexity enumerated type exposed by the cSudokuBoard class is actually mapped to each MenuItem using the System.Enum.GetNames() method. Each MenuItem’s Click event is then hooked into the handler, NewGameSelected() . NewGameSelected() pulls double duty because it prepares the UI for both new and previously saved puzzles and discerns between them by interrogating its sender parameter. If a new puzzle is requested, this parameter holds the selected complexity MenuItem otherwise it is set to the value Nothing . New puzzles get directed to the cSudokuBoard class’ Generate() method that accepts the complexity parameter. Previously saved puzzles bypass the Generate() method, and instead get loaded from disk. In this case, the complexity is retrieved from the puzzle itself (more on this later).

The cSudokuBoard Class

The cSudokuBoard class encapsulates all of the logic for generating, checking, saving, loading, and printing puzzles. Puzzles are created or loaded and stored in arrays, which are virtual representations of the 9×9 cell grid. Actually, five private module-level byte arrays are defined to store data required for generation. Table 1 lists the arrays.


Array

Description

mbyary_OrgSudokuBoard

9×9 2-dimensional array holding puzzle solution

mbyary_SudokuBoard

9×9 2-dimensional array holding current puzzle state

mbyary_SudokuNumbers

1-dimensional array holding number samples for puzzle

mbyary_Boxes

1-dimensional array holding 9 3×3 puzzle regions

mbyary_IdentityMatrix

1-dimensional array holding identity matrix used to discover number collisions

Table 1. Key data arrays

The first two arrays are repopulated by the Generate() or Load() methods each time a player requests a new or previously saved puzzle from the UI. For new puzzles, the SelectNumbers() private method is called to populate mbyary_SudokuNumbers with random numbers from 1 to 9. The latter two arrays provide processing support and are initialized once in the class’s New() constructor. mbyary_Boxes identifies the rectangular coordinates (left, right, top and bottom array indexes) of the 9 regions within the 9×9 cell grid while mbyary_IdentityMatrix allows traversal of a cell’s region, the 3×3 cell grid encompassing the cell. Used exclusively by the isCollision() method, both arrays help to identify valid number placement during initial puzzle load and player input.

{mospagebreak title=Creating Puzzles}

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.

{mospagebreak title=Saving and Loading Puzzles}

Sometimes you might not be able to solve a puzzle at one sitting. That’s where the application’s save and load features come in handy. The Save() (see Listing 3) and Load() methods assist in this endeavor.

Listing 3 Save a puzzle to disk


Public Sub Save(ByVal szSaveFilePath As String)


‘This method accepts the full path and name of a file to save the contents

‘of the 9×9 2-dimensional byte arrays holding the puzzle’s current state and

‘solution. In addition, the selected complexity is saved in the 1st element (0,0)

‘of the puzzle’s current state array. Note that a vanilla binaryformatter is used

‘to serialize the array contents to a file.

Dim oFS As FileStream

Dim oFormatter As IFormatter

Dim szBaseFileName As String

Dim szBaseFilePath As String

Dim szBaseFileExt As String


Try


szBaseFileName = Path.GetFileNameWithoutExtension(szSaveFilePath)

szBaseFileExt = Path.GetExtension(szSaveFilePath)


szBaseFilePath = Path.GetDirectoryName(szSaveFilePath)

If Not szBaseFilePath.EndsWith("") Then szBaseFilePath &= ""


oFormatter = New Formatters.Binary.BinaryFormatter


‘Save original SudokuBoard

oFS = New FileStream(szBaseFilePath & szBaseFileName & szBaseFileExt, _

FileMode.OpenOrCreate, FileAccess.Write)

oFormatter.Serialize(oFS, mbyary_OrgSudokuBoard)


oFS.Close()


‘Save current SudokuBoard

oFS = New FileStream(szBaseFilePath & szBaseFileName & _

szBaseFileExt.Substring(0, 3) & "1", FileMode.OpenOrCreate, FileAccess.Write)

oFormatter.Serialize(oFS, mbyary_SudokuBoard)


Catch ex As Exception

If File.Exists(szBaseFilePath & szBaseFileName & ".*") Then

File.Delete(szBaseFilePath & szBaseFileName & ".*")

End If


Finally

If Not (oFS Is Nothing) Then oFS.Close()

oFS = Nothing


oFormatter = Nothing


End Try


End Sub


Both methods incorporate BinaryFormatters and FileStreams to de/serialize both puzzle arrays from and to disk. BinaryFormatters provide a way to take an object and break it up into a linear sequence of bytes, thereby making it easy to store and retrieve. The contents of the arrays are saved to and consequently loaded from two separate files. The UI supplies the name of the files to save/load by calling upon the easy-to-use SaveFileDialog and OpenFileDialog dialog boxes. As mentioned previously, the puzzle’s complexity is always saved within the mbyary_SudokuBoard array. During a load request, the UI code retrieves this value from the appropriate array element and uses it to properly set the loaded puzzle’s complexity in the File > New menu.

{mospagebreak title=Solving Puzzles}

The UI represents each numeric cell using a label control. Each label control restricts input to the numbers 1 through 9 and the spacebar, the latter used to clear out previous numeric entries. Positioning the mouse over a cell provides focus and tracking by highlighting the cell’s background (see Figure 3).


Figure 3. UI Data Entry


Data entry can be performed using the keyboard or mouse, the latter option stemming from the program’s initial design as a mobile application. I thought it best to allow input through successive taps of the screen with a mobile stylus. Naturally, I adapted this technique to the left mouse button. Clicking repeatedly on the mouse button cycles through the numbers 0 to 9, with 0 rendered as a space. UI handlers tied to the KeyPress and MouseUp label events catch all of the data entry. Ultimately all captured data is delegated to the class’ SetPuzzleCell() method. SetPuzzleCell() simply maps the number or space from the label to the underlying cell in the mbyary_SudokuBoard array and sets its value accordingly. In addition, if the move is deemed valid, the routine calls the isPuzzleSolved () method, shown in Listing 4 below. If you’re having trouble solving the puzzle and you need a hint, checking the Options > Show Solution menu on the UI will render the solution. Conversely, un-checking the menu reverts to the original puzzle’s state.

Listing 4 Check to see if a Puzzle has been solved


Public Function is PuzzleSolved(Optional ByVal bisKeystroke As Boolean = True) As Boolean


‘This method keeps track of real-time puzzle statistics and checks to see if the

‘puzzle has been solved. It uses the bisKeystroke parameter to discern if data entry

‘was the result of a keystroke or some other UI event. If a keystroke and puzzle

‘is found not to be solved, the method returns false. Otherwise, if a UI event

‘other than a keystroke occurred or if the puzzle is in fact solved, the

‘CompleteEventArgs module-level variable is set with the collected real-time statistics

‘and the CompleteEvent is raised.


‘Either this is a newly loaded game or board has yet to be initialized for a new game.

‘Previous game has not been canceled.

If (mo_CEA Is Nothing) OrElse (mbyary_OrgSudokuBoard(1, 1) = 0) Then


mo_CEA = New CompletedEventArgs(0, False, New TimeSpan(Now.Hour, _

Now.Minute,Now.Second))


Return False

Exit Function


End If


‘Loop through array and see if puzzle has been solved by comparing against

‘solution array.

Dim bisSolved As Boolean = True


mo_CEA.TotalGuesses = mi_TotalGuesses


For byY As Byte = 1 To (mi_ActualBoardWidthAndHeight – 1)


For byX As Byte = 1 To (mi_ActualBoardWidthAndHeight – 1)


If (mbyary_SudokuBoard(byX, byY) <> mbyary_OrgSudokuBoard(byX, byY)) Then


bisSolved = False

Exit For


End If


Next ‘byX


Next ‘byY


If (Not bisSolved) Then


‘Check if player started a new game, effectively canceling the existing game.

‘Or the player simply was entering a cell value for the current puzzle

If bisKeystroke Then


Return False

Exit Function


End If


mo_CEA.isCanceled = True


End If


mo_CEA.ElapsedTime = New TimeSpan(Now.Hour, Now.Minute, _

Now.Second).Subtract(mo_CEA.ElapsedTime)


RaiseEvent CompleteEvent(Me, mo_CEA)


ClearBoard()


mi_TotalGuesses = 0

mo_CEA = Nothing


Return True


End Function


This method conducts two important functions. Firstly, it compares each cell of the puzzle array with each cell of its corresponding solution to determine if the puzzle is solved. Secondly, it collects interesting tidbits of information which it broadcasts back to all event subscribers should the puzzle be solved. It packages statistics such as the amount of numeric guesses made and the time taken to solve the puzzle into the CompletedEventArgs EventArgs object, which is passed as a parameter to the CompleteEvent Event. When the puzzle is solved, the event is raised and sunk by the UI and the data is used to report player results.

{mospagebreak title=Printing Puzzles}

While developing the generator, I couldn’t think of an easy and succinct way to print the puzzle. I toyed with simulating a printable grid using ASCII line characters, Excel and various third-party tools, but each potential solution fell short of what I envisioned, even introducing needless complexity. This feature almost remained on the enhancement list until I thought about an old program I wrote back in the VB3 days that facilitated screen captures.

The idea of presenting a printable, WYSIWYG rendition of the puzzle to the user was appealing, but I didn’t have the old code and writing it from scratch was not an option, especially for an optional feature. So it was as good a time as any to “borrow” some code. My web search led me to the Developerfusion UK website and an article written by James Crowley entitled "Capture a Screen Shot". You can find the article and code at http://www.developerfusion.co.uk/show/4630/. I ported a portion of the original C# code to VB and you’ll find it in the cScreenCapture class. Due to constraints on this article’s length, I’ll defer study of its logic to you.

The CaptureWindow() method is tasked with getting a snap shot of any window given its handle. As you might expect, the call to it is encapsulated in the cSudokuBoard class’ Print() method. The File > Print menu’s Click Event handler passes the handle of the panel control (containing the numeric labels that comprise the 9×9 cell puzzle grid) to the method and it returns a bitmap rendition of the puzzle. To scale and print the returned screen shot, the PrintDocument object and PrintPreviewDialog dialog box are employed. The PrintDocument defines “a reusable object that sends output to a printer” while the PrintPreviewDialog dialog box allows us to preview the output before sending it to the printer. By hooking a handler into the PrintDocument’s PrintPage event and assigning the document to the Document property of the dialog, we can actually render our bitmap onto the PrintDocument. The call to the ShowDialog method sets this all in motion, raising the PrintPage event handler, PrintPuzzleBoard() shown in Listing 5. The routine literally owner-draws the puzzle bitmap and some text onto the canvas of the PrintDocument and displays the document for preview (See Figure 4) and eventual printing.

Listing 5 Render the puzzle onto the print preview document


Private Sub PrintPuzzleBoard(ByVal sender As Object, _

ByVal e As System.Drawing.Printing.PrintPageEventArgs) e System.Drawing.Printing.PrintPageEventArgs)


‘This subroutine sinks the PrintPage event raised by the PrintDialog.

‘It draws header and footer information and the captured puzzle bitmap unto the

‘graphics canvas of the PrintDocument.

‘Use GDI+ to scale the image for printing

With e.Graphics


‘Make sure to draw the puzzle image within the bounds of the printed page’s margins

‘Image is scaled and centered automatically

.DrawImage(mbmp_PuzzleBoardImage, e.MarginBounds)


.DrawString(msb_PuzzlePrintHeader.ToString & me_SelectedComplexity.ToString, _

New Font("MS Trebuchet", 20, FontStyle.Bold), Brushes.Blue, _

e.MarginBounds.X, e.PageBounds.Y + 50)


.DrawString(msb_PuzzlePrintFooter.ToString, New Font("MS Trebuchet", 10, _

FontStyle.Bold), Brushes.Blue, e.MarginBounds.X, _

e.MarginBounds.Bottom + 5)


End With


e.HasMorePages = False


End Sub


Figure 4. The Puzzle Print Preview

Enhancing the Puzzle Generator

During the design phase, I came up with various ideas for improving the generator, but alas there are only so many hours in a day and I could not implement them all. Following are some of the better enhancement ideas you may wish to incorporate. Drop me an email if you do get around to implementing any or if you come up with a great one yourself!

1. Include some AI to generate challenging puzzles.

2. Create a user-drawn Graphical User Interface (GUI).

3. Support multiple solutions for puzzles of greater complexity.

4. Create a timed version of the puzzle.

5. Substitute colors, shapes, or text for the numbers.

In general, I find that nothing exercises a computer’s capabilities better than the development of a great puzzle, strategy, or arcade game. It’s not only an entertaining endeavor, but a rich learning experience. Hopefully you have come away with a better understanding of Sudoku and the different techniques used to provide its features. Maybe the next time you won’t be in such a hurry to buy or download the latest must-have game and instead you’ll challenge yourself to program it. Hope you enjoyed this as much as I did. Happy Programming and Gaming!

[gp-comments width="770" linklove="off" ]