14,219,408 members

Sudoku and Smart Client techniques

Rate this:
21 Aug 2005Ms-PL
This article will develop a Sudoku game based on a web service, while presenting useful development techniques of Smart Client applications.

Section 1: Sudoku

If you don’t know what Sudoku is, you can return to your spaceship and fly home. On your way back, you can stop here and find out what it is.

So, why Sudoku?

I began playing Sudoku very recently and found the game very funny and addictive. When you play Sudoku you finally reach a point where you need to find a way to mark the possible values a square has, since you can't remember all of them. Some people write the possible numbers in small, the problem with this method is that if you write it with a pencil it's not readable and if you use a pen it becomes messy. Another method is to use points as markers for the available possibilities, every number has its own position, for example, number 1 is represented as a point in the top-left corner of the square, number 5 is in the middle of the square, and number 9 is in the bottom-right corner.

An easy way to remember this is to look at the phone keypad.

So, after finishing all the paper-based Sudoku puzzles, I searched the net for more. I found plenty of puzzles but there I encountered a major problem. You see, you can't put points on the screen! I actually tried to play with MS Paint but I quickly found out that writing the number '2' with the mouse is as hard as proving Fermat's last theorem.

So here I was, with plenty of puzzles but no way to play with them. Suddenly a new mail arrives! "..Code Project Newsletter.. ..Smart Client competition..".

Well, if you read this article you know what happened next.

Section 2: Architecture

So, after deciding to write a Sudoku Smart Client, I started to think about the general architecture and design. These are my insights:

1. A custom control is needed that will be in charge of drawing the Sudoku puzzle and will interact with the user so that he can mark the available possibilities as points.
2. Several map sizes (6x6, 9x9, 16x16) and difficulty levels (Easy, Medium, Hard) should be supported.
3. Application settings like selected map size and difficulty level should be saved to disk along with high scores information.
4. A web service should be used to:
1. get the Sudoku puzzle data,
2. and supply internet-wide high scores.
5. The Smart Client should work both on Pocket PC and on normal PC.
6. The Smart Client should work fast (!). This insight actually came a little later, after I came to realize that performance requires special attention while developing a Smart Device. Many of the techniques mentioned in this article are used due to performance reasons.

The following sections discuss these issues in detail.

As a general note, the development was done using the .NET Compact Framework and was tested using my WinXP system and a Pocket PC emulator. Feel free to comment if you find any bug or incompatibility with your Smart Device.

Section 3: SudokuMap and SudokuCell

Section 3.1: General

If you open the source code you will see that the project name is Sudoku2, here is what happened to the project Sudoku:

The first thing I coded was a control named `SudokuCell` that supports:

• Drawing the selected number, if a number is selected.
• Drawing the semi-selected possibilities as points.
• Allow user click on a spot on the cell to set it as a possibility.
• Allow double click on a spot on the cell to select the value.
• Do not allow user interaction when the cell is set as read only.

I'll focus on the interesting aspects and leave the tedious parts aside, like calculating the cell's size and checking which number was selected according to the position of the click. If you are interested in this, look at the source code.

Section 3.2: Minimize amount of controls

My initial design was to create multiple instances of `SudokuCell`, one per each cell in the Sudoku puzzle. So in the classic mode (9x9 grid), I had 81 controls on my main form. I even wrapped them in a nice class named `SudokuMap` so that I will be in charge of creating the controls according to the selected map size etc.

So far so good, until I ran the application. It took the application more than two minutes to load on the Pocket PC emulator. When the same executable was run on my normal PC, the main form was loaded instantly.

After searching for the wasted time, I discovered that the problematic command was `Controls.Add` and not the 81 constructors or anything else; just adding the `SudokuCell` controls to the form's `Controls` collection. I even tried to add standard controls like labels but I got the same result. `Controls.AddRange` would have worked better but Microsoft chose not to include this function in the .NET Compact Framework.

After that I created a new project `Sudoku2` and rewrote `SudokuCell` and `SudokuMap` classes so that `SudokuMap` is the only control that is added to the form and `SudokuCell` became a class that does not inherit from `Control` but is still responsible for taking care of mouse clicks and drawing a cell.

The implementation is that `SudokuMap` has an array of `SudokuCell`, and when `OnMouseDown` or `OnPaint` functions are triggered it delegates the call to the correct `SudokuCell`.

Section 3.3: Double click implementation

The user interaction on a cell was to be as follows:

1. Single click on a specified location in the square will mark a point in the location. The points will represent the selected possibilities for that square.
2. Double click on a specified location in the square will select the number related to the location. After selecting a number, the points disappear and the selected number is shown.

Imagine my surprise when I found that double click does not exist in .NET Compact Framework! It took me a few days to relax and I finally decided to implement it myself. I'll implement double click on a Smart Device.

The basic idea behind the implementation of double click is that we need to remember when and where the previous click was clicked. So if a click arrives and it is in the same location as the previous click (up to a certain threshold) and the time elapsed between the consecutive clicks is small (say less then 250 milliseconds) then we have a double click.

One minor inaccuracy is that in this case we can't determine from the first click whether it belongs to a "double click" pair. So, we always perform the action of a click and sometimes we also perform the action of a double click.

If you wish to implement a double click and want to avoid the extra click action, you should invoke a timer (250 ms) on every click pressed and do the single click action only if the timer elapses (if a second click arrives, don't forget to stop the timer).

Here is a sample code that demonstrates the double click technique:

```// return clicked number
int clickedNumber = GetCheckedNumber(e.X - CellLocation.X,
e.Y - CellLocation.Y);
int now = System.Environment.TickCount;

// check for double click activity
if ((mPreviousClickedNumber == clickedNumber) &&
(now - mPreviousClickTime < DoubleClickTime))
{
// double click
// ...
}
else
{
// single click
// ...

// update previous clicked number and time
mPreviousClickedNumber = clickedNumber;
mPreviousClickTime = now;
}```

Section 3.4: Double buffering and painting techniques

Another performance penalty was induced by the `Paint` method. There were three problems associated with the `Paint` method.

1. The `Paint` method did a lot of painting directly on the screen `Graphics` object.
2. Each time the map was changed (e.g. a point was marked) the whole map was redrawn.
3. Expensive GDI objects where created repeatedly on every paint.

The first improvement was to use the double buffer technique. Instead of performing all the user defined painting directly on the screen `Graphics` object, you can do it on your own `Graphics` object that will serve as a buffer. This `Graphics` object represents an in-memory bitmap. After you finish doing all the painting to the memory bitmap, you can simply copy the bitmap to the screen `Graphics` object to do the actual drawing. This results in quicker paint and reduced flickering.

The normal .NET Framework has built-in support for double buffering while doing user defined painting, so all it takes is to `SetStyle` to your control. Unfortunately, this support does not exist in the .NET Compact Framework.

Another improvement is to paint only those parts that are changed. Here we use the same memory bitmap described in the previous paragraph, and when we finish painting it to the screen, we don't destroy it, instead we save it to the next paint. So if nothing has changed we don't need to recalculate the bitmap and we can simply copy it directly to the screen. Furthermore, if a single cell has changed, we only need to recalculate the painting of this single cell.

Following is a sample code that demonstrates these techniques:

We need three member variables in our control; first is the memory bitmap, second is the `Graphics` object on the memory bitmap, and third is a Boolean flag that indicates whether recalculation of the bitmap is required.

```/// <SUMMARY>
/// saves buffer in-memory bitmap
/// </SUMMARY>
private Bitmap mBufferBitmap;

/// <SUMMARY>
/// saves buffer in-memory graphics
/// </SUMMARY>
private Graphics mBufferGraphics;

/// <SUMMARY>
/// saves a flag that indicates whether a
/// recalculation of the bitmap is needed
/// </SUMMARY>
private bool mRecalculateNeeded = true;```

And here is the implementation of the `OnPaint` method, you can see that we perform the heavy drawing only if the recalculate flag is on, most of the time we just copy the memory bitmap. In this example, you will see that the `SudokuMap` `OnPaint` draws the Sudoku grid and then delegates the paint to each `SudokuCell`.

```/// <SUMMARY>
/// OnPaint - overrides paint to draw sudoku map
/// </SUMMARY>
/// <PARAM name="e">arguments</PARAM>
protected override void OnPaint(PaintEventArgs e)
{
if (mRecalculateNeeded)
{
// fill background in white
mBufferGraphics.FillRectangle(
CommonGraphicObjects.WhiteBrush, e.ClipRectangle);

int i,j;

// draw grid
for (i=0 ; i<=MapInfo.MapCellsNumber ; ++i)
{
// draw vertical line
if (i % MapInfo.ColsInSmallRect == 0)
mBufferGraphics.DrawLine(CommonGraphicObjects.BlackPen,
mOffset.X + i*mCellSize.Width, mOffset.Y,
mOffset.X + i*mCellSize.Width,
mOffset.Y + MapInfo.MapCellsNumber*mCellSize.Height);
else
mBufferGraphics.DrawLine(CommonGraphicObjects.GrayPen,
mOffset.X + i*mCellSize.Width, mOffset.Y,
mOffset.X + i*mCellSize.Width,
mOffset.Y + MapInfo.MapCellsNumber*mCellSize.Height);

// draw horizontal line
if (i % MapInfo.RowsInSmallRect == 0)
mBufferGraphics.DrawLine(CommonGraphicObjects.BlackPen,
mOffset.X, mOffset.Y + i*mCellSize.Height,
mOffset.X + MapInfo.MapCellsNumber*mCellSize.Width,
mOffset.Y + i*mCellSize.Height);
else
mBufferGraphics.DrawLine(CommonGraphicObjects.GrayPen,
mOffset.X, mOffset.Y + i*mCellSize.Height,
mOffset.X + MapInfo.MapCellsNumber*mCellSize.Width,
mOffset.Y + i*mCellSize.Height);
}

// draw cells internal
for (i=0 ; i < MapInfo.MapCellsNumber ; ++i)
{
for (j=0 ; j < MapInfo.MapCellsNumber ; ++j)
{
mSudokuCells[i,j].Paint(mBufferGraphics);
}
}
}

e.Graphics.DrawImage(mBufferBitmap, 0, 0);

mRecalculateNeeded = false;

}```

And finally, if a cell was changed (e.g. because of a mouse click), it updates the memory bitmap and causes a refresh of the control to invoke the `Paint` method.

```/// <SUMMARY>
/// causes image to recalculate and redraw
/// </SUMMARY>
internal void UpdateImage(SudokuCell updatedCell)
{
updatedCell.Paint(mBufferGraphics);
Invalidate();
}```

One final note about painting is the usage of GDI objects. These objects are expensive resources and should not be recreated on every draw, it is best to create them once and then use them wherever needed using `static` variables. Don't forget to dispose them when you finish using them (e.g. when closing the application).

Section 4: Map information classes

Section 4.1: General

Map information classes are a set of classes that give information on different map types. These classes contain information like how many rows and columns are there in a small Sudoku rectangle and the kind of symbols we should use while drawing (think of the 16x16 grid). All these classes have the same interface and so other parts of the application do not have to know their internals.

Section 4.2: Factory design pattern

The map information classes are constructed using the factory design pattern.

In this design pattern, we have a class that knows how to construct map information classes. The class has some sort of `Create` function that gets parameters, and according to these parameters and some internal logic, creates the relevant map information class. The class is then returned as a base class, so that no one knows the exact type of the class. This is good, so if we want to add new types of maps, we just need to change the factory and it will construct them, the rest of the application does not even know the specifics or even where these classes came from (we can construct classes from remote objects etc.).

Here is a class diagram for the map information classes:

This design could be made even more interesting by using reflection to create the classes so that additional maps could be added as DLLs without recompiling the application. However, in our application this would be an overkill.

Section 4.3: Using Interfaces

You must have seen in the factory section that I didn't use any interface to unite the different map information classes. Using a common interface would have been a more correct design, but in this particular case the price was too big.

Even using interfaces has its own penalty when coding for a Smart Device. If we look at the interface needed, we will see that it has three member variables that return different values for different map information classes, of course, the interface does not have member variables so they must be implemented as properties of the interface.

The problem is that getting and setting a value using a property yields a function call in addition to the simple integer assignment. And if we use these properties a lot then the overhead of the function calls becomes obvious. To make things short, I've gained 30% in performance after removing the use of interfaces and switching back to a plane old base class. What works for native C++ works for me.

Section 5: Application settings

Section 5.1: General

Everybody needs application settings. In my Smart Client, the application settings include remembering the last selected map type and map difficulty level and, of course, the local high scores.

I chose to serialize my application settings into an XML file, since the .NET has such convenient classes to read and write from. Lucky me, this part was supported by the .NET Compact Framework! Silent minute for double click.

Section 5.2: Delay IO

Delaying IO is a very sophisticated headline but actually it doesn't mean anything special. The basic idea is: don't write to file on every memory change.

My implementation: write to the file when the application exits. Sounds like a trivial concept but I initially wanted to write to file every time a setting was changed, so the application would be more tolerant in the case of a crash. Then I remembered that Pocket PC doesn't like people who abuse it, so I let it go.

Section 5.3: Singleton design pattern

Singleton is another design pattern, one that everybody should know about.

Basically everyone has a settings class in their application. And this settings class is always available from any part of the application. But you usually don’t want to create multiple instances of your settings class. So here comes the singleton design pattern that enforces the creation of maximum one instance.

The implementation details are trivial. In your settings class: write a static `GetInstance` function that creates an instance of your class the first time it is called. The function saves this instance to a static variable. The next time the function is called, it will return the previously created instance. One extra feature is to make the constructor of your settings class as `private`, to ensure that no one creates your class outside your `GetInstance` function.

Sample code for singleton pattern:

```private static Settings mInstance;

/// <SUMMARY>
/// Get single instance of settings class
/// </SUMMARY>
public static Settings Instance
{
get
{
if (mInstance == null)
{
mInstance = new Settings();
}

return mInstance;
}
}

/// <SUMMARY>
/// Private ctor to enforce singelton
/// </SUMMARY>
private Settings()
{
}```

Section 6: Web service and high scores

Section 6.1: General

Web services are fun. The idea of putting a code that everybody with an internet access can call brings life to many applications. I mean, playing Sudoku and have the best result in your high scores is fun, but having the best result in the internet? Imagine that!

I created a web service with two features: get Sudoku puzzle data and host internet-wide high score results.

By the way, the hardest part regarding web services was to find a free host that supports ASP.NET.

Section 6.2: Cross platform bug

If you recall, one of my goals was to create an application that will run the same way on both PC and Pocket PC. It turns out there is a bug when consuming a web service from the .NET Compact Framework. When you add a reference to a web service, Visual Studio creates a proxy for you. This proxy is used to hide the details of the web service connection. The code generated by Visual Studio in the case of a .NET Compact Framework application fails to run when used with a normal .NET Framework. The problem is that two attributes are not supported; they are the `Use` attribute and the `ParameterStyle` attribute.

Here is a sample of the original generated code:

```[System.Web.Services.Protocols.SoapDocumentMethodAttribute(
"http://tempuri.org/GenerateMapData",
RequestNamespace="http://tempuri.org/",
ResponseNamespace="http://tempuri.org/",
Use=System.Web.Services.Description.SoapBindingUse.Literal,
ParameterStyle=
System.Web.Services.Protocols.SoapParameterStyle.Wrapped)]
[return: System.Xml.Serialization.XmlArrayItemAttribute(
IsNullable=false)]
public CellData[] GenerateMapData(int cellsNumber,
MapDifficultyLevel level) {
object[] results =
this.Invoke("GenerateMapData", new object[] {
cellsNumber,
level});
return ((CellData[])(results[0]));
}```

The solution is to just remove them on recompile:

```[System.Web.Services.Protocols.SoapDocumentMethodAttribute(
"http://tempuri.org/GenerateMapData",
RequestNamespace="http://tempuri.org/",
ResponseNamespace="http://tempuri.org/")]
[return: System.Xml.Serialization.XmlArrayItemAttribute(
IsNullable=false)]
public CellData[] GenerateMapData(int cellsNumber,
MapDifficultyLevel level) {
object[] results =
this.Invoke("GenerateMapData", new object[] {
cellsNumber,
level});
return ((CellData[])(results[0]));
}```

Note that if you update your web reference you should do this again, since the code is regenerated.

Section 6.3: High scores implementation

The web service supplies functions to get the list of internet high scores, to get the time of a specific high score, and update the high scores with a new time. Using these functions, I create labels that display the information in the internet high scores page.

Note: This particular web service is not secure. It was created for learning purpose. It is probably less secure than the Internet Explorer. If you abuse this web service you have too much time on your hand, why else would you want to change a text file on a remote server in Russia?

A sample of internet high scores when you run the application on a normal PC:

Section 6.4: Web Service Sample

I've included in the source code the code for the basic web service. I say basic because the generation function in the basic sample returns a hard-coded game for each map type (Mini, Classic, Monster).

In the web service run on the server, I get the puzzle data from a local database in the case of a classic map (9x9, Easy, Medium, Hard) and the same hard-coded map in the monster and mini map types.

Nevertheless, this sample shows the interface and the basic coding used for the web service involved.

Section 7: Final

As always, in embedded systems, you must code for performance and don't make anything extra without a good reason. The only difference from now and 30 years ago is that back then you coded for performance using assembly, now we code for performance using .NET. This is the only difference. That and web services. :)

That’s it. Hope you like it. Don’t forget to vote.

Section 8: Updates

• 05.08.2005 - Added support for saving and loading Sudoku maps so offline playing is also available.
• 12.08.2005 - Added support for saving and loading a game (with time and marked values) + added colors and some minor bug fixes.

License

This article, along with any associated source code and files, is licensed under The Microsoft Public License (Ms-PL)

About the Author

 Software Developer (Senior) Verint Israel
Arik Poznanski is a senior software developer at Verint. He completed two B.Sc. degrees in Mathematics & Computer Science, summa cum laude, from the Technion in Israel.

Arik has extensive knowledge and experience in many Microsoft technologies, including .NET with C#, WPF, Silverlight, WinForms, Interop, COM/ATL programming, C++ Win32 programming and reverse engineering (assembly, IL).

Comments and Discussions

 First PrevNext
 very good xds102221-Aug-12 3:44 xds1022 21-Aug-12 3:44
 Nice app! Sandeep Mewara22-Mar-10 5:33 Sandeep Mewara 22-Mar-10 5:33
 How handle Windows Explorer by vb.net Navaratan11-Jun-09 2:09 Navaratan 11-Jun-09 2:09
 hi bashar_kabbani587-Apr-08 4:07 bashar_kabbani58 7-Apr-08 4:07
 excellent.. apache1o11-Jun-07 23:11 apache1o 11-Jun-07 23:11
 find a free host that supports ASP.NET plumot Werner10-Jul-06 3:37 plumot Werner 10-Jul-06 3:37
 Liscense codegalaxy21-Dec-05 5:14 codegalaxy 21-Dec-05 5:14
 ^5 - Excellent Article and Code jadedgeek9-Dec-05 4:25 jadedgeek 9-Dec-05 4:25
 Got my 5. Thanks for putting this together. I guess you'll be selling this or providing the game as a paid service, that's why your not releasing the inner working on how the map was generated and the actual webservice :-> - good luck with that. Cheers
 New Feature Bassam Abdul-Baki1-Dec-05 3:52 Bassam Abdul-Baki 1-Dec-05 3:52
 Great Game Bassam Abdul-Baki17-Nov-05 7:03 Bassam Abdul-Baki 17-Nov-05 7:03
 Generation of the Map. Benoit Morneau12-Oct-05 9:01 Benoit Morneau 12-Oct-05 9:01
 Entering a name Saltire15-Aug-05 13:01 Saltire 15-Aug-05 13:01
 Re: Entering a name Arik Poznanski15-Aug-05 20:29 Arik Poznanski 15-Aug-05 20:29
 Awesome! Save/Load Question davfive10-Aug-05 13:57 davfive 10-Aug-05 13:57
 Re: Awesome! Save/Load Question Arik Poznanski10-Aug-05 20:00 Arik Poznanski 10-Aug-05 20:00
 Re: Awesome! Save/Load Question Arik Poznanski12-Aug-05 3:00 Arik Poznanski 12-Aug-05 3:00
 Re: Awesome! Save/Load Question davfive12-Aug-05 7:38 davfive 12-Aug-05 7:38
 Download exe here Arik Poznanski10-Aug-05 1:46 Arik Poznanski 10-Aug-05 1:46
 Re: Download exe here soniq7711-Aug-05 20:31 soniq77 11-Aug-05 20:31
 Re: Download exe here Arik Poznanski11-Aug-05 22:40 Arik Poznanski 11-Aug-05 22:40
 Re: Download exe here soniq7712-Aug-05 19:51 soniq77 12-Aug-05 19:51
 Thanks a lot soniq779-Aug-05 23:09 soniq77 9-Aug-05 23:09
 Re: Thanks a lot Arik Poznanski10-Aug-05 1:43 Arik Poznanski 10-Aug-05 1:43
 Updated: map generation Arik Poznanski9-Aug-05 10:09 Arik Poznanski 9-Aug-05 10:09
 Re: Updated: map generation Saltire7-Oct-05 4:21 Saltire 7-Oct-05 4:21
 Last Visit: 27-Jun-19 3:11     Last Update: 27-Jun-19 3:11 Refresh 12 Next »

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Article
Posted 30 Jul 2005

198.3K views
2.1K downloads
123 bookmarked