Microsoft Sudoku: Optimizing UMPC Applications for Touch and Ink

 

Stephen Toub
Microsoft Corporation

March 2006

Applies to
    Windows XP Tablet PC Edition
    Microsoft .NET Framework

Summary: Stephen Toub discusses Sudoku, the number puzzle game, and demonstrates how to build an application to solve puzzles, generate puzzles, and enable enhanced game play for ultra-mobile PC and Tablet PC. (60 pages)

Click here to download the sample code for this article.

Contents

Introduction
What Is Sudoku?
Application Infrastructure
   Platform Detection
   Designing Applications for Ultra-Mobile PC
   Code Access Security
   Handling Fatal Exceptions
   Single-Instance Applications
Sudoku Algorithms
   Maintaining Puzzle State
   Analyzing and Solving Puzzles
   Generating Puzzles
Windows Forms and Hardware Interactions
   Laying out Sudoku
   Drawing Sudoku
   Enabling Tablet PC Interaction
   Recognizing Numbers Made from Multiple Strokes
   Undo Support
   Scratchpad Support
   Eraser Support
   A Winning Animation
   Saving State and Settings
   Power Awareness
Extending Sudoku
   Extending Undo Support
   Printing Puzzles
   Supporting Multiprocessors
   Copying the Puzzle to the Clipboard
   And So On...
Acknowledgements
Biography

Introduction

A year ago in a small café in the West Village in New York City, I was introduced to a pen-and-pencil puzzle game with which my friend Luke was entirely captivated. Lively conversation with our significant others saved me from falling into the same trap, but it was only a short reprieve. A few months later in July of 2005, I again found myself confronted by Sudoku while visiting my brother and my former college roommate in London. This time, it was everywhere. And there was no escape. I was enthralled, addicted, and borderline obsessed. As is the case for many developers, today's passions frequently become tomorrow's development projects, and so it took little more than the flight back to the United States for me to have the first version of my C# Sudoku implementation up and running.

But I wasn't satisfied. Something was missing. There was something thrilling about setting the logically discovered numbers crisply onto the paper with my pen or pencil, a property that was lost in the game's translation into Windows Forms. And that's when it hit me. Sudoku is the quintessential application for a Tablet PC. After downloading the Tablet PC SDK to my computer the next day, I soon transformed this keyboard-and-mouse powered game into one that is completely pen-driven.

Figure 1. Microsoft Sudoku

This article closely examines my Tablet PC-based implementation of Sudoku. It is the same implementation I wrote for the Touch Pack, a software package that comes preinstalled on ultra-mobile PCs (UMPCs). The article details the algorithmic aspects of implementing a Sudoku game, in addition to the specific details that help you implement other applications designed for Tablet PC.

Back to Top

What Is Sudoku?

Sudoku is a number puzzle game that's popular right now in Japan and Europe. The game is quickly gaining a similar popularity in the United States, filling shelves in neighborhood bookstores and showing up daily in newspapers across the country. The prototypical puzzle is a 9x9 grid, divided into nine 3x3 boxes, each of which is comprised of 9 cells. Figure 2 shows the total grid of 81 cells.

Figure 2. An empty Sudoku grid

The goal of the puzzle is to fill every cell with a number, 1 through 9, such that each row, column, and box contains only one instance of each number from 1 through 9 (a harder puzzle, sometimes referred to as Super Sudoku, can be constructed using a 16x16 grid and the digits 1-9, plus the letters A-G).

Figure 3 shows a valid Sudoku solution.

Figure 3. A valid Sudoku solution

It's been computed that there are more than 1021 valid 9x9 Sudoku solutions (for more information about these calculations, see http.//www.afjarvis.staff.shef.ac.uk/sudoku/). What makes Sudoku engaging is that the initial state of each puzzle consists of some cells in the grid already populated with numbers. Given this initial state, there is one, and only one, solution to the puzzle, and it can be deduced using logic to fill in all of the missing numbers.

Consider the puzzle in Figure 4 (I've highlighted a few cells in yellow and red for the sake of explanation). As mentioned, every box must include the numbers 1 through 9. Currently, the upper-left box doesn't have a 2 in it, but I can figure out where the 2 in that box should go through simple deduction. I know it can't be in the top row because there's already a 2 in that row (the 2 in the upper-right corner, highlighted in yellow). I know it can't be in the middle row, because there's already a 2 there, as well (the 2 in the second row, fourth column). It obviously can't be in the third row, second column, as there's already a 7 there (highlighted in yellow), and it can't be in the cell to the 7's right, because there's already a 2 in that column (highlighted in yellow in the eighth row). Therefore, the 2 must be in the third row, first column—the cell highlighted in red. I can fill in that 2, moving me one step closer to solving the puzzle.

Figure 4. A starting Sudoku puzzle

Now that you're familiar with the game, the rest of this article is about implementing Sudoku for the Tablet PC. To begin, I'm going to focus on some typical requirements of Tablet PC applications, showing how I address the requirements in Sudoku and how you might in your own applications. From there, I'll dive into specifics of implementing a Sudoku game, focusing on algorithms that you can use to accomplish many Sudoku-related tasks, such as puzzle generation and solving. I'll follow that up with Tablet PC-specific details, focusing on working with Tablet PC APIs to support pen-based interaction. And finally, I'll wrap up with some ideas and samples for fun, additional projects that you can undertake to extend the game to your liking.

Back to Top

Application Infrastructure

The concepts in this section apply to Tablet PC applications in general and not specifically to the Sudoku game.

Platform Detection

Most programs written to take advantage of Tablet PC functionality work best only on a Tablet PC or on a development computer configured appropriately. Such a development computer would have installed both the Microsoft Windows XP Tablet PC Edition Software Development Kit 1.7 and the Microsoft Windows XP Tablet PC Edition 2005 Recognizer Pack (both of which can be found through the Mobile PC Developer Center). This is frequently and partially due to the reliance on the Microsoft.Ink.dll assembly, which is distributed along with Windows XP Tablet PC Edition 2005. Thus, it's important for any Tablet PC application to check whether the necessary libraries and functionality are available before attempting to execute code that relies on their existence. This is true even if the application is factored in such a way that the libraries are loaded and used only if they're found, because platform detection must be used to perform that existence check.

Note   You need not check for the Tablet PC binaries as long as you redistribute tpcman17.msm and mstpcrt.msm. Alternatively, you could ensure that you deploy your application only on computers running Windows XP Tablet PC Edition 2005. If, however, you cannot redistribute the Tablet PC binaries and your application may be deployed on a computer that does not have the Tablet PC binaries, you should perform these checks to insure the application will not fail. This is relevant if, for example, your application contains an inking control and is deployed to a Web site.

In the accompanying sample code, all of the platform detection code is in the PlatformDetection class in the PlatformDetection.cs file, located in the Utilities folder. This class has code to perform several different checks and to expose the results of those queries to the rest of the application.

First, and soon after startup, your application should check whether the Microsoft.Ink.dll assembly is available. This check would be performed implicitly when code referencing classes from the Microsoft.Ink.dll assembly is first compiled, but you don't want to let things get to that point, as it can be difficult to properly recover from the exceptions thrown by the JIT compiler when you're not expecting them. Instead, one option is to explicitly search, by using the Assembly.Load and Assembly.LoadWithPartialName methods, to see if you can find a valid Microsoft.Ink.dll assembly.

public static bool InkAssemblyAvailable 
{
  get { return _inkAssemblyAvailable; } 
}

private static bool _inkAssemblyAvailable = 
  (LoadInkAssembly() != null);

private static Assembly LoadInkAssembly()
{
  try 
  {
    Assembly a = Assembly.Load(
      "Microsoft.Ink, Version=1.7.2600.2180, " + 
      "Culture=neutral, PublicKeyToken=31bf3856ad364e35");
    if (a == null)
    {
      a = Assembly.LoadWithPartialName(
        "Microsoft.Ink, PublicKeyToken=31bf3856ad364e35");
      if (a != null && a.GetName().Version < 
        new Version("1.7.2600.2180")) a = null;
    }
    return a;
  }
  catch(IOException){}
  catch(SecurityException){}
  catch(BadImageFormatException){}
  return null;
}

The public static InkAssemblyAvailable property returns the value stored in a private static Boolean value that's initialized with the return value of a call to LoadInkAssembly. LoadInkAssembly uses the reflection APIs to load the Microsoft.Ink assembly by using its full name, including version number, culture, and public key token. If the loader is unable to find the assembly with this information, then LoadInkAssembly tries to load the Microsoft.Ink assembly by using a partial name, meaning that it omits some of the information from the assembly's full name while performing the search. In this case, I've omitted the version number. The idea here is that the Sudoku implementation might be used with a newer version of Microsoft.Ink.dll (for example, if the game runs the version of the Tablet PC APIs in Windows Vista), and by leaving out the version number, I allow the loader to find any version of the assembly. Of course, assuming that any version found will be good enough is a dangerous assumption; the game may run on an older version that lacks the functionality that I depend on, at which point I'm back to failing when the JIT compiler attempts to compile my use of the missing pieces. To counteract that, I make a slightly safer (though not 100% safe) assumption that any version that's newer is acceptable. Therefore, after loading the assembly by partial name, I check its version number to ensure that it's either the version that I compiled against or a later version.

Another, arguably better, option (and the one that I actually use) is to let the CLR attempt to find and load an appropriate Microsoft.Ink.dll assembly by using its standard logic, and then handle the case where the assembly isn't available and able to load. I mentioned earlier that it's frequently difficult to recover from assembly and type loading exceptions when you're not expecting them. But when you're aware that they can occur and you take advantage of them in a controlled environment, relying on the capabilities of CLR is frequently the best approach. I can change my implementation by rewriting the LoadInkAssembly method in the following way.

private static Assembly LoadInkAssembly()
{
  try { return LoadInkAssemblyInternal(); }
  catch(TypeLoadException) {}
  catch(IOException){}
  catch(SecurityException){}
  catch(BadImageFormatException){}
  return null;
}
[MethodImpl(MethodImplOptions.NoInlining)]
private static Assembly LoadInkAssemblyInternal()
{
  return typeof(InkOverlay).Assembly;
}

Back in the Main method of the program (in the Program.cs file), I use the InkAssemblyAvailable property to determine whether I should allow execution to continue. Main then displays a message box and exits if the execution isn't allowed to continue.

bool validSystem = PlatformDetection.InkAssemblyAvailable && 
          PlatformDetection.RecognizerInstalled;
if (!validSystem)
{
  MessageBox.Show(ResourceHelper.NotRunningOnTablet,
    ResourceHelper.DisplayTitle, MessageBoxButtons.OK, 
    MessageBoxIcon.Error, MessageBoxDefaultButton.Button1);
  return 1;
}

Note that I require that more than just the ink assembly is available. I also require that a recognizer is installed. On a typical Tablet PC installation, the presence of the former implies the presence of the latter. However, it is possible that the recognizers were removed. It's also possible that the Tablet PC APIs were installed without recognizers, potentially the case in a development environment. Consequently, I use the following code to check both conditions.

public static bool RecognizerInstalled
{
  get
  {
    if (!InkAssemblyAvailable) return false;
    return GetDefaultRecognizer() != null;
  }
}

The RecognizerInstalled property first checks to see whether the ink assembly is available. This is very important because my implementation of GetDefaultRecognizer, which the RecognizerInstalled property uses to see whether a recognizer is available, relies on types from Microsoft.Ink.dll.

[MethodImpl(MethodImplOptions.NoInlining)]
public static Recognizer GetDefaultRecognizer() 
{
  Recognizer recognizer = null;
  try 
  { 
    Recognizers recognizers = new Recognizers();
    if (recognizers.Count > 1)
    {
      try { recognizer = recognizers.GetDefaultRecognizer(); } 
      catch {}

      if (recognizer == null)
      {
        try 
        { 
          recognizer = 
            recognizers.GetDefaultRecognizer(1033); 
        }
        catch {}
      }
    }
  }
  catch {} 
  return recognizer;
}

GetDefaultRecognizer instantiates a Microsoft.Ink.Recognizers collection and makes sure that there is at least one recognizer available in it. It then uses the collection to retrieve the default recognizer. If for some reason it is unable to do so, it attempts to retrieve the default recognizer for LCID 1033, which is the US English locale. (Because the only recognition being performed by Sudoku is for integers, this is good enough.)

Note that I used a System.Runtime.CompilerServices.MethodImplAttribute on GetDefaultRecognizer to mark it is as being exempt from inlining. Inlining is a process where a compiler can choose to copy the contents of a target function to a call site, rather than making the actual method call. For small methods, where the cost of executing the method is dominated by the overhead of making a method call, inlining can result in significant performance improvements. In reality, due to the amount of code in the GetDefaultRecognizer method, there is little chance that the JIT compiler would exercise the option.

However, I don't want GetDefaultRecognizer inlined. Remember that when the JIT compiles a method, the JIT compiler attempts to load any assemblies that contain types used in that method. So, for example, when the JIT compiles GetDefaultRecognizer, the JIT compiler will attempt to load Microsoft.Ink.dll. If GetDefaultRecognizer is inlined into RecognizerInstalled, that load attempt will occur when the JIT compiles RecognizerInstalled, which is before RecognizerInstalled has a chance to check for the existence of the ink assembly. Therefore, I use the MethodImplAttribute on GetDefaultRecognizer to ensure that it is never inlined. This enables RecognizerInstalled to first perform the assembly existence check.

This Sudoku implementation supports the use of a scratch-out gesture to erase numbers previously entered by the player. Unfortunately, what you won't see in most sample code is that attempting to support gestures can cause exceptions to be thrown if a valid gesture recognizer isn't installed. Consequently, I also use PlatformDetection to check for the existence of a gesture recognizer.

public static bool GestureRecognizerInstalled
{
  get
  {
    return InkAssemblyAvailable && 
      GestureRecognizerInstalledInternal;
  }
}
private static bool GestureRecognizerInstalledInternal 
{
  [MethodImpl(MethodImplOptions.NoInlining)]
  get
  {
    try
    {
      Recognizers recognizers = new Recognizers();
      if (recognizers.Count > 0)
      {
        using(new GestureRecognizer()) return true;
      }
    }
    catch { } 
        return false;
  }
}

As with RecognizerInstalled, the GestureRecognizerInstalled public static property doesn't explicitly perform the check. It, too, relies on a helper member marked as NoInlining, due to its dependencies on the Microsoft.Ink assembly. The GestureRecognizerInstalledInternal property checks to see whether any recognizers exist. It then explicitly instantiates a Microsoft.StylusInput.GestureRecognizer, returning whether it was able to create one successfully. If one can't be successfully instantiated, an InvalidOperationException is thrown (and, hence, the try-catch surrounding the instantiation), stating that "The requested recognizer is not available with the current setup or configuration."

The last piece of functionality exposed by PlatformDetection is used to determine the handedness of the user. The Tablet PC operating system enables the user to configure the system according to whether he or she is left-handed or right-handed. Applications can query this setting and modify their user interface in any fashion deemed necessary to best accommodate the user's handedness.

public static bool UserIsRightHanded
{
  get
  {
    if (IsRunningOnTablet)
    {
      bool rightHanded = true;
      if (NativeMethods.SystemParametersInfo(
        NativeMethods.SPI_GETMENUDROPALIGNMENT, 0, 
          ref rightHanded, 0))
      {
        return rightHanded;
      }
    }
    return true;
  }
}
private static bool IsRunningOnTablet
{ 
  get 
  {
    return NativeMethods.GetSystemMetrics(
      NativeMethods.SM_TABLETPC) != 0; 
  }
}

The property first checks to see whether the current system is a Tablet PC. This doesn't use InkAssemblyAvailable, because the ink assembly's existence doesn't imply that the system is a Tablet PC and thus that this setting is available for query. Instead, it relies on the GetSystemMetrics function that is exposed from user32.dll.

[DllImport("user32.dll", CharSet=CharSet.Auto)]
internal static extern int GetSystemMetrics(int nIndex);

When supplied with the SM_TABLETPC value (86), this function returns a non-zero value if the current operating system is Microsoft Windows XP Tablet PC Edition; otherwise, it returns a zero. When I know the application is running on a Tablet PC, I can query for the handedness setting by using the SystemParametersInfo function that is exposed from user32.dll. The user's preference is exposed through the SPI_GETMENUDROPALIGNMENT setting, which determines whether pop-up menus are left-aligned or right-aligned, relative to the corresponding menu-bar item.

Back to Top

Designing Applications for Ultra-Mobile PC

For those of us familiar with Tablet PC development, the ultra-mobile PC (UMPC)—recently announced by Microsoft and a number of OEMs—presents device-like computers that are a great opportunity. All of the experience we've garnered developing for the Tablet PC comes to bear, as the UMPC runs Windows XP Tablet PC Edition. This means that every UMPC comes with the APIs necessary to develop full-fledged pen-based applications. In fact, the applications you've already written for the Tablet PC should run without a hitch. However, there are some differences to keep in mind when writing new software for UMPC devices or when tweaking your current software to provide a better UMPC experience.

First, a UMPC has a smaller screen, typically 800x480. This means you need to be aware of what sort of screen real estate your application requires. Additionally, if your application targets standard Tablet PCs in addition to UMPCs, you'll need to craft your application in a way that allows for optimal experiences on multiple screen sizes. I discuss how I handle that for Sudoku in Windows Forms and Hardware Interaction.

Whereas most Tablet PCs today have electromagnetic screens that allow for sophisticated detection and interaction with specialized pens, UMPCs have touch-sensitive screens. This makes them more accessible, enabling users to easily manipulate a UMPC with a finger or other pointing device readily at hand. However, it also means that due to the lack of palm rejection on most touch screens the user experience can differ when compared to that of a Tablet PC with an electromagnetic digitizer. When designing your application's user interface, make sure to factor this into your design. My implementation of Sudoku allows for multiple methods of interaction. Numbers can easily be set into a puzzle with a keyboard or with a pen, but I've also provided relatively large number buttons. These make it easy to use a finger to tap a number and then a cell in the Sudoku grid in order to set that number into that cell.

Another related factor to keep in mind is that the pens for UMPCs are simple pointing devices rather than electromagnetic devices. This means that applications do not receive as much information about pen interactions as they do on a Tablet PC with an electromagnetic digitizer. Make sure that your applications destined for UMPC devices do not rely on the extra information, such as in-air packets or digitizer pressure, in order to function correctly.

Most importantly, however, is the fact that the development knowledge you have from working on Tablet PCs is 100% applicable. If you keep the extra considerations in mind while designing and developing for UMPCs, you'll enable a more a positive experience for your users. As you'll see, I developed Sudoku to work correctly on both standard Tablet PCs and on UMPC devices.

Code Access Security

At first glance, one might think that implementing a game like Sudoku means you don't have to think about security, but that couldn't be further from the truth. As a developer, you always need to be thinking about security and what sorts of security-related requirements you impose on your users.

For example, Sudoku makes use of several Win32 APIs. Accessing these APIs requires unmanaged code permissions. That's not a problem if Sudoku is running from a local drive and the default Code Access Security (CAS) settings have been left intact, but what if someone attempts to run Sudoku from a network share? Unmanaged code permissions are, by default, not granted to intranet applications. Consequently, the system would throw security exceptions left and right as Sudoku attempted to access these unmanaged APIs.

Rather than attempt to have Sudoku run in a partial trust environment, I decided that Sudoku, like most managed applications, would require full trust. However, the user experience would be pretty horrible if users tried to run Sudoku from a partial trust environment, and the application then had a catastrophic failure before their very eyes. Instead, at startup, Sudoku explicitly checks for full trust and warns the user if the current environment is incompatible. Here's the start of Sudoku's Main method.

[STAThread]
public static int Main()
{
  Application.EnableVisualStyles();
  Application.DoEvents();
  if (!HasFullTrust)
  {
    MessageBox.Show(ResourceHelper.LacksMinimumPermissionsToRun, 
      ResourceHelper.DisplayTitle, MessageBoxButtons.OK, 
      MessageBoxIcon.Error, MessageBoxDefaultButton.Button1);
    return 1;
}

Sudoku checks whether the application has been granted full trust. If it hasn't, Sudoku displays a friendly error dialog to the user and exits. The HasFullTrust property is implemented as follows.

private static bool HasFullTrust
{
  get
  {
    try
    {
      new PermissionSet(PermissionState.Unrestricted).Demand();
      return true;
    }
    catch (SecurityException) { return false; }
  }
}

The property instantiates a System.Security.PermissionSet for unrestricted, full trust access, and it demands this permission. The Demand method throws a SecurityException if the requested permission is not available. As a result, this code is wrapped in a try block. If the Demand method succeeds, HasFullTrust returns true. If it fails with an exception, HasFullTrust returns false.

One interesting thing to note is that if the check for full trust fails, the application attempts to display a message box. There is actually a permission that controls whether message boxes can be displayed. If the UIPermission for SafeSubWindows has not been set, an application will receive a security exception when attempting to display a message box. There are a few ways to deal with this. One would be to catch the resulting exception and exit the program, but users would have no idea what went wrong. They would double-click the application in Microsoft Windows Explorer, and nothing would happen (or, more specifically, they wouldn't see anything happen. Windows would launch the application in the background and then exit before displaying any visual clues). Instead, I chose to mark the assembly as requiring this SafeSubWindows permission as a bare minimum.

[assembly: UIPermission(SecurityAction.RequestMinimum, 
  Window=UIPermissionWindow.SafeSubWindows)]

This way, if the assembly isn't granted at least this permission, the CLR displays its own dialog box that informs the user that the application could not be loaded due to a lack of necessary permissions. If at least this permission is granted, the application loads, and my logic to check for full trust in the Main method takes over.

Back to Top

Handling Fatal Exceptions

After the Main method checks for full trust and verifies that the Microsoft.Ink assembly is available and that recognizers are installed, it calls to another method, MainInternal, that does all the core work of setting up the main form and launching it. MainInternal activates the main message loop for the application; therefore, any unhandled exceptions that come from user interface interactions in the game are propagated out of MainInternal. To make sure that these exceptions are properly logged (for diagnosis and debugging purposes), the Main method catches all of these exceptions, logs them, and then exits.

try
{
  return MainInternal() ? 0 : 1;
}
catch(Exception exc)
{
  ShutdownOnException(new UnhandledExceptionEventArgs(exc, false));
  return 1;
}
catch
{
  ShutdownOnException(new UnhandledExceptionEventArgs(null, false));
  return 1;
}

I use the ShutdownOnException method to log all fatal error conditions and to ensure that the application shuts down as soon as possible.

internal static void ShutdownOnException(UnhandledExceptionEventArgs e)
{  
  try
  {
    string message = (e.ExceptionObject != null) ?
      e.ExceptionObject.ToString() : 
      ResourceHelper.ShutdownOnError;
    EventLog.WriteEntry(ResourceHelper.DisplayTitle, message, 
      EventLogEntryType.Error);
  }
  catch {}

  try
  {
    MessageBox.Show(ResourceHelper.ShutdownOnError, 
      ResourceHelper.DisplayTitle, MessageBoxButtons.OK, 
      MessageBoxIcon.Hand, MessageBoxDefaultButton.Button1);
  } 
  catch {}
  
  if (!e.IsTerminating) Environment.Exit(1);
}

Much of this could have been accomplished better by using the System.Environment.FailFast method that is available in the .NET Framework 2.0, but this implementation is based on the .NET Framework 1.1.

The ShutdownOnException method accepts a System.UnhandledExceptionEventArgs parameter that describes what went wrong. The method first attempts to log information about the exception, including its stack trace, to the application event log by using the System.Diagnostics.EventLog.WriteEntry static method. It then attempts to display a message box to users to inform them that something bad happened. Finally, if the application isn't already shutting down, the Environment.Exit method ceases execution.

As documented thus far, ShutdownOnException is called only for unhandled exceptions on the main UI thread. What about fatal exceptions on other threads? To account for this, the first thing that the MainInternal method does is hook up event handlers to the current UnhandledException event of the AppDomain and to the Windows Form's Application.ThreadException event.

AppDomain.CurrentDomain.UnhandledException += 
  new UnhandledExceptionEventHandler(
    CurrentDomain_UnhandledException);
Application.ThreadException += 
  new ThreadExceptionEventHandler(Application_ThreadException);

The event handlers for these events delegate to ShutdownOnException.

private static void Application_ThreadException(
  object sender, ThreadExceptionEventArgs e)
{
  ShutdownOnException(new UnhandledExceptionEventArgs(
    e.Exception, false));
}
private static void CurrentDomain_UnhandledException(
  object sender, UnhandledExceptionEventArgs e)
{
  ShutdownOnException(e);
}

With this code in place, any crashes or fatal exceptions experienced by users of the application are logged, which makes debugging of production crashes much easier. Note that with the .NET Framework 2.0, most of this is automatically taken care of for you. All unhandled exceptions result in the process being torn down, and Dr. Watson steps in to take a dump of the application for later analysis and debugging.

Back to Top

Single-Instance Applications

Many applications, especially those on a Tablet PC, are meant to be single-instance applications. A single-instance application is one where only one process that executes that application is running at any given time, either on a particular desktop or on the whole computer, depending on how you define "single-instance" and on the needs of the application. In the case of Sudoku, I wanted each user on the computer to be able to run only one instance of Sudoku at a time. If Sudoku was implemented by using Microsoft Visual Studio 2005 and the .NET Framework 2.0, single-instance support is already available. However, because I'm using the .NET Framework 1.1, I had to craft my own support. For more information about single-instance support, see the .NET Matters column in MSDN Magazine's September, 2005 issue.

My single-instance support is built into the SingleInstance class, available in the SingleInstance.cs file in the Utilities folder. MainInternal uses SingleInstance in the following way.

using(SingleInstance si = new SingleInstance())
{
  if (si.IsFirst)
  {
    // Create the main form and run the app
    ...

    // Finished game successfully
    return true;
  }
  else
  {
    // Not the first Sudoku instance... show the other one
    si.BringFirstToFront();
    return false;
  }
}

I first create a new instance of the class and query its IsFirst property to determine whether any other instances of this application are currently running. If this is the first instance, the application proceeds as it normally would, creating and displaying the main form of the application. If it's not the first instance, the BringFirstToFront method brings the window of the first instance of the Sudoku application to the foreground, and then the secondary instance exits.

Single-instance functionality requires some form of inter-process communication (IPC), since one instance needs to be able to tell another instance that one already exists and that the secondary instance should not continue to load. The SingleInstance class actually relies on two different IPC mechanisms: a cross-process synchronization primitive and a memory-mapped file.

Creating bare-bones single-instance functionality is easy and can be accomplished in only a few lines of code.

static void Main()
{
  string mutexName = "2ea7167d-99da-4820-a931-7570660c6a30";
  bool grantedOwnership;
  using(Mutex singleInstanceMutex = 
    new Mutex(true, mutexName, out grantedOwnership)
  {
    if (grantedOwnership)
    {
      ... // core code here
    }
  }
}

When two or more threads need to access a shared resource at the same time, you need a synchronization mechanism to ensure that only one of the threads has access to the resource at a time. In our case, that "resource" is more logical than physical. It's the ability to have an instance of the application running. A mutex, as implemented in the System.Threading.Mutex class, is a synchronization primitive that grants exclusive access to only one thread at a time. If a thread acquires a Mutex, another thread that wants to acquire the same Mutex is suspended until the first thread releases the Mutex. Alternatively, rather than being suspended while waiting for the resource, a thread can attempt to acquire the Mutex and be told that the Mutex is already held by another thread.

Here, a Mutex is created with a GUID as a name (every different application that uses code like this would pick its own unique name). When you create a Mutex with a name, it can be used to synchronize threads that exist in separate processes, where each process refers to the Mutex by its predetermined and known name. One of the Mutex constructors accepts not only the name, but also an out Boolean parameter that indicates whether the Mutex could in fact be acquired. This makes it very easy to create single-instance functionality. The code creates a Mutex and checks to see whether it can be acquired. If the Mutex can be acquired, this instance of the application is the first instance and it can proceed. If the Mutex can't be acquired, then it's a secondary instance, and it should exit.

At its core, SingleInstance is built around the same principles, but it's also built out a bit more. First, rather than using a hard-coded GUID, SingleInstance builds up an ID based on the identity of the entry assembly in the current application.

private static string ProgramID
{
  get
  {
    Assembly asm = Assembly.GetEntryAssembly();
    Guid asmId = Marshal.GetTypeLibGuidForAssembly(asm);
    return asmId.ToString("N") + asm.GetName().Version.ToString(2);
  }
}

The ID is a combination of the assembly's type library GUID and the version of the assembly. This ID is then used in the following way to construct the name for the Mutex.

string mutexName = "Local\\" + ProgramID + "_Lock";

Like the previous simple single-instance example, my SingleInstance class constructor instantiates a Mutex, although it stores it to a member variable rather than to a local variable.

_singleInstanceLock = new Mutex(true, mutexName, out _isFirst);

The third parameter to the constructor is the Boolean variable that stores whether this instance of Mutex was able to acquire the lock, and it is this Boolean value that is then accessible through the IsFirst property.

public bool IsFirst { get { return _isFirst; } }

The implementation of IDisposable.Dispose by SingleInstance closes the Mutex.

If this was the extent of the required functionality, I'd be finished. However, many single-instance applications also bring the existing instance to the foreground when an attempt is made to launch a secondary instance. That functionality requires additional information to be passed between processes. Specifically, in addition to detecting that an instance already exists, a secondary instance must be able to determine which process it is that should be brought to the foreground. I've seen some applications do this by searching all of the top-level windows on the desktop for a specific name, but this process isn't very robust. Another approach, and the one that I took, is to use a memory-mapped file.

For our scenario, think of memory-mapped files as a form of shared memory. This allows one process to write some information to memory that another process can later read. Specifically, the first instance of the application can write its process ID to a memory-mapped file, and then secondary instances can read that process ID and use it to bring the primary instance to the foreground.

private void WriteIDToMemoryMappedFile(uint id)
{
  _memMappedFile = new HandleRef(this, 
    NativeMethods.CreateFileMapping(new IntPtr(-1), IntPtr.Zero, 
      PAGE_READWRITE, 0, IntPtr.Size, _memMapName));
  if (_memMappedFile.Handle != IntPtr.Zero && 
    _memMappedFile.Handle != new IntPtr(-1))
  {
    IntPtr mappedView = NativeMethods.MapViewOfFile(
      _memMappedFile.Handle, FILE_MAP_WRITE, 0, 0, 0);
    try
    {
      if (mappedView != IntPtr.Zero) 
        Marshal.WriteInt32(mappedView, (int)id);
    }
    finally
    {
      if (mappedView != IntPtr.Zero) 
        NativeMethods.UnmapViewOfFile(mappedView);
    }
  }
}

private uint ReadIDFromMemoryMappedFile()
{
  IntPtr fileMapping = NativeMethods.OpenFileMapping(
    FILE_MAP_READ, false, _memMapName);
  if (fileMapping != IntPtr.Zero && fileMapping != new IntPtr(-1))
  {
    try
    {
      IntPtr mappedView = NativeMethods.MapViewOfFile(
        fileMapping, FILE_MAP_READ, 0, 0, 0);
      try
      {
        if (mappedView != IntPtr.Zero)
          return (uint)Marshal.ReadInt32(mappedView);
      }
      finally
      {
        if (mappedView != IntPtr.Zero) 
          NativeMethods.UnmapViewOfFile(mappedView);
      }
    }
    finally { NativeMethods.CloseHandle(fileMapping); }
  }
  return 0;
}

Like cross-process mutexes, memory-mapped files can be named so that multiple processes can access them by name. A memory-mapped file is created by using the CreateFileMapping function exposed from kernel32.dll. The memory-mapped file is then mapped into the current address space by using the MapViewOfFile function, which is also exposed from kernel32.dll. MapViewOfFile provides the starting address for the memory, which can then be used with methods from the System.Runtime.InteropServices.Marshal class to read data from and write data to this memory. If a memory-mapped file has already been created, you can use the OpenFileMapping function from kernel32.dll to open it.

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
internal static extern IntPtr CreateFileMapping(IntPtr hFile, 
  IntPtr lpAttributes, int flProtect, int dwMaxSizeHi, 
  int dwMaxSizeLow, string lpName);

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
internal static extern IntPtr OpenFileMapping(int dwDesiredAccess, 
  [MarshalAs(UnmanagedType.Bool)] bool bInheritHandle, 
  string lpName);

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
internal static extern IntPtr MapViewOfFile(IntPtr hFileMapping, 
  int dwDesiredAccess, int dwFileOffsetHigh, int dwFileOffsetLow, 
  int dwNumberOfBytesToMap);

[DllImport("Kernel32", CharSet=CharSet.Auto, SetLastError=true)]
[return: MarshalAs(UnmanagedType.Bool)]
internal static extern bool UnmapViewOfFile(IntPtr pvBaseAddress);

[DllImport("kernel32.dll", SetLastError=true)]
[return: MarshalAs(UnmanagedType.Bool)]
internal static extern bool CloseHandle(IntPtr handle);
 

The SingleInstance constructor creates the Mutex and verifies whether it is the first to do so. If it is the first, the SingleInstance constructor uses the WriteIDToMemoryMappedFile method to store its own process ID for later retrieval by secondary instances. When a secondary instance runs and calls the BringFirstToFront method, the secondary instance uses the ReadIDFromMemoryMappedFile to access the primary instance's process ID. This process ID can then be used in concert with the ShowWindowAsync and SetForegroundWindow functions exposed from user32.dll to bring the primary instance to the foreground.

public void BringFirstToFront()
{
  if (!_isFirst)
  {
    uint processID = ReadIDFromMemoryMappedFile();
    if (processID != 0)
    {
      const int SW_SHOWNORMAL = 0x1;
      const int SW_SHOW = 0x5;
      IntPtr hwnd = new ProcessInfo(processID).MainWindowHandle;
      if (hwnd != IntPtr.Zero)
      {
        int swMode = NativeMethods.IsIconic(new HandleRef(
          this, hwnd)) ? SW_SHOWNORMAL : SW_SHOW;
        NativeMethods.ShowWindowAsync(hwnd, swMode);
        NativeMethods.SetForegroundWindow(new HandleRef(
          this, hwnd));
      }
    }
  }
}

Back to Top

Sudoku Algorithms

This section details the aspects of the application that are specific to the game of Sudoku.

Maintaining Puzzle State

When I plan to build an application like this, I like to get a minimal set of features working first that I can then build on. For Sudoku, this involves creating the necessary data structures to store the state of the puzzle.

A puzzle is easily represented as a two-dimensional array. Each cell needs to be able to store a digit or to be empty. The .NET Framework 2.0 provides a nice solution in the form of nullable types. Nullable types in the .NET Framework 2.0 allow value types to also take on a null value, and are represented using a new generic structure, Nullable<T>. Internally, Nullable<T> stores two values, one of type T (where T is the generic type parameter, and can be any value type, with the exception of another nullable type) that stores the value of the instance, and one Boolean that indicates whether the instance has a value or not. Generics aren't available in the .NET Framework 1.1; however, that doesn't mean that I'm out of luck. For the few types for which I want nullable support, I create my own replacements, such as NullableByte and NullableInt. Each of these replacements is a structure that contains a value of the relevant type (such as byte for NullableByte and int for NullableInt), and a Boolean value, the latter of which represents whether the integer value contains a usable value. This isn't as elegant as the .NET Framework 2.0 generic solution, especially since C# 2.0 provides syntactic support for Nullable<T>, but for my purposes, it's good enough. Because each cell in the puzzle grid can be either empty or a small numerical value, I store the grid as an array of NullableBytes.

[Serializable]
public sealed class PuzzleState : ICloneable, IEnumerable
{
  private NullableByte[,] _grid;
  private readonly byte _boxSize;
  private readonly byte _gridSize;
  ...
}

The PuzzleState class contains several pieces of information, including the size of the grid and its contents. In the current implementation, only 9x9 Sudoku grids are supported, but with some work, the application could be extended to support larger, and even non-square, grids.

One of the most important aspects of PuzzleState is its implementation of the ICloneable interface. This implementation, with which you can easily produce a deep copy of a PuzzleState instance, is used heavily in other aspects of this solution, such as puzzle solving, generation, and even game play related features, like undo support.

object ICloneable.Clone() { return this.Clone(); }
public PuzzleState Clone() { return new PuzzleState(this); }
private PuzzleState(PuzzleState state)
{
 _boxSize = state._boxSize;
 _gridSize = state._gridSize;
 _grid = (NullableByte[,])state._grid.Clone();
  ...
}

Back to Top

Analyzing and Solving Puzzles

Solving a Sudoku puzzle is really a special kind of search, and as such I can take advantage of standard search algorithms. A common search algorithm is depth-first search (DFS), which is typically taught as one of the first algorithms in a data structures and algorithms class in college. During a search, there are instances where multiple routes are presented for exploration, and in a DFS, one of those routes is explored in its entirety, including all routes that result from it, before proceeding to examine the other routes. Though you can implement a DFS by using an explicit stack, a DFS is frequently implemented through recursion. Imagine a tree node data structure that stores a value in addition to a list of child nodes. A DFS for a particular value within a tree might look something like the following.

public class TreeNode<T> where T : IComparable
{
  public TreeNode(T value) { Value = value; }
  public T Value;
  public List<TreeNode<T>> Children = new List<TreeNode<T>>();

  public TreeNode<T> DfsSearch(T v)
  {
    if (Value.CompareTo(v) == 0) return this;
    foreach (TreeNode<T> child in Children)
    {
      TreeNode<T> rv = child.DfsSearch(v);
      if (rv != null) return rv;
    }
    return null;
  }
}

Calling DfsSearch on a TreeNode<T> checks to see if the value stored within the node is the same as the one being searched for. If it is, the current node is returned. Otherwise, each child node's DfsSearch method is called to check if the value being searched for is in that child's subtree. This way, I can search the entire tree structure.

You can search for a Sudoku solution in the exact same way. Think of a particular state of a puzzle board as a node within a tree. From that state, I can get to other "child" states by entering a number into an empty cell in the grid. Therefore, from each state, there are a finite number of child states I can reach (one state for each value that I can enter into each empty cell). For a 9x9 grid, there are at most 729 child states, a finite number. Therefore, I can implement a search for a solution to any Sudoku puzzle with only a small amount of DFS-like code, something like the following.

static PuzzleState DfsSolve(PuzzleState state)
{
  switch (CheckSolution(state))
  {
    case PuzzleStatus.Solved: return state;
    case PuzzleStatus.CannotBeSolved: return null;
    default:
      NullablePoint cell = FindFirstEmptyCell(state);
      if (cell == null) return null;
      for (byte n = 0; n < state.GridSize; n++)
      {
        state[cell.Value] = n;
        PuzzleState result = DfsSolve(state);
        if (result != null) return result;
      }
      state[cell.Value] = null;
      return null;
  }
}

This method, similar to one employed by my Sudoku implementation, looks over the PuzzleState and determines whether it has been solved, whether it's currently in an invalid state (meaning there's a conflict somewhere) and definitely can't be solved, or whether it's still an unsolved puzzle in progress. Performing this check is similar to the DfsSearch of the TreeNode<T> checking to see if a node has been found that has the correct value, where I'm checking to see if I've found a solution. If I have found a solution, I return it. If I've found an invalid state, it means I made a mistake somewhere and need to backtrack. If the puzzle is still in progress, I need to enter a number in an empty cell. I find the first cell that's empty, and try every possible value, one after the other. If this puzzle can be solved, one of these values must work. I enter a number in each cell, and then recursively call DfsSolve. Eventually, if the puzzle is solvable, a solution will be found.

Unfortunately, this approach has a major drawback: it takes a very, very, very long time to complete. For a 9x9 board, I'll be trying up to nine values for every cell. With up to 81 cells to fill in, I could end up trying up to 981 boards. Even if I could process a number in a cell every nanosecond, chances are that neither I nor anyone that is reading this article would be alive to see it finish! In fact, the Earth's sun would likely burn out long before a solution is found. The real problem is that I'm looking through the entire search space, even though there are many things I can do to prune the search tree, such as limiting the amount of exploration that the search must do. When you play a game of Sudoku, there are many moves that you know you can't make, so why should the computer try those? Eliminate them.

There are a variety of techniques for teaching the computer what it can prune away, but one of the simplest is to inform the computer which numbers definitely cannot be in a particular cell. Then, when the computer does the brute-force search, it only has to consider those numbers that are still possible.

For every cell in the grid, I maintain a bit array. The idea here is that I can rule out certain numbers as possibilities for each cell by examining the other automatically set, or "given", numbers in that cell's column, row, and box; any number that appears in one of those cannot be in the cell. In principle, a bit array is a set of switches—on or off—that maintains Boolean values for a set of items. The easiest way to represent a bit array in the.NET Framework is to use the System.Collections.BitArray class. However, after I used this class in my implementation and did some profiling tests, I found that there would be some benefits to my creating a new implementation to suit my particular needs. So, I created my own implementation, FastBitArray, located in the FastBitArray.cs file in the Collections directory. (If you have ever written a bit bucket, the implementation should look very familiar.) Because this implementation of Sudoku never needs to deal with large values (given that it supports only 9x9 boards), FastBitArray wraps a single unsigned integer, allowing it to hold up to 32 Boolean values. Writing and reading operations are implemented with simple bit manipulation.

public bool Get(int index) 
{
  return (_bits & (1u << index)) != 0;
}
public void Set(int index, bool value) 
{
  bool curVal = Get(index);
  if (value && !curVal) 
  {
    _bits |= (1u << index);
    _countSet++;
  }
  else if (!value && curVal)
  {
    _bits &= ~(1u << index);
    _countSet--;
  }
}

I then maintain a two-dimensional array of FastBitArray instances, corresponding to the two-dimensional array that contains the values for each cell in the grid.

Knowing the possible cells results in the DfsSolve method functioning more quickly. Rather than trying every value in every cell, I can limit the search to only the possible candidate values in each cell. Additionally, the DfsSolve implementation that I showed finds and fills in the first empty cell found, which is a poor heuristic. Because only one of the values that I can try in a particular cell is the correct one, it makes sense to prune the tree by starting with a cell that I know has the fewest number of possible candidate numbers. So, DfsSolve can be further improved by finding the empty cell with the fewest number of possible candidates out of all of the empty cells. And every time a cell is set in DfsSolve, I can update the possible candidate numbers array, eliminating the number that was just set as a possibility for each affected cell.

While I made up DfsSolve for explanatory purposes, the implementation that I use in Sudoku is very similar in practice. Here are slightly trimmed down versions of the two core methods in my Solver class, available in the Solver.cs file. Notice the similarities to DfsSolve and the suggested augmentations I've described.

private static SolverResults SolveInternal(
  PuzzleState state, SolverOptions options)
{
  state = state.Clone();

  FastBitArray [][] possibleNumbers = 
    FillCellsWithSolePossibleNumber(state, 
    options.EliminationTechniques);

  switch (state.Status)
  {
    case PuzzleStatus.Solved:
    case PuzzleStatus.CannotBeSolved:
      return new SolverResults(state.Status, state, 0);
    default:
      if (options.AllowBruteForce)
      {
        SolverResults results = BruteForceSolve(
          state, options, possibleNumbers);
        return results;
      } 
      else return new SolverResults(
        PuzzleStatus.CannotBeSolved, state, 0, null);
  }
}

private static SolverResults BruteForceSolve(PuzzleState state, 
  SolverOptions options, FastBitArray [][] possibleNumbers)
{
  // Find cells with fewest possible candidates
  ArrayList bestGuessCells = new ArrayList();
  int bestNumberOfPossibilities = state.GridSize + 1;
  for (int i = 0; i < state.GridSize; i++)
  {
    for (int j = 0; j < state.GridSize; j++)
    {
      int count = possibleNumbers[i][j].CountSet;
      if (!state[i, j].HasValue)
      {
        if (count < bestNumberOfPossibilities)
        {
          bestNumberOfPossibilities = count;
          bestGuessCells.Clear();
          bestGuessCells.Add(new Point(i, j));
        }
        else if (count == bestNumberOfPossibilities)
        {
          bestGuessCells.Add(new Point(i, j));
        }
      }
    }
  }

  // Pick one
  SolverResults results = null;
  if (bestGuessCells.Count > 0)
  {
    Point bestGuessCell = (Point)bestGuessCells[
      RandomHelper.GetRandomNumber(bestGuessCells.Count)];
    FastBitArray possibleNumbersForBestCell = possibleNumbers[
      bestGuessCell.X][bestGuessCell.Y];
    for(byte p=0; p<possibleNumbersForBestCell.Length; p++)
    {
      if (possibleNumbersForBestCell[p])
      {
        PuzzleState newState = state;
        newState[bestGuessCell] = p;
        SolverOptions tempOptions = options.Clone();
        if (results != null) 
        {
          tempOptions.MaximumSolutionsToFind = (uint)(
            tempOptions.MaximumSolutionsToFind.Value – 
            results.Puzzles.Count);
        }

        // Recur
        SolverResults tempResults = 
          SolveInternal(newState, tempOptions);

        if (tempResults.Status == PuzzleStatus.Solved)
        {
          if (results != null && results.Puzzles.Count > 0)
          {
            results.Puzzles.AddRange(tempResults.Puzzles);
          }
          else
          {
            results = tempResults;
            results.NumberOfDecisionPoints++;
          }
          if (options.MaximumSolutionsToFind.HasValue &&
            results.Puzzles.Count >= 
              options.MaximumSolutionsToFind.Value) 
            return results;
        }

        newState[bestGuessCell] = null;
      }
    }
  }
  return results != null ? results : new  
    SolverResults(PuzzleStatus.CannotBeSolved, state, 0, null);
}

There's a lot going on here. The SolveInternal method starts by making a copy of the PuzzleState, and it works on that copy rather than on the original. That way, the PuzzleState provided by the caller is not affected by the actions initiated by Solver. It then uses the FillCellsWithSolePossibleNumber to analyze the current game board for any cells that can be only one possible candidate number, and it fills those in (I'll get back to this method in a moment). At that point, if the game board is either solved or is deemed unsolvable, the method returns. Otherwise, it uses brute-force search to fill in one cell. The next cell to fill in is selected based on which cell has the fewest possible candidate numbers (if multiple cells tie for the fewest, a random selection from those cells is made). After the cell is filled, the system recurs with a call to SolveInternal, and the process starts over, except with one more cell filled.

You'll notice that an instance of the SolverOptions class is driving some decisions made during the solve operation. The following code shows the SolverOptions public interface.

public sealed class SolverOptions : ICloneable
{
  public SolverOptions();
  public NullableUint MaximumSolutionsToFind { get; set; }
  public TechniqueCollection EliminationTechniques { get; }
  public bool AllowBruteForce { get; set; }
  public SolverOptions Clone();
}

MaximumSolutionsToFind enables a client of Solver to specify how many solutions it should attempt to find; the solver stops only after this many solutions have been found or after the solver determines that the requested number can't be reached. Note that MaximumSolutionsToFind is one of my custom NullableUint types; if it's null, the solver finds as many unbounded solutions as it can. The most common usage of this value, though, is to set it to either 1 or 2. By searching for one solution, I can quickly determine whether a puzzle is still solvable. By searching for two solutions, I can determine whether a puzzle has one and only one solution (if the solver finds two, even if there were more to be found, I know that there is more than one solution). The AllowBruteForce property determines whether brute-force search is allowed at all in the solver, or whether it must fill in a puzzle by using only the FillCellsWithSolePossibleNumber method. FillCellsWithSolePossibleNumber uses the EliminationTechniques property to figure out the possible numbers for each cell. (I'll discuss both AllowBruteForce and FillCellsWithSolePossibleNumber in Generating Puzzles.)

When discussing the prototype DfsSolve, I glossed over CheckSolution. In my actual Sudoku implementation, CheckSolution is replaced by PuzzleState.Status, a property that analyzes the current puzzle state and returns whether it's solved, unsolvable, or in some intermediate stage.

public PuzzleStatus Status
{
  get
  {
    if (_status == PuzzleStatus.Unknown) 
      _status = AnalyzeSolutionStatus();
    return _status;
  }
}
private PuzzleStatus AnalyzeSolutionStatus()
{
  FastBitArray numbersUsed = new FastBitArray(_gridSize);

  // Make sure no column has duplicates
  for (int i = 0; i < _gridSize; i++)
  {
    numbersUsed.SetAll(false);
    for (int j = 0; j < _gridSize; j++)
    {
      if (_grid[i, j].HasValue)
      {
        int value = _grid[i, j].Value;
        if (numbersUsed[value]) 
          return PuzzleStatus.CannotBeSolved;
        numbersUsed[value] = true;
      }
    }
  }

  // Same for rows
  for (int j = 0; j < _gridSize; j++)
  {
    numbersUsed.SetAll(false);
    for (int i = 0; i < _gridSize; i++)
    {
      if (_grid[i, j].HasValue)
      {
        int value = _grid[i, j].Value;
        if (numbersUsed[value]) 
          return PuzzleStatus.CannotBeSolved;
        numbersUsed[value] = true;
      }
    }
  }

  // Same for boxes
  for (int boxNumber = 0; boxNumber < _gridSize; boxNumber++)
  {
    numbersUsed.SetAll(false);
    int boxStartX = (boxNumber / _boxSize) * _boxSize;
    for (int x = boxStartX; x < boxStartX + _boxSize; x++)
    {
      int boxStartY = (boxNumber % _boxSize) * _boxSize;
      for (int y = boxStartY; y < boxStartY + _boxSize; y++)
      {
        if (_grid[x, y].HasValue)
        {
          int value = _grid[x, y].Value;
          if (numbersUsed[value]) 
            return PuzzleStatus.CannotBeSolved;
          numbersUsed[value] = true;
        }
      }
    }
  }

  // Now figure out whether this is a solved puzzle or a work 
  // in progress based on whether there are any holes
  for (int i = 0; i < _gridSize; i++)
  {
    for (int j = 0; j < _gridSize; j++)
    {
      if (!_grid[i, j].HasValue) return PuzzleStatus.InProgress;
    }
  }

  // If I made it this far, this state is a valid solution!  
  return PuzzleStatus.Solved;
}

PuzzleState.Status analyzes the current solution in multiple steps. It checks if the state's PuzzleStatus has already been computed and cached. If it has, PuzzleStatus can just return the cached value (any changes to the puzzle invalidate the cache). Assuming that the state's PuzzleStatus does have to be computed, Status uses the AnalyzeSolutionStatus method to see whether duplicate numbers are currently set in any column, row, or box. If there are duplicates, the puzzle obviously can't be solved. It then checks to see whether there are any empty cells in the grid. If there are, the puzzle is still in progress. Otherwise, it's a solved puzzle. Note that AnalyzeSolutionStatus doesn't indicate whether a puzzle that's in-progress can be solved, only whether it's currently solved, definitely unsolvable, or possibly solvable. It's the responsibility of Solver, as you've seen, to do the search for true solvability.

That's basically it for Solver. A public Solve method wraps the SolveInternal method, and some additional work is done to keep track of statistics about how the puzzle was solved, which is information that is useful during puzzle generation. This isn't a lot of code for what ends up being a very useful and powerful class.

Back to Top

Generating Puzzles

While generating random puzzles that have only one valid solution would seem to be the hardest problem to solve, it's actually a fairly easy piece of code to write, given all of the other pieces I now have to build upon. I'm sure there are plenty of algorithms available on the Web to generate puzzles. However, I've chosen my algorithm for several reasons: it's elegant, it's easy to code by using the classes and methods I've implemented up to this point, it's fast enough, and, best of all, it works. Of course, you can remove this generator from the accompanying code and use your own in its place, should you so desire.

The idea behind this algorithm is simple and is made up of two parts. First, I need to create a full and random Sudoku solution, meaning a random solution where all 81 cells in the grid are filled such that each row, cell, and box contains one and only one instance of each of the numbers 1 through 9. At first this might seem to be an incredibly difficult problem, so it might surprise you to learn that I've already implemented all of the necessary code to handle this approach: Solver.Solve. If you recall from my discussion about solving puzzles and finding the next cell to brute-force, I pick a random cell from among those with the least amount of possible candidate numbers. Therefore, in order to create a random, full Sudoku solution, all I need to do is solve an empty grid! Take a moment to think through that, because it's a powerful leap. On the first pass, the solver will randomly fill one of the 81 cells with a value, because all 81 cells have the same number of possible candidate numbers. After filling in that cell, some of the cells will now have fewer possible candidate numbers than others, and the solver will choose one of them at random. In this fashion, a random solution will be generated. In only a line or two of code, I can generate a random valid solution.

PuzzleState newPuzzle = Solver.Solve(
  new PuzzleState(), new SolverOptions()).Puzzle;

That's all there is to it! And while there may be a more efficient way of doing this, this code takes only a few milliseconds to run on my laptop, which is more than fast enough for my purposes.

The next step in my algorithm is to take the full solution and continually remove numbers from cells, randomly selecting a cell in the grid that's filled, and clearing it. After each removal, I again use my solver to determine whether there is now more than one solution. There's obviously only one solution to the original game board, and after removing a couple of numbers, there should still be only one solution. But at some point, after a significant number of cells are cleared, the game board will reach a state where it can be solved in multiple ways, each leading to different Sudoku solutions. Because that violates our goal of creating a game board with only one solution, I have to avoid such states. Therefore, after each removal, the Solver informs me whether I've now reached a point where the state is ambiguous. At that point, I can undo one removal to achieve a valid starting game board. The core of this approach looks like the following, as implemented in the Generator class in the Generator.cs file.

Point [] filledCells = GetRandomCellOrdering(newPuzzle);
int filledCellCount = filledCells.Length;
for(int filledCellNum=0;
  filledCellNum < filledCellCount && 
    newPuzzle.NumberOfFilledCells > _options.MinimumFilledCells; 
  filledCellNum++)
{
  byte oldValue = newPuzzle[filledCells[filledCellNum]].Value;
  newPuzzle[filledCells[filledCellNum]] = null;
  SolverResults newResults = Solver.Solve(
    newPuzzle, solverOptions);
  if (!IsValidRemoval(newPuzzle, newResults)) 
    newPuzzle[filledCells[filledCellNum]] = oldValue;
}

The GetRandomCellOrdering method creates a list of all 81 cells in the puzzle in a random order. The IsValidRemoval method checks to determine whether the last removal broke any rules, including the primary rule that the puzzle must still have only one solution. As you can see in the code, I loop over each of the 81 cells in the order returned by GetRandomCellOrdering. For each cell, I attempt to remove it, and if the resulting state is invalid according to IsValidRemoval, I put it back.

My generator implements what's known as a greedy algorithm. This means that the algorithm makes every valid move it finds, even if not making a valid move might ultimately create a better overall result. As with many greedy algorithms, while it doesn't produce an optimal result, it produces one that's good enough. Moreover, what constitutes an optimal solution for Sudoku is difficult to define, and optimal solutions are certainly not required. That's a good thing. Creating Sudoku puzzles falls into a category of problems known to be NP-complete. In layman's terms, this means that generating an optimal Sudoku puzzle can take a very long time. As a result, heuristics that provide "good enough" solutions are preferred.

As with the Solver, I've glossed over a few things here. First, you may notice in the game's configuration options, and in the GeneratorOptions class, that the generator can produce puzzles with 180-degree symmetry. This means that the cell located at [x,y] is filled in only if the cell at [10-x,10-y] is filled in (for example,. if the cell in the first column, second row is filled, then the cell in the ninth column. eighth row is filled also, and vice versa). This is implemented as a slight augmentation to the previously shown code. First, if symmetry is used, the ordering return by the GetRandomCellOrdering method is modified to create a random ordering of pairs of cells instead of a random ordering of individual cells, such that symmetrical pairs are always next to each other in the ordering. This then allows the code to remove values in pairs rather than individually, which restores those values as pairs if either removal resulted in an invalid puzzle.

The generator also supports difficulty levels. Difficulty levels are based on several configuration options, including the minimum number of cells that must be filled and the techniques a player may need to use to solve the puzzle. These techniques bring us back to the Solver and to the SolverOptions.EliminationTechniques property.

If you've read a book about Sudoku or browsed for information online, you'll find that there are a variety of formalized techniques that people use to solve puzzles. I've already described one technique, which is to eliminate a number as a possible candidate number in a cell because there is already the same number in another cell in the same row, column, or box. If you browse through the Techniques folder in the source code download, you'll find that I've implemented several techniques, including techniques such as naked subset, hidden subset, and x-wing. These techniques are used to set numbers in cells in the grid and to remove possible candidate numbers from each cell. Depending on the configured difficulty level for the Generator, the Solver is allowed to use only certain techniques, because some techniques require greater skill than others.

The number of puzzles that the Generator creates also influences the level of difficulty. Rather than generate only one puzzle, for certain difficulty levels the Generator creates multiple puzzles and then chooses the one that it determines to be the most difficult. The Generator makes that decision based on statistics returned by the Solver regarding which techniques were used to solve the puzzle and how many times each one was used.

As you'll see in the source, in the current implementation, there are three difficulty levels.

  • At the Easy level, three puzzles are generated, at least 32 cells must remain filled, and only one technique is required to solve the whole puzzle.
  • At the Medium level, 10 puzzles are generated, there is no minimum number of cells that must be filled, and several techniques may be required.
  • At the Difficult level, 20 puzzles are generated, there is no minimum number of cells that must be filled, and all of the implemented techniques may be required. In fact, the difficult level turns on the AllowBruteForce option for the solver. This means that a puzzle may be created that can't be solved by using only the supplied techniques, and that may even require a logical form of trial-and-error. If you disapprove of that approach, as some avid Sudoku fans do, you're welcome to change the code.

Back to Top

Windows Forms and Hardware Interactions

The following sections discuss aspects of the Sudoku game that deal with Tablet PC features and user experience.

Laying out Sudoku

An important aspect of any application for Tablet PCs is the rendering of that application. How does the application look on different sizes of Tablet PC screens? Does the application adapt well to different screen orientations? Does it deal well with high-DPI resolutions and large fonts? All of these are important to making an application successful. Of course, it's difficult to discuss these aspects of an application without first discussing its construction.

I've implemented Sudoku as a Windows Forms application, and with the exception of the OptionsDialog through which a user configures the game, the entire application is presented in one form, MainForm, available in the MainForm.cs file. The only control in the Controls collection of MainForm is an ImagePanel docked to fill the form, and it serves as the background for the whole application and as a container for the next level of controls on the form. ImagePanel is a simple control that I created whose sole purpose is to draw an image to fill the control.

internal class ImagePanel : NoFlickerPanel
{
  public ImagePanel(){}

  [DesignerSerializationVisibility(
     DesignerSerializationVisibility.Hidden)]
  [Browsable(false)]
  public Image Image { get { return _img; } set { _img = value; } }
  private Image _img;

  protected override void OnPaint(PaintEventArgs e)
  {
    if (_img != null) 
    {
      e.Graphics.DrawImage(_img, 0, 0, Width, Height);
    }
    base.OnPaint(e);
  }
}

ImagePanel derives from my NoFlickerPanel control rather than directly from System.Windows.Forms.Panel.

internal class NoFlickerPanel : Panel
{
  public NoFlickerPanel()
  {
    SetStyle(ControlStyles.DoubleBuffer | 
      ControlStyles.AllPaintingInWmPaint | 
      ControlStyles.UserPaint | ControlStyles.ResizeRedraw | 
      ControlStyles.SupportsTransparentBackColor, true);
  }
}

NoFlickerPanel serves as the base class for several of my specialized Panel-derived classes. It's only real purpose is to enable double-buffering, in addition to automatic redrawing when the control is resized. The double-buffering is very important for the look of the application, as it prevents the Panel from flickering when it's redrawn (hence its name). If you enable automatic repainting when the form is resized, the support for redrawing the form is painless when the user changes its size or changes the screen's orientation of the Tablet PC.

The background panel parents four other panels:

  • A NoFlickerPanel that serves as the container for the grid control (the control that actually renders the puzzle and allows for user interaction).
  • Two ImagePanels which hold the controls for the "screens" that allow you to start a new game or continue a previous game
  • A ScalingPanel, derived from NoFlickerPanel, that handles the entire layout for the controls that are used to interact with the game (such as the pen button, the number buttons, and the exit button).

One of the things that I really wanted in this Sudoku implementation was a very smooth experience that would make people say, "Wow, that looks great." To aid in this endeavor, I wanted to make sure that when the main form was resized, the controls on the form would move and resize accordingly, while still maintaining their relative sizes and positioning. ScalingPanel enables this.

internal class ScalingPanel : NoFlickerPanel
{
  public ScalingPanel(){}

  private Rectangle _initialBounds;
  private Hashtable _controlBounds;
  private bool _initialized;

  public void ConfigureByContainedControls()
  {
    _initialBounds = Bounds;
    _controlBounds = new Hashtable();
    foreach(Control c in this.Controls)
    {
      _controlBounds.Add(c, c.Bounds);
    }
    _initialized = true;
  }

  protected override void OnLayout(LayoutEventArgs levent)
  {
    if (_initialized && Width > 0 && Height > 0 && 
      levent.AffectedControl == this)
    {
      // Maintain original aspect ratio
      int newWidth = Width;
      int tmp = (int)(_initialBounds.Width / 
        (double)_initialBounds.Height * Height);
      if (tmp < newWidth) newWidth = tmp;

      int newHeight = Height;
      tmp = (int)(_initialBounds.Height / 
        (double)_initialBounds.Width * newWidth);
      if (tmp < newHeight) newHeight = tmp;

      // Keep track of max and min boundaries
      int minX=int.MaxValue, minY=int.MaxValue, maxX=-1, maxY=-1;

      // Move and resize all controls
      foreach(Control c in this.Controls)
      {
        Rectangle rect = (Rectangle)_controlBounds[c];

        // determine initial best guess at size
        int x = (int)(rect.X / (double)
          _initialBounds.Width * newWidth);
        int y = (int)(rect.Y / (double)
          _initialBounds.Height * newHeight);
        int width = (int)(rect.Width / (double)
          _initialBounds.Width * newWidth);
        int height = (int)(rect.Height / (double)
          _initialBounds.Height * newHeight);

        // set the new bounds
        Rectangle newBounds = new Rectangle(
          x, y, width, height);
        if (newBounds != c.Bounds) c.Bounds = newBounds;

        // Keep track of max and min boundaries
        if (c.Left < minX) minX = c.Left;
        if (c.Top < minY) minY = c.Top;
        if (c.Right > maxX) maxX = c.Right;
        if (c.Bottom > maxY) maxY = c.Bottom;
      }

      // Center all controls
      int moveX = (Width - (maxX - minX + 1)) / 2;
      int moveY = (Height - (maxY - minY + 1)) / 2;

      if (moveX > 0 || moveY > 0)
      {
        foreach(Control c in this.Controls) 
        {
          c.Location = c.Location + 
            new Size(moveX - minX, moveY - minY);
        }
      }
    }

    // Do base layout
    base.OnLayout (levent);
  }
}

ScalingPanel works on the premise that the initial relative sizes and positions of the controls (as created visually in the form designer of Visual Studio) are the relative sizes and positions that should be maintained throughout life of the application. After all of the child controls have been added to an instance of ScalingPanel, the client calls the ConfigureByContainedControls method of the ScalingPanel control. This method initializes several pieces of state that are used later when the form is laid out. First, it stores the current bounds of the control. Then, it loops through all of the child controls, storing each of their current bounds into a System.Collections.Hashtable, which is indexed by the Control. With the size of the ScalingPanel and the starting size and position of each individual control now in hand, the ScalingPanel knows the ratios of each control's size to the size of the containing panel, and it also knows the relative spacing between each control. When the panel changes size, ScalingPanel uses this information to shift the position and change the size of each contained control to maintain these size and positioning ratios.

All of the magic happens in the OnLayout override. First, ScalingPanel checks to see whether ConfigureByContainedControls has been called previously, avoiding any custom layout operations if it hasn't hasn't been called. It also checks to make sure that the panel's size is greater than 0 to avoid doing layout if the form is minimized or if similar operations are performed that would cause the control's size to shrink in a similarly dramatic fashion. Finally, ScalingPanel ensures that the target control of the layout operation is the panel itself, to avoid unnecessary duplication of layout operations if multiple controls that are related to the panel are required to perform layout.

The layout operation involves three main steps.

  1. It makes sure that the aspect ratio of the bounding box for all of the controls remains constant, so that the method computes the new width and height of that bounding box, based on the current width and height of the panel relative to the original width and height of the panel.
  2. It loops through all of the controls, scaling the position and size of each control based on the ratio of the original bounding box to the new bounding box.
  3. It centers the box of controls within the panel. This ensures that if the width to height ratio of the panel is dramatically different from the original ratio, the controls still remain centered within the panel.

This ScalingPanel functionality serves to do more than just maintain a pretty look when the user resizes the form. Because all calculations are based on relative sizes and positioning, I get support for high DPI resolution (frequently used on Tablet PCs) for free! Lack of support for high DPI resolutions is a common bug in many applications because frequently many developers and testers that work on applications that aren't originally planned to run on a Tablet PC aren't aware that DPI settings can be changed in Windows. Implementing controls like ScalingPanel can make your development and testing life much better.

Of course, all of this functionality in ScalingPanel only matters if the panel itself is resized, and if it's resized in a manner relative to the current size of the form. As mentioned earlier, the main form in Sudoku has four child-panel controls, but only two of them are docked to the panel. The controls panel is docked to the right of the form, and the panel that holds the grid control is docked to fill the rest of it. This makes it incredibly easy to maintain the relative sizes of both panels when the main form resizes. I ensure that the controls panel always occupies a third of the width of the form, which allows the grid panel to occupy the rest of it.

protected override void OnLayout(LayoutEventArgs levent)
{
  pnlControls.Width = Width / 3;
  base.OnLayout(levent);
}

To get a sense of how this affects the game board, consider the screenshot in Figure 5. Shrinking the width of the main form results in the layout in Figure 6, while widening the form results in the layout in Figure 7.

Figure 5. Default layout

Figure 6. Layout after decreasing width

Figure 7. Layout after increasing width

This approach also makes it very easy to adapt to the user's handedness. My SetHandedness method is called at application startup and any time users change their Windows handedness setting.

private void SetHandedness()
{
  DockStyle targetStyle = PlatformDetection.UserIsRightHanded ? 
    DockStyle.Right : DockStyle.Left;
  if (targetStyle != pnlControls.Dock)
  {
    pnlControls.SendToBack();
    pnlControls.Dock = targetStyle;
  }
}

This is a very simple method, and yet very powerful. With just a few lines of code, it checks the user's current handedness settings and accordingly changes whether the controls panel is docked to the right or left of the main form. That's it! The layout support already described takes care of the rest, and the game immediately responds to a change in user preferences (I discuss when this method is actually called in Power Awareness).

Figure 8 and Figure 9 demonstrate the change to the form that results from a change to the handedness setting.

Figure 8. Right-handed layout

Figure 9. Left-handed layout

I've discussed how the controls within the controls panel are resized, and how the two main panels on the form are resized relative to each other. The rest of the automatic layout support is handled by the OnResize override in MainForm.

protected override void OnResize(EventArgs e)
{
  // Do the base resizing
  base.OnResize(e);

  // Put the new puzzle and saved puzzle panels in the middle
  pnlNewPuzzle.Location = new Point(
    backgroundPanel.Location.X + 
      (backgroundPanel.Width - pnlNewPuzzle.Width) / 2, 
    backgroundPanel.Location.Y + 
      (backgroundPanel.Height - pnlNewPuzzle.Height) / 2);
  pnlSavedOrNewPuzzle.Location = new Point(
    backgroundPanel.Location.X + 
      (backgroundPanel.Width - pnlSavedOrNewPuzzle.Width) / 2, 
    backgroundPanel.Location.Y + 
      (backgroundPanel.Height - pnlSavedOrNewPuzzle.Height) / 2);

  // Make sure when I resize the form that the puzzle grid
  // stays in the center and square, as big as it can be while
  // not exceeding its parent's bounds
  int width = pnlGrid.Width;
  int height = pnlGrid.Height;
  int margin = 25;
  Size gridSize = width > height ? 
    new Size(height - margin, height - margin) : 
    new Size(width - margin, width - margin);
  thePuzzleGrid.Bounds = new Rectangle(
    new Point((width - gridSize.Width)/2, 
    (height - gridSize.Height)/2),
    gridSize);

  // Make sure no matter how the form resizes that the
  // marquee progress bar ends up in the center of the form.
  marqueeBar.Location = new Point(
    backgroundPanel.Location.X + 
      (backgroundPanel.Width - marqueeBar.Width) / 2, 
    backgroundPanel.Location.Y + 
      (backgroundPanel.Height - marqueeBar.Height) / 2);
}

This method performs a few simple layout operations. First, it centers the pnlNewPuzzle and pnlSavedOrNewPuzzle panels on the form (most of the time, these panels remain hidden, and are only shown at startup or when the user elects to start a new game). It also resizes and repositions the puzzle grid control within the grid panel (arguably, this could have been done just as easily by making the grid panel a ScalingPanel). Finally, it ensures that the progress bar, which shows the puzzle creation progress, is centered on the form.

The progress bar was an interesting challenge. Windows Forms 1.1 sports a progress bar, but out-of-the-box, it doesn't provide support for the marquee style. Microsoft Windows XP does, however. (The marquee style is used to represent a task without a predetermined starting and ending point. The progress bar shown when Windows starts is a marquee progress bar.) The Windows Forms ProgressBar control is a wrapper for the common controls progress bar in Windows XP, but it doesn't expose the marquee setting (Windows Forms 2.0 does). Therefore, rather than using the Windows Forms ProgressBar, I created my own wrapper for using the marquee style, as shown in Figure 10 (Of course, when you upgrade to Windows Vista, it becomes much prettier, as you can see in Figure 11).

internal sealed class MarqueeProgressBar : Control
{
  public MarqueeProgressBar()
  {
    SetStyle(ControlStyles.SupportsTransparentBackColor, true);
    SetStyle(ControlStyles.Selectable | 
      ControlStyles.UserPaint, false);
    BackColor = Color.Transparent;
    ForeColor = SystemColors.Highlight;
  }

  protected override CreateParams CreateParams
  {
    get
    {
      CreateParams cp = base.CreateParams;
      cp.ClassName = "msctls_progress32"; 
      if (!DesignMode) cp.Style |= PBS_MARQUEE;
      if (RightToLeft == RightToLeft.Yes)
      {
        cp.ExStyle |= WS_EX_LAYOUTRTL;
        cp.ExStyle &= ~(WS_EX_RIGHT | WS_EX_RTLREADING | 
                        WS_EX_LEFTSCROLLBAR);
      }
      return cp;
    }
  }

  protected override void OnForeColorChanged(EventArgs e)
  {
    base.OnForeColorChanged(e);
    if (base.IsHandleCreated)
    {
      SendMessage(PBM_SETBARCOLOR, 0, 
        ColorTranslator.ToWin32(this.ForeColor));
    }
  }

  protected override void OnBackColorChanged(EventArgs e)
  {
    base.OnBackColorChanged(e);
    if (base.IsHandleCreated)
    {
      SendMessage(PBM_SETBKCOLOR, 0, 
        ColorTranslator.ToWin32(this.BackColor));
    }
  }

  protected override ImeMode DefaultImeMode 
  { 
    get { return ImeMode.Disable; } 
  }

  protected override Size DefaultSize 
  { 
    get { return new Size(100, 23); } 
  }

  protected override void CreateHandle()
  {
    if (!RecreatingHandle)
    {
      NativeMethods.INITCOMMONCONTROLSEX icc = 
        new NativeMethods.INITCOMMONCONTROLSEX();
      icc.dwSize = 0;
      icc.dwICC = ICC_PROGRESS_CLASS;
      NativeMethods.InitCommonControlsEx(icc);
    }
    base.CreateHandle();
  }

  private IntPtr SendMessage(int msg, int wparam, int lparam)
  {
    return NativeMethods.SendMessage(new HandleRef(this, 
      this.Handle), msg, new IntPtr(wparam), new IntPtr(lparam));
  }

  protected override void OnHandleCreated(EventArgs e)
  {
    base.OnHandleCreated(e);
    SendMessage(PBM_SETRANGE, MINIMUM, MAXIMUM);
    SendMessage(PBM_SETSTEP, STEP, 0);
    SendMessage(PBM_SETPOS, VALUE, 0);
    SendMessage(PBM_SETBKCOLOR, 0, 
      ColorTranslator.ToWin32(BackColor));
    SendMessage(PBM_SETBARCOLOR, 0, 
      ColorTranslator.ToWin32(ForeColor));
    Start(DEFAULTSPEED);
  }

  private void Start(int speed)
  {
    if (!DesignMode && IsHandleCreated) 
      SendMessage(PBM_SETMARQUEE, speed == 0 ? 0 : 1, speed);
  }

  ... // constant definitions 

}

Figure 10. Marquee progress bar in Windows XP

Figure 11. Marquee progress bar in Windows Vista

Back to Top

Drawing Sudoku

The PuzzleGrid control, in the PuzzleGrid.cs file in the Controls folder, is the most important control in the application. It is the control that displays the Sudoku puzzle, provides the core mouse and keyboard support to play Sudoku, and enables pen-based interactions with the game.

As is the recommended practice, all drawing for the control is in response to a WM_PAINT message. In Windows Forms, this typically means either adding an event handler for the control's Paint event or overriding the OnPaint method. I chose the latter.

protected override void OnPaint(PaintEventArgs e)
{
  base.OnPaint(e);
  e.Graphics.PixelOffsetMode = PixelOffsetMode.HighQuality;
  DrawToGraphics(e.Graphics, e.ClipRectangle);
}

The drawing logic is factored into a separate DrawToGraphics method that accepts the target Graphics object and the rectangle that defines the bounds within the control that were invalidated. (Redrawing only what absolutely needs to be drawn significantly improves the performance of an application; when I augmented my initial implementation with this capability, the improvement was immediately noticeable). When you factor out the drawing code in this fashion, printing support is dramatically simplified, as is the ability to render the control to a Bitmap object. I show this in A Winning Animation, where I take advantage of this capability to display a congratulatory animation when a player solves a puzzle.

While fairly long, the code to draw the board is very straightforward. It begins by drawing the background images, which are located in the Images folder in the code download.

graphics.DrawImage(ResourceHelper.BoardBackgroundImage, 
  0, 0, Width, Height);
graphics.DrawImage(ResourceHelper.BoardImage, rect);

The first image is drawn to fill the control. The second image is drawn based on the rectangle that is returned by the private BoardRectangle property, which returns a rectangle that is just a bit smaller than the control, allowing for some thin margins around all sides. Following that, the size and position of each cell is determined by using a private GetCellRectangle method that takes into account the known size of each cell image in the background image relative to the size of the whole image, in addition to the sizes and positions of the gaps in the background image relative to the size of the whole image. I use the size returned by GetCellRectangle to determine whether a particular cell needs to be further examined and drawn at all.

for (int i = 0; i < State.GridSize; i++)
{
  for (int j = 0; j < State.GridSize; j++)
  {
    RectangleF cellRect = GetCellRectangle(rect, new Point(i,j));
    if (clipRectangle.IntersectsWith(Rectangle.Ceiling(cellRect)))
    {
      ... // cell drawn here
    }
  }
}

Similarly, I use the clipRectangle information provided by OnPaint to DrawToGraphics to avoid rendering cells that weren't invalided. Because drawing is a relatively expensive operation and invalidation frequently occurs for only small regions of the control (such as when a number is entered into a cell or when the cell that is selected changes), this makes a dramatic improvement to the usability of the control.

When I've decided that I should draw a cell, a few things happen. First, assuming that the puzzle has not yet been solved, the cell is checked to determine whether it's currently selected. If the cell is selected, I use one of the five green images (in the Images folder) to paint the cell. These five images correspond to whether the selected cell is one of the four corners or not.

Image selectedCellImage;
if (i == 0 && j == 0) 
  selectedCellImage = ResourceHelper.CellActiveUpperLeft;
else if (i == 0 && j == State.GridSize-1) 
  selectedCellImage = ResourceHelper.CellActiveUpperRight;
else if (i == State.GridSize-1 && j == 0) 
  selectedCellImage = ResourceHelper.CellActiveLowerLeft;
else if (i == State.GridSize-1 && j == State.GridSize-1) 
  selectedCellImage = ResourceHelper.CellActiveLowerRight;
else 
  selectedCellImage = ResourceHelper.CellActiveSquare;
graphics.DrawImage(selectedCellImage, 
cellRect.X, cellRect.Y, cellRect.Width, cellRect.Height);

Similar logic is used to paint the suggested cell image over a cell if the user has opted to be provided with a hint about what cell to attempt to fill in next and if the current cell being rendered is that suggested cell. The suggested cell is determined by using the exact same techniques that are used by the Solver and Generator to determine the puzzle difficulty level and puzzle solvability. The private SuggestedCell property computes the suggested cell based on these techniques, and caches the result so that it doesn't have to be recomputed every time the grid is drawn (the cache is invalidated when a change is made to the game state). At its core, SuggestedCell is implemented as follows.

TechniqueCollection tc = new TechniqueCollection();
FastBitArray [][] possibleNumbers = 
  PuzzleState.InstantiatePossibleNumbersArray(State);
foreach(EliminationTechnique et in 
  EliminationTechnique.AvailableTechniques)
{
  tc.Add(et);
  Hashtable ignored = null;
  State.ComputePossibleNumbers(tc, ref ignored, true, 
    true, possibleNumbers);
  for(int row=0; row<State.GridSize; row++)
  {
    for(int column=0; column<State.GridSize; column++)
    {
      if (possibleNumbers[row][column].CountSet == 1)
      {
        return _suggestedCell = new Point(row, column);
      }
    }
  }
}

The logic retrieves all of the available techniques, in order of easiest to most difficult (determined loosely by my estimation of a technique's difficulty level). Starting with the easiest, it determines if by running that technique, any empty cells in the grid have only one possible candidate number that can be filled in. If there are any such empty cells, the first one found is returned as the suggested cell. If none are found, the next technique is added to the mix and the possible candidate numbers are recomputed. Again, if any are found that have only one possible candidate number, the first of those found is returned. This continues until a suggested cell has been found or until all techniques have been exhausted without finding a suggested cell (which can happen only at the difficult level, where the brute-force technique is allowed during puzzle generation). In this case, the cell with the fewest remaining possible candidate numbers is returned as the suggested cell.

When a cell's background has been drawn, if it already has a number entered in it, that number is rendered.

if (State[i, j].HasValue)
{
  Brush b;
  if (ShowIncorrectNumbers &&
    State[i, j].HasValue && _solvedOriginalState != null && 
    State[i, j].Value != _solvedOriginalState[i, j].Value)
  {
    b = _incorrectValueBrush;
  }
  else if (_originalState != null && _originalState[i,j].HasValue)
  {
    b = _originalValueBrush;
  } 
  else b = _userValueBrush;

  graphics.DrawString((State[i, j] + 1).ToString(
    CultureInfo.InvariantCulture), setNumberFont, b,
    cellRect, _centerNumberFormat);
}

The brush to use in conjunction with DrawString is chosen from a selection of three cached brushes:

  • A red brush displays incorrect values.
  • A black brush displays values that were part of the original puzzle.
  • A blue brush displays input values.

The brushes are cached so that they don't have to be created every time the puzzle is drawn (another performance optimization). The brush that displays incorrect values is selected if:

  • The user has opted to be alerted to errors in his game play, and
  • The value in a cell doesn't match the value in the solved puzzle as created by the grid when a new puzzle was initially stored into it.
public void SetOriginalPuzzleCheckpoint(PuzzleState original)
{
  _originalState = original;
  if (original != null)
  {
    SolverOptions options = new SolverOptions();
    options.MaximumSolutionsToFind = 2;
    SolverResults results = Solver.Solve(original, options);
    if (results.Status == PuzzleStatus.Solved && 
      results.Puzzles.Count == 1)
    {
      _solvedOriginalState = results.Puzzle; 
    }
    else _solvedOriginalState = null;
  }
}

The last thing that DrawToGraphics does is render any ink that needs to be displayed on the grid, by initiating a call to its private RenderInk method. That brings me to the pièce de résistance of this Sudoku implementation: tablet pen support.

Back to Top

Enabling Tablet PC Interaction

Plain and simple, any game written for a Tablet PC must support pen-based interaction. At a bare minimum, an application enables the use of a pen as a navigation device. Ideally, the application supports handwriting recognition as a means of data entry—although there are varying degrees of support for that. As such, how much work is involved in enabling pen-based interaction varies. Your applications can also take advantage of gesture support, which allows certain pen movements to be interpreted as actions rather than as ink to be recognized. And for applications that are to be used on a Tablet PC with a touch screen, such as an ultra-mobile PC, touch support should also be considered during the design and development stage. My Sudoku implementation addresses all of these core tenets.

For a Sudoku game for Tablet PC, a core requirement is that you can write the numbers into the cells. This is what gives the game that pen-on-paper feel. Whether the handwritten numbers are then converted into rendered type rather than left in ink is up to the implementation; regardless, it's important that the application has the ability to recognize the input. I chose to recognize each piece of input individually, rendering all handwritten numbers in typewritten text rather than in the original handwriting.

All pen-based interaction is handled by the PuzzleGrid control. PuzzleGrid has two private members of types that hail from the Microsoft.Ink.dll assembly.

private InkOverlay _inkOverlay;
private RecognizerContext _recognizerCtx;

The InkOverlay class serves as the basis for all of our pen interaction handling. InkOverlay attaches to any existing Control, allowing for pen-based interaction with that control. The RecognizerContext class provides the basis for the handwriting recognition that I use to recognize numbers that are input by the user.

The EnableTabletSupport method on PuzzleGrid initializes both the InkOverlay and RecognizerContext. First, I retrieve the default recognizer to be used from the PlatformDetection class by using the previously discussed logic. I then use the returned Recognizer to configure the RecognizerContext.

Recognizer defaultRecognizer =
  PlatformDetection.GetDefaultRecognizer();
_recognizerCtx = defaultRecognizer.CreateRecognizerContext();
_recognizerCtx.Factoid = Factoid.Digit;

The RecognizerContext exposes a Factoid property, which enables you to give hints to the RecognizerContext about what sort of input it will be asked to recognize. By properly scoping the recognizer with factoids, I dramatically improve the quality of a user's interaction with my application, biasing the recognizer toward the classification of the input specified. In the case of Sudoku, the only input that the recognizer will be asked to recognize are the numbers 1 through 9. I bias the recognizer for this input by setting its Factoid property to Factoid.Digit. Factoid.Digit sets the recognizer's bias for a single digit, so that it expects and tends to return only single digit values (note that only a few factoids are guaranteed to work with recognizers across all languages; luckily, Digit is one of them).

After I configure the RecognizerContext, I initialize the InkOverlay.

_inkOverlay = new InkOverlay(this, true);
_inkOverlay.Ink.CustomStrokes.Add(ScratchpadStrokesID, 
  _inkOverlay.Ink.CreateStrokes());
_inkOverlay.Ink.CustomStrokes.Add(NormalStrokesID, 
  _inkOverlay.Ink.CreateStrokes());
_inkOverlay.DefaultDrawingAttributes.Color = _inkColor; 

The InkOverlay is instantiated and bound to the PuzzleGrid (the this reference, because this code exists within the PuzzleGrid class). I add two CustomStrokes collections to the InkOverlay. I'll focus on these later in the article, but in short, they'll make it easy to separate various types of ink input that are provided by the user, and to allow for easy persistence of that ink for saved games. I then configure the color of the ink for the overlay and set the overlay's CollectionMode.

The CollectionMode property tells the overlay whether it should be treating inputs as ink, gestures (movements of the tablet pen that are meant to be interpreted as specific actions rather than as content), or both. Attempting to enable an InkOverlay for gesture collection causes an error if no gesture recognizer is present, so I again use the PlatformDetection class to determine whether a gesture recognizer is available. If one is, I set CollectionMode.InkAndGesture; otherwise, I set CollectionMode.InkOnly.

bool gestureRecognizerInstalled = 
  PlatformDetection.GestureRecognizerInstalled;
_inkOverlay.CollectionMode = gestureRecognizerInstalled ? 
CollectionMode.InkAndGesture : CollectionMode.InkOnly;

Setting the CollectionMode tells the InkOverlay whether it can accept gestures, but not specifically which gestures to expect, nor what to do when they occur. For Sudoku, I only care about ApplicationGesture.Scratchout, which I use to enable users to scratch out a number that they previously entered into the grid, thus erasing it from the game board. To enable support for the gesture, I use the InkOverlay.SetGestureStatus method, and I register an event handler with the InkOverlay.Gesture event in order to handle the receipt of a scratch-out gesture.

if (gestureRecognizerInstalled)
{
  _inkOverlay.SetGestureStatus(
    ApplicationGesture.AllGestures, false);
  _inkOverlay.SetGestureStatus(
    ApplicationGesture.Scratchout, true);
  _inkOverlay.Gesture += 
    new InkCollectorGestureEventHandler(HandleGesture);
}

I then configure the AutoRedraw and DynamicRendering properties of the InkOverlay class. If AutoRedraw is set to true, the InkOverlay automatically renders any completed strokes that it has captured. If DyamicRendering is set to true, the InkOverlay automatically renders any strokes that are currently being captured. In order to enable double-buffering for ink rendering, I've chosen to draw captured ink myself, and I therefore set AutoRedraw to false. However, I'm more than happy to let the InkOverlay render ink that is currently being input by the user, and thus a value of true for DynamicRendering.

_inkOverlay.AutoRedraw = false;
_inkOverlay.DynamicRendering = true;

I'm almost finished configuring the InkOverlay. I need to tell the InkOverlay how to respond to certain pen interactions, and I do this by registered handlers for a bunch of events on the InkOverlay.

  • The Stroke event is raised when the user completes a new stroke.
  • The CursorInRange event is raised when a pen enters the physical detection range (proximity) of the tablet context.
  • The NewPackets event is raised when the InkOverlay receives new packets that contain data from a tablet pen that is touching the screen.
  • The NewInAirPackets event is raised when the InkOverlay receives packets that contain data about in-air movements from a tablet pen that is hovering above the screen.
  • The StrokesDeleting event is raised when strokes are being removed from the Strokes collection of the InkOverlay class.

Note   The CursorInRange and NewInAirPackets events are reported for electromagnetic digitizers and the mouse, but not for touch digitizers.

_inkOverlay.Stroke += new InkCollectorStrokeEventHandler(HandleStroke);
_inkOverlay.CursorInRange += 
  new InkCollectorCursorInRangeEventHandler(HandleCursorInRange);
_inkOverlay.NewPackets += 
  new InkCollectorNewPacketsEventHandler(HandleNewPackets);
_inkOverlay.NewInAirPackets += 
  new InkCollectorNewInAirPacketsEventHandler(HandleNewInAirPackets);
_inkOverlay.StrokesDeleting += 
new InkOverlayStrokesDeletingEventHandler(HandleStrokesDeleting);

Finally, the InkOverlay is enabled.

_inkOverlay.Enabled = true;

Back to Top

Recognizing Numbers Made from Multiple Strokes

When it's time to recognize a user's input, I make use of my RecognizeStrokes method.

private bool RecognizeStrokes(Strokes strokes, out byte number)
{
  number = 0;
  if (_recognizerCtx != null && strokes.Count > 0)
  {
    _recognizerCtx.Strokes = strokes;
    _recognizerCtx.EndInkInput();

    RecognitionStatus rs;
    RecognitionResult rr = _recognizerCtx.Recognize(out rs);
    if (rr != null && rs == RecognitionStatus.NoError)
    {
      string inputNumberText = rr.TopString;
      if (inputNumberText != null && inputNumberText.Length > 0)
      {
        try
        {
          number = byte.Parse(inputNumberText, 
            CultureInfo.InvariantCulture);
        } 
        catch(OverflowException){}
        catch(FormatException){}
        if (number >= 1 && number <= 9) return true;
      }
    }
  }
  return false;
}

RecognizeStrokes accepts two parameters: the collection of strokes to be recognized, and an output byte to contain the recognized digit. It has a Boolean return value that indicates whether the input was recognized in an acceptable way, meaning whether the output number can be used and treated as input. First, RecognizeStrokes checks to make sure that it has a valid RecognizerContext that it can use, and whether any strokes were supplied to it. Assuming that both conditions check out, it stores the strokes into the RecognizerContext and uses the EndInkInput method to notify the RecognizerContext that I'm finished accepting input for recognition. I then call the Recognize method to perform the recognition.

Recognize provides several pieces of information. The RecognitionResult object returned from Recognize contains information about the results of the operation, and you can use the RecognitionStatus enumeration value that is provided as an output parameter from the method to determine whether an error occurred during recognition, and, if one did occur, what kind. The TopString property of the RecognitionResult object returns as a string of the recognized text, which, for this scenario, should be a single digit. I then use the byte.Parse method to verify that a digit was in fact recognized, and if one was, the number is returned to the caller.

I can make use of RecognizeStrokes any time that a user enters a stroke, which is exactly what I did in my original implementation of Sudoku. But that presents a problem for any numbers that are written as multiple strokes (I didn't think of this at first, because I write all of my digits with a single, continuous stroke). As soon as one of the strokes in the multistroke input is received, RecognizeStrokes would get called, and in most cases would improperly recognize the input, given that it would be missing a good chunk of the number yet to be input.

I solve this problem in Sudoku by using a timer. When the InkOverlay receives a Stroke, I start a timer that has a period of half a second. If the InkOverlay receives another stroke before the timer expires, I reset the timer again, allowing another half second. Eventually, the timer expires before the player adds more strokes. When the timer expires, I call the event handler for the timer in which I recognize the user's input and store it into the puzzle in the appropriate cell, based on the location of the strokes that the player entered.

if (strokes.Count > 0)
{
  byte number = 0;
  bool recognized = false;

  Point cell = GetCellFromStroke(strokes[0]);
  if (CanModifyCell(cell)) 
  {
    recognized = RecognizeStrokes(strokes, out number);
  }

  _inkOverlay.Ink.DeleteStrokes(strokes);
  strokes.Clear();

  if (recognized) SetStateCell(cell, (byte)(number-1));
}

Note, however, that I don't treat all strokes equally. Specifically, I ignore strokes that I believe to be mistakes, such as where the pen accidentally brushed the screen or where the user tapped on the screen to change which cell is currently selected. To do that, I get the bounding box rectangle for the Stroke, converting from ink-space coordinates to control space.

Rectangle boundingBox = e.Stroke.GetBoundingBox();
InkToPixelSpace(ref boundingBox);

I then compare the width and height of this bounding box to the width and height of a cell in the grid. If the width or height of the bounding box is smaller than some predetermined fraction of the size of a cell, I ignore the Stroke. This is done by setting the event argument's Cancel property to true, so that the Tablet PC API deletes the stroke automatically. I also need to make sure that I restart the multistroke timer if any normal strokes were entered and are not yet recognized.

RectangleF cellRect = GetCellRectangle(ClientRectangle, Point.Empty);
if (boundingBox.Width < 
    cellRect.Width * MINIMINUM_BOUNDING_RATIO_TO_RECOGNIZE &&
  boundingBox.Height < 
    cellRect.Height * MINIMINUM_BOUNDING_RATIO_TO_RECOGNIZE)
{
  e.Cancel = true;
  ...
}

I also use a number of other events to recognize strokes. I assume that if users move their pens to a different cell—either while pressed against the screen or while in the air—they're finished entering the number for the previous cell. Therefore, at that point I stop the timer and automatically recognize the strokes, as if the timer had expired. (RecognizePreviousCellFromPacket checks to see if the current strokes are in a different cell from the cell underneath the pen; if they are and those strokes are in a cell that can be edited, it calls RecognizeStrokes.)

private void HandleNewInAirPackets(
  object sender, InkCollectorNewInAirPacketsEventArgs e)
{
  if (e.PacketData.Length >= 2)
  {
    RecognizePreviousCellFromPacket(
      new Point(e.PacketData[0], e.PacketData[1]));  
  }
}

The same logic occurs in response to the NewPackets event and in response to the Stroke event. Figure 12 shows the strokes for a number that is entered by using multiple strokes (for example, two strokes to create the number 4), and Figure 13 shows the results after the number has been recognized and rendered.

Figure 12. The digit 4 composed of multiple strokes

Figure 13. The digit 4 recognized from multiple strokes

Back to Top

Undo Support

One of my favorite features in any application is multilevel undo, so of course I chose to implement it in my Sudoku application. And with my implementation of PuzzleState.Clone, this is a fairly easy feature to implement.

The basic idea is that every time a change is made to the game board, I push a copy of the current state onto an undo stack.

private PuzzleStateStack _undoStates = new PuzzleStateStack();

The PuzzleStateStack type is a small, strongly-typed class that is derived from the Stack class in System.Collections. Later on, when I want to undo and revert back to a previous state, I pop a state from the undo stack and set it as the current state.

public void Undo()
{
  if (_undoStates.Count > 0) this.State = _undoStates.Pop();
}

The only trick is to make sure that every change to the current state pushes the current state onto the undo stack. Internally, PuzzleGrid can make sure that it pushes the state onto the stack any time that a change is made, but PuzzleGrid publicly exposes the current PuzzleState instance, and with that implementation, I can't be sure that every change will be successfully recorded. Therefore, PuzzleGrid exposes a SetUndoCheckpoint member and places the responsibility on the control consumer to ensure that SetUndoCheckpoint is called before any significant changes to the current state are made.

public void SetUndoCheckpoint()
{
  _undoStates.Push(State.Clone());
}

The PuzzleGrid also uses SetUndoCheckpoint internally. As an example of where and when it's called, consider the SetStateCell method that's used in the multistroke timer's event handler described in the previous section.

private void SetStateCell(Point cell, byte number)
{
  if (State[cell] != number)
  {
    SetUndoCheckpoint();
    ClearTabletStateCell(cell);
    State[cell] = number;
  }
}

The method first checks to make sure that the new value for the target cell isn't the same as the value that's already there. Assuming a change is necessary, the method sets an undo checkpoint, pushing the current PuzzleState onto the undo stack. The method then adds the value to the cell. Additionally, the method calls the ClearTabletStateCell method. ClearTabletStateCell deals with the scratchpad functionality in the game.

Back to Top

Scratchpad Support

One of the key features I implemented in Sudoku to make it feel more like playing on paper is the pencil note-taking feature, which is referred to as scratchpad in the code. The idea is that you can take notes, which allows you to keep track of your logical deductions along the way, as you might with a pencil in a paper-based puzzle (see Figure 14). These notes are not recognized as is ink that's written in pen (referred to as normal in the code); rather, they are stored along with the PuzzleState as additional tag data.

Figure 14. Taking notes with the scratchpad

When demonstrating how the InkOverlay that I use is instantiated and configured, I briefly mentioned two instructions.

_inkOverlay.Ink.CustomStrokes.Add(ScratchpadStrokesID, 
  _inkOverlay.Ink.CreateStrokes());
_inkOverlay.Ink.CustomStrokes.Add(NormalStrokesID, 
_inkOverlay.Ink.CreateStrokes());

The Ink property of the InkOverlay class returns the Ink object that's currently associated with the overlay, and its CreateStrokes method creates a new Strokes collection that's associated with that Ink object. By creating and maintaining two different Strokes collections, I'm able to easily separate strokes that are created in the normal pen mode and strokes that are created in the scratchpad pencil mode. This makes it easy to perform operations on only one of these types of strokes. To make it easy to retrieve the collections and to ensure that they're properly serialized along with the Ink object, both of these collections are added to the CustomStrokes collection of the Ink object (Serialization is the process of turning the Ink object into a byte array for storage. I use this for two different purposes, as I'll cover shortly). The CustomStrokes collection contains named Strokes collections that are persisted and made available for later use. I've defined a few helper properties that make it easy to query and work with these collections.

private Strokes NormalStrokes 
{
  get { return _inkOverlay.Ink.CustomStrokes[NormalStrokesID]; }
}
private Strokes ScratchpadStrokes
{
  get { return _inkOverlay.Ink.CustomStrokes[ScratchpadStrokesID];}
}
private bool HasScratchpadStrokes 
{ 
  get 
  {
    using(Strokes strokes = ScratchpadStrokes)
    {
      return strokes.Count > 0; 
    }
  }
}

Note that HasScratchpadStrokes, which returns true if the scratchpad strokes collection has any strokes in it, disposes of the scratchpad Strokes collection after it has finished using it. This seems odd, until you examine what the CustomStrokes indexer actually does. Here's pseudo-code for its implementation.

public Strokes this[string name]
{
  get { return new Strokes(this.m_CustomStrokes.Item(name)); }
}

It returns a new Strokes object rather than the one that was originally stored in the collection. It is this Strokes object that is being disposed, not the original. The same thing is true for accessing the main Strokes collection from the Ink object on the InkOverlay. The following is the pseudo-code for the Strokes object's get accessor.

public Strokes Strokes
{
  get
  {
    if (this.disposed)
    {
      throw new ObjectDisposedException(GetType().FullName);
    }
    return new Strokes(this.m_Ink.Strokes);
  }
}

Again, a new Strokes instance is returned every time you access the Strokes property, and you need to make sure that you dispose of each of these objects when you're finished with them. As an example, the following code shows the RenderInk method that PuzzleGrid uses to manually draw all of the ink (remember that we turned off AutoRedraw on the InkOverlay).

private void RenderInk(Graphics graphics)
{
  if (_inkOverlay != null)
  {
    using(Strokes strokes = _inkOverlay.Ink.Strokes)
    {
      if (strokes.Count > 0)
      {
        _inkOverlay.Renderer.Draw(graphics, strokes);
      }
    }
  }
}

The PuzzleGrid keeps track of whether the grid is or isn't in scratchpad mode; this switch is controlled by the pencil and pen buttons on the main form. When in scratchpad mode, the event handler for the Stroke event on the InkOverlay doesn't perform the multistroke logic described earlier. Instead, it adds each received stroke to the custom scratchpad's Strokes collection. However, there's some additional work that is necessary.

First, every scratchpad stroke must be kept as its own change in the undo stack so that individual notes can be undone. This is difficult in that there's no event on the InkOverlay that's fired before data from the stroke has already been added to the Ink object. To counteract this requires a bit of trickery. What I must do is delete the stroke from the Ink object, set an undo checkpoint, and then add the stroke back in. Unfortunately, a deleted stroke is not usable. The workaround is to serialize the stroke, delete the original, and then after setting the undo checkpoint, create a brand new stroke that's based on the data from the old one. I can then add this new stroke back to the Ink object.

Stroke s = e.Stroke;
TabletPropertyDescriptionCollection tpdc = 
  new TabletPropertyDescriptionCollection();
foreach (Guid g in s.PacketDescription)
{
  TabletPropertyDescription tpd = new TabletPropertyDescription(
    g, e.Cursor.Tablet.GetPropertyMetrics(g));
  tpdc.Add(tpd);
}
int[] packetData = e.Stroke.GetPacketData();
_inkOverlay.Ink.DeleteStroke(e.Stroke);
SetUndoCheckpoint();
s = _inkOverlay.Ink.CreateStroke(packetData, tpdc);

A Stroke is composed from a series of points, each being the result of some data packets. You use the GetPacketData method on the Stroke to retrieve an array of this packet data, and the CreateStroke method on the Ink object has an overload that accepts such an array of data and creates a new Stroke from it. The catch is that this method also requires a description of what's contained in the packet data, and this description comes in the form of a TabletPropertyDescriptionCollection. Therefore, before deleting the Stroke, you need to examine it for this information. The PacketDescription property on the Stroke returns an array of Guids, one for each type of packet data stored in the Stroke. These can be enumerated to build up the TabletPropertyDescriptionCollection that's necessary for the CreateStroke invocation.

With the undo support out of the way, I then give the scratchpad strokes a different color in order to differentiate scratchpad strokes from normal strokes.

s.DrawingAttributes.Color = _scratchpadInkColor;

Following that is another tricky bit of code. Previously in this article, I discussed at length the importance of supporting resizable forms, and I demonstrated how various controls, such as PuzzleGrid, adapt to being resized. Each stroke object also needs to be resized and repositioned so that it maintains its size and position, relative to the PuzzleGrid. This is easier said than done. My solution is that every scratchpad stroke must have associated with it at creation time the current size of the stroke and the current size of the grid. Every time the grid is resized, this information allows the stroke to be resized accordingly. By basing these transforms on the original size and position of the stroke rather than on its current size and position, I avoid problems that result from rounding errors related to storing this data in floating-point numbers; if frequent resizing occurs, such errors can lead to shifting of ink over time.

I store all of this bound information in the ExtendedProperties on the Stroke object. Applications can use Stroke.ExtendedProperties to access custom data that is stored in the Stroke object. This custom data is automatically serialized with the object. Therefore, I store six pieces of information into the ExtendedProperties: the location (x,y) and size (width, height) of the bounding box of the Stroke, as well as the current size of the PuzzleGrid control (width, height). The first parameter to the Add method on the ExtendedProperties is a Guid that you use to identify the particular extended property you're creating. This can be any Guid that you want, but if you're serializing Strokes to a persistent store so that you can retrieve the Strokes in a later run of the application, make sure that the Guids that you use for your extended properties are constant between runs of the application.

Rectangle boundingBox = s.GetBoundingBox();
using(Graphics graphics = CreateGraphics())
{
  InkSpaceToPixelSpace(graphics, ref boundingBox);
  s.ExtendedProperties.Add(OriginalStrokeBoundRectXGuid, 
    boundingBox.X);
  s.ExtendedProperties.Add(OriginalStrokeBoundRectYGuid, 
    boundingBox.Y);
  s.ExtendedProperties.Add(OriginalStrokeBoundRectWidthGuid, 
    boundingBox.Width);
  s.ExtendedProperties.Add(OriginalStrokeBoundRectHeightGuid, 
    boundingBox.Height);
  s.ExtendedProperties.Add(OriginalClientRectWidthGuid, 
    ClientRectangle.Width);
  s.ExtendedProperties.Add(OriginalClientRectHeightGuid, 
    ClientRectangle.Height);
}

Later, when the PuzzleGrid is resized, I use this information to modify each Stroke.

protected override void OnResize(EventArgs e)
{
  _cachedEmSize = -1;
  ResizeScratchpadInk();
  base.OnResize(e);
}
internal void ResizeScratchpadInk()
{
  if (_inkOverlay != null)
  {
    Rectangle currentClientRect = ClientRectangle;
    using(Strokes scratchpadStrokes = ScratchpadStrokes)  
    {
      foreach(Stroke s in scratchpadStrokes)
      {
        int originalBoundsX = (int)s.ExtendedProperties[
          OriginalStrokeBoundRectXGuid].Data;
        int originalBoundsY = (int)s.ExtendedProperties[
          OriginalStrokeBoundRectYGuid].Data;
        int originalBoundsWidth = (int)s.ExtendedProperties[
          OriginalStrokeBoundRectWidthGuid].Data;
        int originalBoundsHeight = (int)s.ExtendedProperties[
          OriginalStrokeBoundRectHeightGuid].Data;
        int originalClientRectWidth = 
          (int)s.ExtendedProperties[
            OriginalClientRectWidthGuid].Data;
        int originalClientRectHeight = 
          (int)s.ExtendedProperties[
            OriginalClientRectHeightGuid].Data;
        double scaleX = currentClientRect.Width / 
          (double)originalClientRectWidth;
        double scaleY = currentClientRect.Height / 
          (double)originalClientRectHeight;

        Rectangle newBounds = new Rectangle(
          (int)(originalBoundsX*scaleX), 
          (int)(originalBoundsY*scaleY), 
          (int)(originalBoundsWidth*scaleX), 
          (int)(originalBoundsHeight*scaleY));

        using(Graphics graphics = CreateGraphics())
        {                
          PixelSpaceToInkSpace(graphics, ref newBounds);
          s.ScaleToRectangle(newBounds);
        }
      }
    }
  }
}

For each stroke, I compute the ratio between the current size of the control and the size of the control when the stroke was created (note that this has to be computed for each stroke, because different strokes could have been created with different "original" control sizes, namely if the PuzzleGrid was resized between the creation of the strokes). I then use this ratio in conjunction with the original bounds of the stroke to calculate what the new bounds for the stroke should be. I then provide that information to the ScaleToRectangle method on the Stroke, which performs the actual resizing operation on the Stroke.

Having the scratchpad strokes in their own collection comes in handy when switching between normal and scratchpad mode. One of the visual distinctions the application makes between these two modes is that when in normal mode, scratchpad ink is grayed out, whereas when in scratchpad mode, the ink is solid black. This is done by changing the DrawingAttributes on each scratchpad Stroke instance. For example, to change the color of each stroke to grey, the following code is used.

using(Strokes strokes = ScratchpadStrokes)
{
  foreach(Stroke s in strokes)
  {
    s.DrawingAttributes.Color = Color.Gray;
  }
}

Having the scratchpad strokes in their own collection is also handy for when a user enters numbers into cells. When a user enters a number into a cell, I call the SetStateCell method (shown earlier). This method in turn calls the ClearTabletStateCell method. ClearTabletStateCell removes any scratchpad strokes that are in the cell, the idea being that the user has just entered a logically deduced number into the target cell, and thus the notes associated with that cell can be deleted to avoid unnecessary clutter. ClearTabletStateCell works by iterating through all of the strokes in the scratchpad strokes collection, deleting those found to be in the target cell.

private void ClearTabletStateCell(Point cell)
{
  if (_inkOverlay != null)
  {
    // Delete any scratchpad strokes in that cell
    using(Strokes strokes = ScratchpadStrokes)
    {
      for(int i=strokes.Count-1; i>=0; --i)
      {
        Stroke s = strokes[i];
        if (GetCellFromStroke(s) == cell)
        {
          strokes.RemoveAt(i);
          _inkOverlay.Ink.DeleteStroke(s);
        }
      }
    }
  }
}

Back to Top

Eraser Support

A neat feature supported by many Tablet PCs is pen-based eraser support. Flip your pen over, and you can use the back of it as a virtual eraser, assuming the application supports the concept. Sudoku does.

The InkOverlay class exposes an EditingMode property of type InkOverlayEditingMode. The default value for this property is InkOverlayEditingMode.Ink. However, when set to InkOverlayEditingMode.Delete, the cursor turns into an eraser, and dragging over existing strokes causes them to be deleted rather than causing new ink strokes to be created and stored. Typically, an application checks and sets this property in an event handler for the CursorInRange event on the InkOverlay, and that's exactly what Sudoku does. The InkCollectorCursorInRangeEventArgs instance that's supplied as a parameter to an event handler for the CursorInRange event has a Cursor property that returns a Microsoft.Ink.Cursor instance, and this object has on it a Boolean Inverted property that returns whether or not the pen is upside down, and thus whether the user is attempting to use the eraser. My event handler responds to this by setting the EditingMode on the InkOverlay appropriately.

Note   In-air packet detection works for electromagnetic digitizers and the mouse, but not for touch digitizers.

When a deletion stroke is received, the Stroke event on the InkOverlay is raised. However, rather than performing the multistroke recognition logic, which happens when the EditingMode is set to InkOverlayEditingMode.Ink, I execute code to clear the cell underneath the eraser.

Point currentStrokeCell = GetCellFromStroke(e.Stroke);
if (CanClearCell(currentStrokeCell)) 
{
  ClearStateCell(currentStrokeCell);
}

This erases only one cell because GetCellFromStroke picks the most likely target cell based on the bounding box on the Stroke. However, if a player drags the eraser across multiple cells, they're most likely expecting all touched cells to be erased. To erase all touched cells when users drag the eraser across multiple cells, similar logic is added to an event handler for the NewPackets event on the InkOverlay.

if (_mode == PuzzleGridMode.Eraser || e.Cursor.Inverted)
{
  if (e.PacketData.Length >= 2)
  {
    Point cell = TabletToCell(
      new Point(e.PacketData[0], e.PacketData[1]));
    if (CanClearCell(cell) && State[cell].HasValue) 
    {
      ClearStateCellWithInvalidation(cell);
    }
    if (_selectedCell.HasValue) 
    {
      InvalidateCell(_selectedCell.Value);
    }
    SetSelectedCell(cell);
    InvalidateCell(_selectedCell.Value);
  }
}

When in scratchpad mode, I apply a different logic. The default handling of the InkOverlayEditingMode.Delete on InkOverlay is to remove any strokes that are underneath the cursor. This is exactly the behavior I want while in scratchpad mode, so I let InkOverlay do its thing. There are only two catches. First, I need to set an undo point before I delete a stroke so that undo can be used to get the deleted stroke back. Second, I need to manually remove deleted strokes from the custom collections. I can accomplish both of these in an event handler for the StrokesDeleting event on the InkOverlay.

private void HandleStrokesDeleting(
  object sender, InkOverlayStrokesDeletingEventArgs e)
{
  SetUndoCheckpoint();
  using(Strokes normalStrokes = NormalStrokes) 
  {
    normalStrokes.Remove(e.StrokesToDelete);
  }
  using(Strokes scratchpadStrokes = ScratchpadStrokes)
  {
    scratchpadStrokes.Remove(e.StrokesToDelete);
  }
}

As alluded to earlier, a player can also use a scratch-out gesture to erase a number that was previously entered into a cell (players can also use scratch-out gestures to erase notes that were created in scratchpad mode), as shown in Figure 15.

Figure 15. Scratching out a number to erase it

In normal mode, this means responding to the Gesture event by determining over which cell the scratch-out gesture occurred, and then clearing that cell. One important thing to note, though, is that clearing a cell causes an undo checkpoint to be set. That undo checkpoint includes all ink currently stored in the InkOverlay. At this point, the strokes for the gesture are still in the overlay; therefore, I explicitly delete the strokes for the gesture before clearing the cell.

void HandleGestureInNormalMode(
  object sender, InkCollectorGestureEventArgs e)
{
  switch (e.Gestures[0].Id)
  {
    case ApplicationGesture.Scratchout:
      Point cell = GetCellFromStroke(e.Strokes[0]);
      _inkOverlay.Ink.DeleteStrokes(e.Strokes);
      RecognizePreviousNormalStrokes();
      if (CanClearCell(cell)) ClearStateCell(cell);
      break;
    default:
      e.Cancel = true;
      break;
  }
  Invalidate();
}

Handling scratch-out gestures in scratchpad mode is even easier. The application retrieves any scratchpad strokes that intersect with the scratch-out gesture strokes, and deletes them.

Back to Top

A Winning Animation

No game is complete without proper acknowledgement of the players' accomplishments when they win. Sure, there's a certain amount of self-pride when you fill in that last cell and revel in your power over logic, but it's nice when the game reinforces this and gives you a solid pat on the back, for example, the way the Microsoft implementation of Solitaire does (see Figure 16).

Figure 16. Solitaire window after winning a game

After implementing several animations for a win at Sudoku, and after getting several good suggestions from my fiancée Tamara (a Sudoku fan and my best beta tester), I settled on an animation where the cells fly off the board, rotating, spinning, and floating away, with the text, "Congratulations!" in a bright yellow font. In addition, I keep a faded image of the completed board behind the spinning numbers, after getting feedback that players wanted to see their completed game in addition to the spinning tiles. You can see an example of this in Figure 17.

Figure 17. Sudoku window after solving a puzzle

I built the animation into a control called WinningAnimation, which is available in the WinningAnimation.cs file in the Controls folder. When the main form is initialized, an instance of WinningAnimation is added to the Controls collection on the PuzzleGrid, docked to fill the parent grid control, and hidden.

_winningAnimation = new WinningAnimation(thePuzzleGrid);
thePuzzleGrid.Controls.Add(_winningAnimation);
_winningAnimation.Dock = DockStyle.Fill;
_winningAnimation.Visible = false;
_winningAnimation.BringToFront();

When a player solves the puzzle, the animation control is shown, causing it to start its animation.

The animation itself is based on a system of sprites. Sprites are just a fancy term for images or animations that are integrated into a larger scene. Typically, they can maintain their own state, can move around and interact with other sprites, and can do things like render themselves. For this animation, each flying cell is its own sprite.

internal class ImageSprite : IDisposable
{
  Point _location;
  float _angle;
  float _flipPosition;

  Size _velocity;
  float _angularVelocity;
  float _flipSpeed;
  bool _rotateAroundCenter;

  private Bitmap _bmp;
  ...
}

I create each sprite with a starting position within the control and a Bitmap that contains the main image to be rendered by the sprite. During the animation, a sprite maintains its current position, linear velocity, angular velocity, and flip speed (which is my made-up term for angular velocity around another axis of rotation). I also configure each sprite with a Boolean value that dictates whether it should rotate around its center or around its corner.

Each sprite renders itself. When the parent control is rendered, it supplies the target Graphics object to each sprite, and the sprite handles drawing to this Graphics object.

public void Paint(Graphics graphics)
{
  using(Matrix mx = new Matrix())
  {
    GraphicsState gs = graphics.Save();
    if (_rotateAroundCenter) mx.Translate(
      -_bmp.Width/2, -_bmp.Height/2, MatrixOrder.Append); 
    mx.Rotate(_angle, MatrixOrder.Append);
    if (_rotateAroundCenter) mx.Translate(
      _bmp.Width/2, _bmp.Height/2, MatrixOrder.Append); 
    mx.Translate(_location.X, _location.Y, MatrixOrder.Append);
    graphics.Transform = mx;

    // Draw the image
    float flipMult = ((float)
      Math.Cos(_flipPosition*Math.PI/180.0));
    if (flipMult > 0.001 || flipMult < -0.001)
    {
      graphics.DrawImage(_bmp, 
        new RectangleF(0, 1-Math.Abs(flipMult), 
        _bmp.Width, _bmp.Height*flipMult), 
        new RectangleF(0, 0, _bmp.Width, _bmp.Height), 
        GraphicsUnit.Pixel);
    }

    graphics.Restore(gs);
  }
}

Several things are going on here. First, I create a System.Drawing.Drawing2D.Matrix object. If you are unfamiliar with linear algebra and their influence on graphics, matrices are frequently used to transform from one coordinate space to another. The Matrix class makes it easy to apply transformations like rotations and translations, and handles all of the underlying mathematical operations for you. The Graphics class then makes it easy to draw with these transforms applied.

To begin, I save the current state of the Graphics object, so that I can restore it after I've drawn everything necessary under the current transform. I then rotate the matrix that I created by the sprite's current angle. Note that the sprite rotates around its corner, because the corner is at coordinate [0,0]. If it's necessary that this particular sprite rotate around its center, I can apply a translation before the rotation that moves the center of the sprite to [0,0]. Then, after I apply the rotation, I undo the translation.

After I rotate the sprite appropriately, I move it to the correct location (a translation transformation that is based on the sprite's current position). Finally, I want to draw the sprite, which I can do by using Graphics.DrawImage. To accommodate flipping the sprite, I change the vertical size of the target rectangle (think of an accordion growing and shrinking as it's played). When the vertical size is negative, DrawImage renders the image upside down, which creates the effect of the player looking through the back of the tile.

The overall animation control paints itself by relying on the sprite's ability to render itself.

protected override void OnPaint(PaintEventArgs pe)
{
  // Do base painting
  base.OnPaint(pe);

  // Draw the base underlying image
  if (_underImage != null) 
  {
    pe.Graphics.DrawImage(_underImage, 0, 0);
  }

  // Render all of the sprites
  if (_sprites != null && _sprites.Count > 0)
  {
    for(int i=_sprites.Count-1; i>=0; --i)
    {
      ImageSprite s = (ImageSprite)_sprites[i];
      s.Paint(pe.Graphics);
    }
  }

  // Show the congratulatory text
  string text = ResourceHelper.PuzzleSolvedCongratulations;
  if (_sf != null && text != null && text.Length > 0)
  {
    float emSize = GraphicsHelpers.GetMaximumEMSize(text,
      pe.Graphics, Font.FontFamily, Font.Style, 
      ClientRectangle.Width, ClientRectangle.Height);
    using(Font f = new Font(Font.FontFamily, emSize))
    {
      pe.Graphics.DrawString(text, f, Brushes.Black, 
        new RectangleF(2, 2, ClientRectangle.Width, 
          ClientRectangle.Height), _sf);
      pe.Graphics.DrawString(text, f, Brushes.Gray, 
        new RectangleF(-1, -1, ClientRectangle.Width, 
          ClientRectangle.Height), _sf);
      pe.Graphics.DrawString(text, f, Brushes.Yellow, 
        new RectangleF(0, 0, ClientRectangle.Width, 
          ClientRectangle.Height), _sf);
    }
  }
}

The method starts by rendering the underlying image (I'll get to that momentarily); it then proceeds to iterate through all of the sprites, and renders each by delegating to the sprite's Paint method, mentioned previously. Finally, the method renders the congratulatory text. The text is rendered through three calls to Graphics.DrawString—twice to draw the background or shadow for the text, and once to draw the yellow overlay. As the size of the control may vary, so must the size of the font that is used to render the text. The specified font size is retrieved by using the static method GetMaximumEMSize on my GraphicsHelpers class. This method accepts the text to be rendered, the target graphics object, the specified font family and style, and the width and height of the rectangle within which the text must fit. It then returns the largest font size that enables the specified text to fit into that bounding box with the specified font family and style.

public static float GetMaximumEMSize(string text,
  Graphics graphics, FontFamily fontFamily, FontStyle fontStyle, 
  float width, float height)
{
  const float MAX_ERROR = .25f;
  float curMin = 1.0f, curMax = width;
  float emSize = ((curMax - curMin) / 2f) + curMin;
  while(curMax - curMin > MAX_ERROR && curMin >= 1)
  {
    using (Font f = new Font(fontFamily, emSize, fontStyle))
    {
      SizeF size = graphics.MeasureString(text, f);
      bool textFits = size.Width < width && size.Height < height;
      if (textFits && emSize > curMin) curMin = emSize;
      else if (!textFits && emSize < curMax) curMax = emSize;
    }
    emSize = ((curMax - curMin) / 2f) + curMin;
  }
  return curMin;
}

I determine the maximum font size by using a binary search. I assume that the minimum font size is one point, while I assume the maximum font size to be the width of the bounding box. The method then starts by testing whether the specified text in the specified font fits into the bounding rectangle if rendered at a point size halfway between the minimum and the maximum. If the rendered text fits, then GetMaximumEMSize tries a larger value that is halfway between that halfway point and the maximum size. If it doesn't fit, the method tries a value that is halfway between that halfway point and the minimum size. This halving approach continues until the current minimum and maximum sizes are within a small distance from each other (.25 of a point), at which time the method returns the minimum as the selected font size.

This method is handy not only for rendering the congratulatory text, but for all text that is rendered in the application. When the form is resized, all of the controls in the application that render text (such as labels and buttons) recompute the size of the font to use based on the result of GetMaximumEMSize. This is what enables the fonts (the numbers on the number buttons, for example) to scale well as the form is resized.

The application creates the sprites when the WinningAnimation control is shown. The control takes a snapshot of what the PuzzleGrid control looks like at that moment in time (this is the image to be rendered under the sprites as they rotate and move around). It then creates 81 separate bitmaps from that larger bitmap, and assigns each of those bitmaps to a new sprite.

using(Bitmap bmp = new Bitmap(
  _grid.ClientRectangle.Width, _grid.ClientRectangle.Height))
{
  // Take a snapshot of the underlying puzzle grid
  using(Graphics g = Graphics.FromImage(bmp))
  {
    _grid.DrawToGraphics(g, _grid.ClientRectangle);
  }

  // Set up each individual sprite based on pulling out a section
  // of the underlying grid snapshot
  for(int i=0; i<_grid.State.GridSize; i++)
  {
    for(int j=0; j<_grid.State.GridSize; j++)
    {
      RectangleF cellRect = PuzzleGrid.GetCellRectangle(
        _grid.BoardRectangle, new Point(i,j));
      Bitmap smallImage = new Bitmap( (int)cellRect.Width, 
        (int)cellRect.Height, PixelFormat.Format32bppPArgb);
      using(Graphics g = Graphics.FromImage(smallImage))
      {
        g.DrawImage(bmp, 0, 0, cellRect, GraphicsUnit.Pixel);
      }
      ImageSprite s = new ImageSprite(smallImage);
      ...
    }
  }
}

I also create a timer when the control is shown. When I create the sprites, each is initialized to be at the appropriate position in the control, so that they exactly overlap their counterparts in the underlying grid. Each is then assigned random linear velocities, angular velocities, and flip speeds. Each sprite is also randomly assigned whether to rotate around its center or corner. Every time that the timer fires (24 times per second, assuming the CPU can keep up), I use each sprite's Update method to change the sprite's state appropriately (the Update method uses the various velocities for the sprite to update its positional information) and the control invalidates itself so that it redraws.

for(int i=_sprites.Count-1; i>=0; --i)
{
  ImageSprite s = (ImageSprite)_sprites[i];
  s.Update();

  Rectangle bounds = ClientRectangle;
  if (s.Location.X > bounds.Right + s.Image.Width || 
    s.Location.X < -s.Image.Width ||
    s.Location.Y > bounds.Bottom + s.Image.Width || 
    s.Location.Y < -s.Image.Width) 
  {
    _sprites.RemoveAt(i);
    s.Dispose();
  }
}
if (_sprites.Count == 0) _timer.Stop();
Invalidate();

When a sprite leaves the control's visible area, I dispose of it and remove it from the collection of sprites. When there are no more sprites to be displayed, I stop the timer. Stopping the timer is very important for performance reasons, but it's also especially important on mobile devices that need to be concerned with power consumption. Timers that fire frequently, like more than once a second, can prevent the system from going into power saving modes. Consequently, if you must use a timer that fires very frequently—which is not unusual for games and animations—make sure that you disable the timers if you don't absolutely need them to be running.

Back to Top

Saving State and Settings

Sudoku uses up to two files in the user's local application data store to maintain state for the application. The game uses one file to store application settings, and the other to store the state of an incomplete puzzle so that the user can continue this puzzle on a later run of the program. All settings and state are serialized to and deserialized from files that use the BinaryFormatter, which is available from the System.Runtime.Serialization.Formatters.Binary namespace.

The settings file contains information about the currently configured options (whether to show incorrect values, suggest which cell to attempt to complete next, prompt before deleting an in-progress puzzle, and create new puzzles with symmetry), the current size and position of the main form, and the current puzzle's level of difficulty. Having omitted the exception handling for the sake of a simplified presentation, my SaveSettings implementation is as follows.

private void SaveSettings()
{
  BinaryFormatter formatter = new BinaryFormatter();
  string path = Environment.GetFolderPath(
    Environment.SpecialFolder.LocalApplicationData) + 
    SAVED_SETTINGS_USER_PATH;

  DirectoryInfo parentDir = Directory.GetParent(path);
  if (!parentDir.Exists) parentDir.Create();
  
  ConfigurationOptions options = 
    _optionsDialog.ConfiguredOptions;
  PuzzleDifficulty difficulty = _puzzleDifficulty;
  Rectangle windowBounds = GetRestoreBounds(this);
  bool maximized = (WindowState == FormWindowState.Maximized);
  using(Stream s = File.OpenWrite(path))
  {
    formatter.Serialize(s, options);
    formatter.Serialize(s, difficulty);
    formatter.Serialize(s, windowBounds);
    formatter.Serialize(s, maximized);
  }
}

The LoadSettings method does the opposite—deserializing this information into objects from the settings file, and restoring that information back into the form and configured options.

My SaveStateFile method, which is used to save the state for a currently in-progress puzzle, is as follows (again, I removed exception handling).

internal void SaveStateFile()
{
  if (thePuzzleGrid.PuzzleHasBeenModified)
  {
    string path = Environment.GetFolderPath(
      Environment.SpecialFolder.LocalApplicationData) + 
      SAVED_STATE_USER_PATH;
    DirectoryInfo parentDir = Directory.GetParent(path);
    if (!parentDir.Exists) parentDir.Create();
    using(Stream s = File.OpenWrite(path))
    {
      BinaryFormatter formatter = new BinaryFormatter();
      formatter.Serialize(s,
        Assembly.GetEntryAssembly().GetName().Version);
      formatter.Serialize(s, thePuzzleGrid.State);
      formatter.Serialize(s, thePuzzleGrid.OriginalState);
      formatter.Serialize(s, thePuzzleGrid.UndoStates);
      formatter.Serialize(s, thePuzzleGrid.InkData);
    }
  }
}

Before doing the serialization, the SaveStateFile method first checks with the PuzzleGrid to see if the puzzle is in progress, meaning that it's been modified from the original in some way but it hasn't yet been solved. When SaveStateFile creates the state file, it stores five pieces of information to it. First, it stores the current Sudoku version, which is always a good idea, in case in a future version you decide to change what information is stored to the file and you need to be backwards compatible with state files from previous versions. It then stores the current PuzzleState, followed by the original PuzzleState that is provided to the PuzzleGrid; the latter is necessary in order to know which of the numbers in the current puzzle were there originally. Next, the undo stack is stored to the file. Finally, all of the Ink data on the overlay on the PuzzleGrid is serialized out. The InkData property on the PuzzleGrid returns a byte array that contains the serialized ink.

_inkOverlay.Ink.Save(PersistenceFormat.InkSerializedFormat)

As with settings, the load process is, for all intents and purposes, the opposite of the save method. The load process loads each of these pieces of information from the file and restores the information back into the PuzzleGrid.

Back to Top

Power Awareness

Power is something to be very aware of while implementing mobile applications. Users should know when the device is about to run out of power so that you can do what you can to prevent the user from losing data. When Sudoku detects that the battery is low or that the system is about to hibernate or go into standby, it saves the current puzzle. It does this in the main form by overriding the WndProc method (the main method in a Control for handling Windows messages), thereby saving the current game when the application receives a WM_POWERBROADCAST message (similar functionality can be achieved by using the Microsoft.Win32.SystemEvents class).

protected override void WndProc(ref Message m)
{
  base.WndProc (ref m);

  const int WM_POWERBROADCAST = 0x218;
  const int PBT_APMSUSPEND = 0x0004;
  const int PBT_APMSTANDBY = 0x0005;
  const int PBT_APMBATTERYLOW = 0x0009;

  switch(m.Msg)
  {
    case WM_POWERBROADCAST:
      switch((int)m.WParam)
      {
        case PBT_APMBATTERYLOW:
        case PBT_APMSTANDBY:
        case PBT_APMSUSPEND:
           SaveStateFile();
           break;
      }
      break;
    ...
}

This way, if the current session is lost, the player will be able to pick up where he or she left off in the puzzle.

In addition, several other non-power-related messages are handled in my WndProc override. For example, I mentioned earlier that I call SetHandedness to update the UI to reflect the user's current handedness settings when those settings change. The application is notified by Windows of a settings change when Windows sends it a WM_SETTINGSCHANGE message. My WndProc implementation checks to see if the change is for the SPI_SETMENUDROPALIGNMENT setting. If the change was for this setting, then it calls SetHandedness.

case WM_SETTINGSCHANGE:
  if (SPI_SETMENUDROPALIGNMENT == (int)m.WParam) SetHandedness();
  break;

Back to Top

Extending Sudoku

There are a myriad of ways that you can extend and enhance the accompanying Sudoku code. Here are a few ideas, along with some code to get you on your way.

Extending Undo Support

As implemented, undo support is very useful, but you can take it further. Every once in a while, I make a mistake while playing Sudoku (shocking, isn't it?), where I make an incorrect deduction, fail to see that the number I'm filling in already exists in the relevant row, column, or box, or other offenses like that. As soon as I make that mistake, I've lost the game, but it typically isn't until many moves later that I realize my mistake, and at that point, I'm too lazy to figure out where I messed up. More than just an undo feature, what I really need is a way to undo back to the point where I originally made a mistake. With both the undo functionality that is already implemented and the functionality of the Solver that I discussed earlier, this is easily implemented.

public void UndoUntilSolvableState()
{
  SolverOptions options = new SolverOptions();
  while(Solver.Solve(State, options).Status != 
PuzzleStatus.Solved && Undo());
}

Another useful feature is redo support. You can add support for redo with another PuzzleStateStack that you push states onto as you undo. Give it a shot. Just remember that as you redo, you need to push states back onto the undo stack.

Back to Top

Printing Puzzles

Extending Sudoku with support to print the current puzzle requires almost no work. For example, you can choose a particular key and extend the OnKeyDown method on the PuzzleGrid to execute code when that key is pressed.

using(PrintDialog pd = new PrintDialog())
using(PrintDocument doc = new PrintDocument())
{
  doc.PrintPage += new PrintPageEventHandler(HandlePrintPage);
  pd.Document = doc;
  if (pd.ShowDialog() == DialogResult.OK) doc.Print();
}

You can then handle the PrintPage event with code like the following.

private void Document_PrintPage(object sender, PrintPageEventArgs e)
{
  DrawToGraphics(e.Graphics, Bounds);
  e.HasMorePages = false;
}

That's all there is to it. Of course, this doesn't produce the nicest output. The size of the puzzle will be based on the current size of the PuzzleGrid, it won't be centered on the page, and the printed output will include things like the currently suggested cell. That's easily remedied by creating a new PuzzleGrid purely for printing support.

private void Document_PrintPage(object sender, PrintPageEventArgs e)
{
  using(PuzzleGrid pg = new PuzzleGrid())
  {
    pg.State = State;
    pg.ShowSuggestedCells = false;
    pg.ShowIncorrectNumbers = false;
    if (e.MarginBounds.Width > e.MarginBounds.Height)
    {
      pg.Height = e.MarginBounds.Height;
      pg.Width = pg.Height;
    } 
    else
    {
      pg.Width = e.MarginBounds.Width;
      pg.Height = pg.Width;
    }
    using(Matrix m = new Matrix())
    {
      GraphicsState state = e.Graphics.Save();
      m.Translate((e.PageBounds.Width - pg.Width) / 2, 
            (e.PageBounds.Height - pg.Height) / 2);
      e.Graphics.Transform = m;
      pg.DrawToGraphics(e.Graphics, 
        new Rectangle(0, 0, pg.Width, pg.Height));
      e.Graphics.Restore(state);
    }
  }
  e.HasMorePages = false;
}

You can take this a step further and print out a whole collection of puzzles. Every time the PrintPage handler is called, use the Generator class to create a brand new PuzzleState (rather than using the PuzzleState from the current grid, as in the previous example), and then use code like this to print it out. In doing so, you can print out as many puzzles as you want, setting HasMorePages to true until you've printed as many as you need.

Back to Top

Supporting Multiprocessors

Puzzle generation is very CPU intensive. For systems that have multiple processors, it makes sense to extend Sudoku's puzzle-generation infrastructure to take advantage of these multiprocessors (the current puzzle generation logic is single threaded). Adding support for this is actually much easier than it sounds, because each puzzle that is presented to a user is actually the result of multiple puzzles being generated, and then the hardest one chosen. Currently, this is done in a sequential loop.

private PuzzleState GenerateInternal()
{
  ArrayList puzzles = new ArrayList();
  for(int i=0; i<_options.NumberOfPuzzles; i++) 
  {
    puzzles.Add(GenerateOne());
  }
  puzzles.Sort(new SolverResultsComparer(_options.Techniques));
  return ((SolverResults)puzzles[puzzles.Count-1]).Puzzle;
}

Modify this so that the calls to GenerateOne are queued to the ThreadPool, and you've got instant support for concurrent puzzle generation. Of course, making this change requires some additional synchronization, because you'll need to postpone the call to puzzles.Sort until all of the background threads have completed generating their puzzles and have safely stored them into the collection (access to which would also need to be synchronized). One way to do this is to use something like my ThreadPoolWait class that I described in my October 2004 .NET Matters column in MSDN Magazine.

Back to Top

Copying the Puzzle to the Clipboard

Maybe you want to save a copy of the current puzzle. An easy way to do that is to copy a textual representation of it to the clipboard. Support for this is already built into PuzzleState, as its ToString override returns a textual representation of the puzzle; all you need to do then is copy that string to the clipboard. You can do this with just a little bit of code added to the OnKeyDown override on the MainForm.

if (e.KeyCode == Keys.C && e.Control && 
  thePuzzleGrid.Visible && thePuzzleGrid.Enabled)
{
  if (!thePuzzleGrid.CollectingInk)
  {
    string text = thePuzzleGrid.State.ToString();
    try { Clipboard.SetDataObject(text, true); } 
    catch(ExternalException){ }
  }
}

Back to Top

And So On...

The following suggestions are some other things that you might consider doing.

  • Implement other algorithms to solve and generate puzzles.
  • Implement additional optional hints for the player, or modify the current "suggest a cell" hint to explain why that cell is being suggested.
  • Support additional pen gestures.
  • Allow for puzzle grids larger than 9x9
  • Add a Windows Presentation Foundation (WPF) user interface.
  • Use Windows Communication Foundation (WCF) to enable collaborative puzzle solving over a network.
  • Create a Media Center Markup Language (MCML) interface for Windows Media Center in Windows Vista. (Note that after starting it, my Sudoku implementation is already easily playable with a remote control, by using the arrow keys to navigate and the number keys to enter values.)
  • Add more game-related features, such as high-score tracking and a game-play timer.

The possibilities are many, and I look forward to seeing what you come up with. Have fun coding!

Back to Top

Acknowledgements

Sincere thanks to the Tablet PC team for their support in this project; to David Bessenhoffer, for his superb images; to Calvin Hsia and Brian Goldfarb, for their ideas and suggestions; to John Keefe and Luke Stein, for introducing me to such a fascinating game; to Eliot Graff, for his help in getting this paper and code published; and to Tamara Spiewak, for her love and support (both for me and for Sudoku).

Biography

Stephen Toub is a Technical Lead on the MSDN team at Microsoft. He is the Technical Editor for MSDN Magazine, for which he also writes the .NET Matters column. Stephen developed the implementation of Sudoku that is a part of the Touch Pack, a software bundle that ships with all ultra-mobile PCs.

Back to Top