Introduction
I started playing Sudoku when it became popular in the early 2000s. After playing many versions of the game on the Web, newspapers, and on iOS devices, I decided to see if I could write my own. Over the course of 4 days, this is the result.
This project demonstrates several programming concepts like Singletons, Shared code, Delegates and Events, multi-threading, as well as the MVC programming pattern.
Background
The basic Sudoku game is played on a 9 x 9 grid that is subdivided into 3 x 3 mini grids. The game starts out with some cells filled in with the numbers from 1 through 9. The object of the game is to fill in the blank cells so that each row, column and 3 x 3 mini grid contains each number only once. Here is a sample puzzle.
This article basically describes how the game was put together as well as some background on the design and code decisions I made along the way.
I used the MVC, or Model-View-Controller, programming pattern as a guide when I wrote the game. It is used to separate the different parts of the program into its logical components. The Model contains the data. The View contains all the UI related code. And the Controller contains the business logic as well as ties the Model and the View together. The View does not know anything about the data that is being displayed. Likewise the Model does not know how the data is being used or displayed. By separating the different logical parts of the code, it makes updating and maintaining the code much easier. Likewise, organizing the code in the same way makes it easier to maintain in the long run.
The following is a diagram showing how the different parts of the MVC pattern interact with each other.
There are several excellent articles online that describe this programming pattern in more detail.
Using the Code
The project was written using VS 2013. It is complete and can be loaded, compiled, and run.
Designing the UI
I started the project by designing the user interface, or UI, or the View, for the game. I could have used a Panel
control and just drew the 9 x 9 grid and game on it. But that would have required a lot of behind the scene code to check for mouse clicks and stuff like that. I could have used a DataGridView
control like other people have done. Or created my own custom User Control. But in the end, I decided to use a TableLayoutPanel
as the base grid.
I divided the TableLayoutPanel
into 3 rows and 3 columns to represent the outer grid. Into each cell, I added another TableLayoutPanel
which was divided into 3 rows and 3 columns to represent the smaller 3 x 3 grid. In each cell, I added a Label
control which I set the Dock
property to Fill
. I did this because each cell in the TableLayoutPanel
can only accept a single control. By using the TableLayoutPanel
and changing the CellBorderStyle
and the Background
color, it gave the board just the right emphasis to show the overall 9 x 9 grid as well as the 3 x 3 sub grids. I then added check boxes, buttons, etc. to complete the UI based on how I wanted the game to look and operate. The following is a picture of the UI of the game as seen in the designer view.
In Sudoku, the user needs to enter values into the empty cells. Some games use a series of number buttons at the top, bottom or side of the main grid. Others used a pop-up window. I chose to use the latter method for my game. That way, the user does not have to move the mouse far to enter values into the grid.
I added a new Form
to the project and then added buttons with the numbers 1
through 9
. I then turned off the border by setting FormBorderStyle
= none. I did this because the border would look bulky when placed on top of the main puzzle. Because of this, I added another button to the upper right corner with an "X
" on it to allow the user to close this window without entering a value. Here is how it looks in the designer view.
Because I want to position this number pad on the screen so that it overlays the cell that was just clicked, it is important to set the StartPosition
property to Manual
. Otherwise, Windows will ignore any attempts to position this form when you first open it.
Next came the UI logic. Basically, each button, checkbox, label, etc. has some kind of action to it. As I went along and worked on the UI logic, I added stub code in the Controller and some comments so that I know what to do later on. The code basically looks like this at the beginning.
In the code behind the form, I have this:
Private Sub btnNew_Click(sender As Object, e As EventArgs) Handles btnNew.Click
_clsGameController.NewButtonClicked()
End Sub
Then in the Controller
class, I have the following:
Friend Sub NewButtonClicked()
End Sub
To complete the View, I added two more forms to the project. One is an About/Help box and the other pops up when the puzzle is completed.
Once the basic code behind the UI has been programmed, the next step is to figure out how to create new puzzles.
Generating New Sudoku Puzzles
After playing many different games, I came to the realization that some commercial Sudoku games do not generate new puzzles. Instead, they are loaded with pre-built puzzles. And once you have played them all, the puzzles start repeating. After a while, the game then becomes stale. So, to that end, I want this game to create new puzzles. Knowing how the game is played and actually creating a new puzzle are two different things as I soon found out.
The first step was to figure out how to generate a valid Sudoku puzzle. As it turns out, creating a valid Sudoku puzzle is actually pretty simple. Many people have written examples that demonstrate how this is done. After looking at different examples, I adapted this one for my project:
The next part of the puzzle creation is to start removing cells based on the difficulty of the game. From various sources available on the Web, here is a table that rates the difficulty level of the game.
Difficulty Level | Number of Givens |
Very Easy | 50 - 60 givens |
Easy | 36 to 49 givens |
Medium | 32 to 35 givens |
Hard | 28 to 31 givens |
Expert | 22 to 27 givens |
Some would argue that difficulty ratings should also include what concepts or techniques are required to solve the puzzle. And that the more techniques required, the more difficult the rating. Thus two puzzles with the same number of givens could have different ratings. But that is a little beyond the scope of this project.
At the easier levels, I could just randomly remove cells and the puzzle would still be solvable. But as I have found out after playing many difficult or expert level puzzles, there comes a point when too many cells are removed and one has to start guessing in order to solve the puzzle. While some people would argue that that is part of the game, I feel that guessing detracts from the core concept of the game which is to solve the puzzle using pure logic alone and there is no logic in guessing.
So, I had to incorporate code to solve the puzzle as I removed cells. At first, I thought of the following code logic:
Create puzzle
Do
Remove x number of cells
Loop until puzzle is solvable
Or in flowchart form:
But I soon realized that the following is a better way to go about removing cells:
Create puzzle
Do
Remove one cell
Solve puzzle
Loop while puzzle is solvable and there are more cells to remove
And in flowchart form:
And that is to solve the puzzle as I remove one cell at a time. That way, if the cell I just removed renders the puzzle unsolvable, I can backtrack and choose another cell.
The next part was to figure out how to solve the game. Again, there are many ways to do it. Some wrote brute force algorithms, others used constraint programming, and yet others used Knuth's Dancing Links algorithm. As I looked at the different techniques, I decided to implement Knuth's Dancing Links algorithm. There are several excellent articles on the web that describe the technique as well as actual implementation using different programming languages. I incorporated this version into my project:
When I turned on Option Strict
in my project, this code generated several warnings and errors. It was easy enough to fix them all.
Once I figured out how to create a new Sudoku puzzle, the next task was how to manage the actual puzzle generation.
Puzzle Management
Easy level puzzles do not take long to generate. In fact, it is not noticeable at all. The harder level puzzles take some time to generate. For a positive gaming experience, I did not want the user to wait while the program generates a new game. To solve this issue, the game will spawn several background tasks to generate new games for each level. Each level will have 5 games waiting to be loaded when the user clicks on "New Game". And to further improve the user experience, the generated games will be saved when the program is closed so that the next time the user runs the program, the pre-generated games are loaded and the game is ready to go instantly.
It goes without saying that when this project is first loaded, it will take some time to create new games for each level since no pre-built games are saved with the project. So any subsequent loading/running will be much faster since it had a chance to build up some puzzles in the background and save them.
Actually, we do not really need to generate 5 games per level since even at the Expert level, it will take less time to generate a new game than it will take for the user to solve it. But just in case the user decides to click "New Game" several times before finally playing the game, we will maintain up to 5 new games per level.
Starting a background thread is very easy to do in .NET. Here is an example. First thing we need to do is add the System.Threading
namespace to our code.
Imports System.Threading
The code to actually start the thread looks like this:
Friend Sub CreateNewGame()
Dim tThread As New Thread(AddressOf GenerateNewGame)
tThread.IsBackground = True
tThread.Start()
End Sub
The code that the background thread will execute is this:
Private Sub GenerateNewGame()
Dim uCells(,) As CellStateClass = GenerateNewBoard()
Dim e As GameGeneratorEventArgs = New GameGeneratorEventArgs(uCells)
RaiseEvent GameGeneratorEvent(Me, e)
End Sub
This background thread is self-terminating. Meaning, once the puzzle is generated and the event raised, the thread terminates because there is nothing else to do.
There are other times when we need to keep a background thread running while the program is open. In this case, the code would look something like the following:
Private _bStop as Boolean
Private Sub GameMaker()
_bStop = False
Do
Loop Until _bStop
End Sub
The _bStop
variable allows the Controller to terminate this background task when the user closes the game. Otherwise, the code will just sit in an infinite loop. Technically, we do not need to use the _bStop
variable. When the program exits, all background tasks are aborted. But that is not a clean way to exit so we add the _bStop
variable. And when the application closes, we set the _bStop
variable to True
so that the loop can exit gracefully. We can add more code to check if the background tasks have exited properly before closing the application, but this is just a simple game. But in more complex programs where it is necessary to make sure that the background threads closed properly, by all means, perform those checks before closing the application. An example would be a background task that writes to a database. When the application closes, we want to be sure that all pending writes to the database are completed before closing the connection.
Another reason for using background threads is so that the UI is not bogged down while new puzzles are generated.
I use this code to manage the task of puzzle generation as well as managing the built puzzles. When the user requests a new puzzle, it is removed from the queue and a new game creation thread is spawned.
We could let this loop just keep going while the user is playing the game, but why chew up unnecessary CPU cycles when there is nothing for this thread to do? This could potentially slow down the computer in general and affect the whole gaming experience.
Basically, what we want to do here is once all 5 puzzles have been generated, to put the loop into some kind of suspended state until the next time when a new puzzle needs to be generated. To do this, we will use the AutoResetEvent
Class. Here is the class level declaration:
Private _MakeMoreGames As New AutoResetEvent(False)
The AutoResetEvent
allows two or more threads to signal each other. In the code above, when I need to suspend the background thread, the thread makes the following call:
_MakeMoreGames.WaitOne()
And when I need to wake up the thread, I make this call from another thread.
_MakeMoreGames.Set()
This is how threads can signal each other. When a puzzle is removed from the queue of puzzles, I call Set
on the AutoResetEvent
. This signals the background thread that is waiting to essentially wake up and create another puzzle.
The complete code for the GameMaker
subroutine looks like this:
Private Sub GameMaker()
Do
Try
SyncLock _objQLock
If _qGames Is Nothing Then
_qGames = New Queue(Of CellStateClass(,))
End If
If _qGames.Count < _cDepth Then
_clsGameGenerator.CreateNewGame()
End If
End SyncLock
Catch ex As Exception
End Try
_MakeMoreGames.WaitOne()
Loop Until _bStop
End Sub
At the beginning of the loop, the code checks to see if there are enough games in the queue. If not, it will spawn a thread to create a new game:
_clsGameGenerator.CreateNewGame()
Once the thread is spawned, it will then go to sleep:
_MakeMoreGames.WaitOne()
When the new puzzle is created, the event code looks like this:
Private Sub GameGeneratorEvent(sender As Object, e As GameGeneratorEventArgs) _
Handles _clsGameGenerator.GameGeneratorEvent
SyncLock _objQLock
If (_qGames Is Nothing) Then
_qGames = New Queue(Of CellStateClass(,))
End If
_qGames.Enqueue(e.Cells)
End SyncLock
_MakeMoreGames.Set()
End Sub
Once the new puzzle is queued up, it will send a signal to the main loop to wake up:
_MakeMoreGames.Set()
Then the game management thread will wake up and check to see if more games need to be created. By using the AutoResetEvent
class, the main loop does not need to keep running all the time. It runs when it needs to run.
Because I am creating a multi-threaded application, it is important to maintain thread safety when accessing the variables that hold the generated games. To maintain thread safety, I used the SyncLock
statement. In a nutshell, the SyncLock
statement ensures that multiple threads do not execute the protected statement block at the same time. SyncLock
prevents each thread from entering the block until no other thread is executing it.
In order for the SyncLock
statement to work, we need to declare a class level Object
variable:
Private _objQLock as New Object
Once we have declared the object, we can use the SyncLock
statement like this:
SyncLock _objQLock
_qGames = New Queue(Of CellStateClass(,))
End SyncLock
The SyncLock .. End SyncLock
block guarantees the release of the lock no matter how the code exits the block. Even in the case of an unhandled error condition.
Obviously, we need to use the same Object
variable whenever we are locking the Game
queue. In other words, for every data object we need to protect, it should have a matching Object
variable for use with the SyncLock
statement.
Another way to synchronize access to a code block is by using a Mutex. Here is another example using a Mutex
. We declare a class level Mutex
variable:
Private _mQueueMutex As New Mutex
And here is how it is used:
_mQueueMutex.WaitOne()
_qGames = New Queue(Of CellStateClass(,))
_mQueueMutex.ReleaseMutex()
The problem with this technique is that if an error occurs in the second line, then the third line might not execute and the Mutex
will not be released. In order to fix this, the code should be surrounded with a Try ... Catch
statement. So it will look like the following:
Try
_mQueueMutex.WaitOne()
_qGames = New Queue(Of CellStateClass(,))
Catch ex As Exception
Throw ex
Finally
_mQueueMutex.ReleaseMutex()
End Try
Or if the error can be safely ignored:
Try
_mQueueMutex.WaitOne()
_qGames = New Queue(Of CellStateClass(,))
Finally
_mQueueMutex.ReleaseMutex()
End Try
By putting the ReleaseMutex
inside the Finally
block, the Mutex
will be guaranteed to be released. Both techniques work, but using SyncLock
is only three lines of code and looks cleaner.
As I went along and coded the rest of the game generator, I ran across another issue with respect to the Random Number generator. Generally speaking, the Random Number generator is not really random. It looks random, but it is not. It uses a mathematical formula to generate a sequence of numbers where the output is, statistically speaking, "random." Try the following code in a console project:
Dim rnd1 As New Random
Console.Write("First sequence :")
For I As Int32 = 1 To 10
Console.Write("{0, 5}", rnd1.Next(100))
Next
Console.WriteLine()
Dim rnd2 As New Random
Console.Write("Second sequence:")
For I As Int32 = 1 To 10
Console.Write("{0, 5}", rnd2.Next(100))
Next
It will output the following:
First sequence : 37 65 63 35 30 4 76 89 53 1
Second sequence: 37 65 63 35 30 4 76 89 53 1
As you can see, even though we created two different instances of the Random
class, it generated the same sequence of numbers. Running it multiple times will generate a different sequence of numbers than shown above, but both sequences will still match. If we put this code in our game generator, it will basically generate the same game over and over again and that will be boring.
To get around this problem, the Random
class allows us to initialize the Random number generator with a seed value. The most common seed value used is the current date/time or number of seconds since midnight. To further "randomize" the seed value, I will mod
the Ticks
by 10,000 like so.
Dim tsp As New TimeSpan(DateTime.Now.Ticks)
Dim iSeed As Int32 = _
CInt((CLng(tsp.TotalMilliseconds * 10000) Mod Int32.MaxValue) Mod 10000)
This way, it will generate a seed value between 0 and 9,999 instead of a really big number where only the lower digits will differ.
The next issue is how to implement this Random code in such a way as to ensure that only one instance of it is used throughout the game. The answer is the use of the Singleton pattern. The Singleton pattern is a way to restrict the instantiation of a class to a single object. There are several ways to implement the pattern and searching the Web will yield many examples.
Here are two ways to implement the Singleton pattern. The first method is called late instantiation. It is called that because the class is instantiated when it is first called upon to do something.
Friend Class SingletonClass
Private Shared _instance As SingletonClass
Private Shared _objInstanceLock As New Object
Private Sub New()
End Sub
Friend Shared Sub DoSomething()
If _instance Is Nothing Then
SyncLock _objInstanceLock
If _instance Is Nothing Then
_instance = New SingletonClass
_instance.InitInstance()
End If
End SyncLock
End If
_instance.DoSomethingInstance()
End Sub
Private Sub DoSomethingInstance()
End Sub
Private Sub InitInstance()
End Sub
End Class
Here is another way to implement the Singleton pattern. This is referred to as lazy instantiation because the class is instantiated when the GetInstance
function is first called. The GetInstance
property needs to be called first before any of the other methods or properties of the class can be used.
Friend Class SingletonClass
Private Shared _instance As SingletonClass
Private Shared _objInstanceLock As New Object
Private Sub New()
End Sub
Friend Shared ReadOnly Property GetInstance As SingletonClass
Get
If _instance Is Nothing Then
SyncLock _objInstanceLock
If _instance Is Nothing Then
_instance = New SingletonClass
_instance.InitInstance()
End If
End SyncLock
End If
Return _instance
End Get
End Property
Friend Sub DoSomething()
End Function
Private Sub InitInstance()
End Sub
End Class
In both examples, the New
constructor is declared with the Private
modifier. This helps enforce the Singleton pattern because it prevents other people from creating their own instance. Search the Web for a detailed explanation for the differences between the two and when to use them.
To use the first Singleton pattern, we just simply call it this way:
SingletonClass.DoSomething
To use the second pattern, we have to create a variable to hold the instance.
Dim instance as SingletonClass
Then we need to get an instance before we can use the functions within the Singleton
class.
instance = SingletonClass.GetInstance
instance.DoSomething
The first method looks to be easier since one does not have to remember to first get an instance before using it. But there are pros and cons to both methods and the Web talks about them in great detail.
If we look closely at the second example, there are several variables and methods that have the Shared
modifier. The Shared
modifier basically indicates that the function or variable exists at all times. Without the modifier, it will only exist when an instance is created. A Shared
function cannot access an instance variable, but an instance function can access a Shared
function or variable.
So, in the following code:
instance = SingletonClass.GetInstance
instance.DoSomething
The first line loads an instance of the class by calling the Shared
function GetInstance
. Then in the second line, we can call the instance method DoSomething
.
There are times when the program has code that is needed all over the place. An example would be checking the index variable to make sure that it is between 1
and 9
.
Friend Class Common
Friend Shared Function IsValidIndex(iIndex As Int32) As Boolean
Return ((1 <= iIndex) AndAlso (iIndex <= 9))
End Function
Friend Shared Function IsValidIndex(uIndex As CellIndex) As Boolean
Return (IsValidIndex(uIndex.Col, uIndex.Row))
End Function
Friend Shared Function IsValidIndex(iCol As Int32, iRow As Int32) As Boolean
Return (IsValidIndex(iCol) AndAlso IsValidIndex(iRow))
End Function
Friend Shared Function IsValidStateEnum(iState As Int32) As Boolean
Return ((0 <= iState) AndAlso (iState <= 4))
End Function
End Class
One can say that is overkill because we wrote this game and everything should be between 1
and 9
. That is true, but if you are working on a large project with a group of people, it would help to enforce this rule just in case someone did not get the memo about the index limits. One can then extend this function to throw an error if the index is outside of the valid range. Here is an example:
Friend Shared Function IsValidIndex(iIndex As Int32) As Boolean
If ((1 <= iIndex) AndAlso (iIndex <= 9)) Then
Return True
Else
Throw New Exception("Index is outside of the valid range of 1 through 9.")
End If
End Function
If we look at the Common
class above, the first three functions have the same name, IsValidIndex
. This is called overloading
a method which is part of the Object Oriented Programming paradigm. We use the same name because it does the same thing: it checks to make sure the index is between 1
and 9
, inclusive. The difference between the three functions is the parameter list. This is called the signature of the method. Based on the signature, the compiler then knows which function to use.
Finally, when a game is generated, how do we go about and notify somebody that a new game was just created and to queue it up with the rest of the games? There are several ways to do this. I could have coded it in such way that once the game is created, to have that same thread queue it up. But what is the fun in that. Besides, it can get messy because we would then need to expose the data variables to other classes and pass the class instance around ... messy coding for sure and a nightmare to maintain.
Since I am using background threads to generate the games, I thought it best to use Events and Delegates to do this kind of notification. The first part is to declare a delegate and the matching event like so:
Friend Delegate Sub GameGeneratorEventHandler(sender As Object, e As GameGeneratorEventArgs)
Friend Event GameGeneratorEvent As GameGeneratorEventHandler
I could have declared it this way as well:
Friend Delegate Sub GameGeneratorEventHandler(uCells(,) as CellStateClass)
Friend Event GameGeneratorEvent As GameGeneratorEventHandler
The difference is in the parameters of the Delegate declaration. But to maintain the same style used by Windows Forms Controls, I used the first method. This requires that I create my own custom EventArgs
class:
Friend Class GameGeneratorEventArgs
Inherits EventArgs
Private _uCells(,) As CellStateClass
Friend ReadOnly Property Cells As CellStateClass(,)
Get
Return _uCells
End Get
End Property
Friend Sub New(uCells As CellStateClass(,))
_uCells = uCells
End Sub
End Class
Note the use of Inherits EventArgs
in the class declaration. So, once the new puzzle is generated, I create an EventArgs
object and pass it to the RaiseEvent
delegate.
Dim e As GameGeneratorEventArgs = New GameGeneratorEventArgs(uCells)
RaiseEvent GameGeneratorEvent(Me, e)
On the other side, the Game Manager class contains the following declarations and event listener:
Private WithEvents _clsGameGenerator As GameGenerator
Private Sub GameGeneratorEvent(sender As Object, _
e As GameGeneratorEventArgs) Handles _clsGameGenerator.GameGeneratorEvent
End Sub
Later on, I added a timer to the game so that the user knows how long it takes for him/her to solve the puzzle. The timer also uses Events and Delegates to tell the program when time has expired.
When the timer expires, it will update a label on the UI to indicate how much time has expired. Because the timer runs in a background task, it cannot update the label directly. Instead it must use Invoke
to pass the call to the proper thread where the control was created. Let me show you how it is done. First, we need to declare a callback routine.
Private Delegate Sub SetStatusCallback(sMsg As String)
Then, in the function that sets the Label
text, here is how the code looks:
Private Sub SetStatusText(sMsg As String)
If lblStatus.InvokeRequired Then
Dim callback As New SetStatusCallback(AddressOf SetStatusText)
Me.Invoke(callback, New Object() {sMsg})
Else
lblStatus.Text = sMsg
End If
End Sub
First, we check if the Label
needs to be invoked by calling InvokeRequired
on the Label
. If true
, then create the callback routine and Invoke
it. Otherwise, just update the Label
text..
Up to this point, we have created the basic UI as well as the game generation and management code. Next comes the Model.
Building the Model
The Model is basically a place where the data for the game is stored. So when the user clicks on "New Game," the Controller will load the Model with a new game from the Game Manager. The Controller is in charge of making changes to the Model's data based on user input from the View. Theoretically, the Model is not supposed to contain any business logic or code to manipulate the data. It just contains data. However, I made one small concession.
When playing Sudoku, one aspect to solving the game is entering notes or pencil marks into empty cells. Notes are basically numbers that a particular cell can possibly contain. For example:
In the highlighted cell above, the numbers 1
, 4
, and 9
are possible answers. This is because the other numbers are already represented in the column or 3 x 3 grid where this cell is located. To help the user, the program will generate notes. Since the notes are part of the data, I put the code to generate the notes in with the Model
class. So, when the Model
is loaded with a new game, one of the first things it does is generate notes.
The program will use the basic rule of Sudoku when generating notes for the user. And that is, the numbers 1
through 9
can appear in each row, column, or 3 x 3 grid only once. If a number is in the row, column, or 3 x 3 grid, it will be eliminated from the notes.
Controller
Once the Model is built, the last part is to build the business or game logic. All that goes into the Controller
class. Up to now, all the calls made by the UI are just pointing to stub code in the Controller
class. The game logic was actually the easiest part of the project to code.
I just wrote the code to all the stub code that was generated earlier when I built the UI. The challenging part was highlighting the cell that was just selected. In order to draw directly on the control, I needed to pass the graphics object for the control to the Controller
. So I had to modify the parameters of the stub code.
Here's the code that draws the highlight border around the selected cell:
Private Sub DrawBorder(uSelectedCell As CellIndex, _
e As PaintEventArgs, bHighlight As Boolean)
With _lLabels(uSelectedCell.Col, uSelectedCell.Row)
Dim highlightPen As Pen
If bHighlight Then
highlightPen = New Pen(Brushes.CadetBlue, 4)
Else
highlightPen = New Pen(.BackColor, 4)
End If
e.Graphics.DrawRectangle(highlightPen, 0, 0, .Width, .Height)
highlightPen.Dispose()
End With
End Sub
Once I determine the pen color, either highlight or unhighlight, I then draw a rectangle around the border of the Label. The Pen
object has a width of 4 pixels so it is easily visible.
e.Graphics.DrawRectangle(highlightPen, 0, 0, .Width, .Height)
Notice I passed the PaintEventArgs
into this function since that is where the Graphics
object is located. This comes from the Paint
event of the Windows Forms control.
Private Sub LabelA1_Paint(sender As Object, e As PaintEventArgs) Handles LabelA1.Paint
_clsGameController.PaintCellEvent(1, 1, e)
End Sub
Of course, there are several other functions between this one and the DrawBorder
function above. But the point is, I pass the PaintEventArgs
to the Controller just in case it needs to draw directly on the Label
control.
Also, when displaying the notes for empty cells, I drew them directly on the control rather than setting the text of the Label
control.
Private Sub DrawNotes(iCol As Int32, iRow As Int32, e As PaintEventArgs)
With _Model.Cell(iCol, iRow)
If .HasNotes Then
Dim drawFont As New Font("Arial", 8)
For I As Int32 = 1 To 3
For J As Int32 = 1 To 3
Dim noteIndex As Int32 = J + ((I - 1) * 3)
If .Notes(noteIndex) Then
With _lLabels(iCol, iRow)
Dim X As Int32 = CInt((.Width / 3) * (J - 1))
Dim Y As Int32 = CInt((.Height / 3) * (I - 1))
e.Graphics.DrawString(noteIndex.ToString, _
drawFont, Brushes.Black, X, Y)
End With
End If
Next
Next
drawFont.Dispose()
End If
End With
End Sub
Once I determine I need to draw notes in the cell, I get a Font
object with the Arial
font in size 8
:
Dim drawFont As New Font("Arial", 8)
I then calculate the X
and Y
coordinates of where to write the number with the following:
Dim X As Int32 = CInt((.Width / 3) * (J - 1))
Dim Y As Int32 = CInt((.Height / 3) * (I - 1))
Then, I finally draw the number out with the following line:
e.Graphics.DrawString(noteIndex.ToString, drawFont, Brushes.Black, X, Y)
All this code is found in the Controller
class. One could make the argument that the actual drawing code should be placed in the View since that is the function of View. And the Controller
should only contain the gaming logic because that is the function of the Controller
. In this case, the Controller
's job is to do all the calculations and then tell the View what to draw and where. Maybe in a future version, I will do just that.
Saving User Settings
Saving settings is easy to do in VS 2013. Just pull up the Project
properties, click on the Settings Tab on the left side and create all the settings that you need.
The settings can then be accessed in code by using the following syntax:
My.Settings.[setting name]
Here is an example from the project:
cbDifficultyLevel.SelectedIndex = My.Settings.Level
Here, I am setting the combo box control to the last Level
setting that was saved.
Because the Scope of the settings are set to User
, the settings will be saved to the following location:
[user directory]\AppData\Local\SudokuPuzzle\
SudokuPuzzle.vshost.exe_Url_jnscgesaimzkgsbjhoygfwifnfxk1g51\1.0.0.0\user.config
The actual directory name will be different on different machines due to the random string generated by Windows. But that is the general location of the settings.
[user directory]\AppData\Local\SudokuPuzzle\...
Namespace and Wrapping Up
One final addition to the code is the use of Namespace
. By using Namespace
, I can split up the code into the different parts of the MVC pattern. So the code that belongs to the Model
will be surrounded by the following:
Namespace Model
Friend Class GameModel
...
End Class
End Namespace
To access the GameModel
class in the example above, the fully qualified name is SudokuPuzzle.Model.GameModel
. Using Namespace
helps enforce the MVC programming pattern. One caveat, Windows Forms do not like being enclosed in a Namespace
. The SudokuPuzzle
root Namespace
is assigned in the application properties.
Also, the main entry point for the program is the Main
form. Normally, in the MVC model, the Controller
is the main entry point. But for this project, I just left the main entry point as the Main
form since the project was created as a Windows Forms Application.
Here is how the game looks when it is running:
Points of Interest
When I started planning out the code to solve the puzzle, I thought I would implement it the way a human would. That is by using several techniques to arrive at the answer for each empty cell. But as I went along, I determined that that was not the most efficient way to solving a puzzle. So I started researching the different ways other people have solved this problem. One of the techniques that stood out for me was Knuth's Dancing Links algorithm.
I had always thought that Sudoku was played on a 9 x 9 grid that was subdivided into 3 x 3 smaller grids. But during my research, I discovered that there are several variations to the Sudoku game. Perhaps in the future, I will extend this game to incorporate some of the other variants like the 4 x 4 grid or even the 16 x 16 grid.
Starting with .NET, arrays are all zero based regardless of language used. Throughout my code, I used the indices 1 through 9 instead of 0 through 8 to make things simpler for me. Essentially, I ignore the zero based element of the array.
When planning the grid, I decided to use Excel's way of addressing the cells. And that is by [col][row]. Here is how it looks:
Here is how I addressed each 3 x 3 grid:
I thought about coding a custom Collections
class for the Model
. But to keep things simple, I decided not to.
It is tempting to use For Each
when looping through an array or list of data. However, there is a catch. The element is just a copy of the original. So, if you need to manipulate the object, you need to use a For =
loop instead. For example: when clearing out the array, it is tempting to do it this way:
For Each Item As CellStateClass In _uCells
Item = Nothing
Next
But because we are manipulating the actual elements of the array, we need to do it this way instead:
For I As Int32 = 0 To 80
_uCells(I) = Nothing
Next
As demonstrated by the Singleton pattern and the SyncLock/Mutex
statements, there is no right or wrong way to code a solution. Sometimes, it is just a matter of personal preference. This is where the Art of Programming comes into play.
During a code review I participated in many years ago, a junior programmer wrote this piece of code:
Dim bFlag as Boolean
...
Select Case bFlag
Case True
Case Else
End Select
We spent some time debating the merits of coding such a statement. Needless to say, this code passed the review since technically, it works. Personally, I would never be caught dead writing code like that. For me, the preferred method is:
If bFlag Then
Else
End If
Here is a list of features that I left out in this version of the game:
- When the "Puzzle Complete" dialog pops up, add some kind of fireworks display in the background.
- Save the state of game when the user quits in the middle of a game and restore it the next time the program loads.
- When the user pauses the game, doodle something on the blank panel that hides the game.
- Keep track of the 10 best times per level.
- Allow the user to change the color scheme or look of the game.
- Implement the print routine so the user can print out the game grid.
- Implement the masking pattern so that it is symmetrical on the vertical axis.
- Make the number of pre-generated games variable. Right now, it is hard coded to 5.
- Display at the bottom right corner of the main screen, the number of games that have been generated per level.
History
- 2014-10-24: First release of the code/article