Sudoku and Smart Client techniques

• Download Smart Client source files - 35.5 Kb
• Download Smart Client demo project - 45.3 Kb
• Download web service demo project - 22.8 Kb

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.