he Sudoku game is the latest craze in the UK, and it’s become so popular that every major newspaper now publishes puzzles with varying difficulty levels. I’ve found the process of solving Sudoku puzzles fascinating ever since I first saw one in the London Evening Standard newspaper. But after solving a few, I decided it would be even more interesting to write an application capable of both generating and solving Sudoku puzzles. In this article you’ll see how to use Windows Mobile 5.0 and Visual Studio 2005 to create such an application.

Sudoku originated in Japan. The name is is an abbreviation for a Japanese expression that translates to “The digit must remain single.”

There are many Sudoku variants, but by far the most popular is a 9 x 9 grid, divided into 3 x 3 regions. The grid is partially filled with the numbers 1 to 9. The challenge is to complete the remaining cells in such a way that:

	?
Figure 1. New Project Dialog: The figure shows the process of creating a new PocketPC Project in Visual Studio 2005 with Windows Mobile 5 installed.

• Every row contains a number in the range 1 to 9, each number occurring once.
• Every column contains a number in the range 1 to 9, each number occurring once.
• Every 3 x 3 region contains a number in the range 1 to 9, each number occurring once.

Creating a Windows Mobile 5 Project
I assume you have already installed Visual Studio 2005, and also downloaded Windows Mobile 5.0. If you haven’t downloaded Windows Mobile 5, you should download it now, if you want to follow along with the article or run the downloadable code.

	?
Figure 2. Sudoku Solver: The figure shows a finished version of the Sudoku Solver project running on a PocketPC.

After downloading and installing Windows Mobile 5, you’ll see several new items in the New Project dialog. To begin, create a new Windows Mobile Smart Device project (see Figure 1).

Choose the Device Application template, name the new project “SudokuGUI,” and select a project location.

Next, add a second Smart Device project to your application. This time, choose the Class Library project template and name the new project “Solver.” Solver contains all the logic for generating and solving Sudoku grids while the SudokuGUI project focuses mainly on the user interface?displaying the puzzle and accepting input. Figure 2 shows a running version of the SudokuGUI project.

Loading the Sudoku Solver Project
It’s worth your time to test-drive the finished Sudoku Solver project before digging into the code. To do that, extract all the files in the downloadable zip file to a directory of your choice and open the solution file SudokuUI.sln located in the SudokuUI folder.

Using Sudoku Solver
There are two ways to use Sudoku Solver:

1. You can request a new Sudoku puzzle by selecting the New Game menu item.
2. You can recreate an existing Sudoku game from a newspaper or puzzle book by starting with an empty grid, and entering the supplied numbers manually. To enter a puzzle manually, you must first clear the screen by clicking the “Clear” menu item.

Once you have a puzzle on-screen, clicking the “Solve” button causes Sudoku Solver to try to calculate a solution.

Although you can use the hardware keyboard, an easier way to enter the number for each cell is to select a cell and then click the button in the top row that has a caption matching the number you wish to enter in the cell. Figure 3 shows a solved puzzle.

	?
Figure 3. A Solved Puzzle: Here’s a puzzle solved by Sudoku Solver showing a correct solution.

Solving Puzzles with Sudoku Solver
The solved puzzle grid in Figure 3 shows three types of cells:

• The cells with a blue background are read-only cells (the background color may depend on your device)?the pre-supplied numbers from the original Sudoku puzzle.
• The cells with green numbers (only one in this case) indicate numbers I entered that were correct.
• The cells where the numbers are red are those I got wrong.

I have deliberately not put any effort into ensuring that the Sudoku grid generated is complex or supports varying difficulty levels?I’ll leave that up to you.

Each cell in the grid is a text box. The program must handle two events for each text box, but fortunately all the TextBoxes act identically, so you can use the same code for all of them. First, only numbers in the range 1 to 9 are allowed in the TextBoxes, which you can enforce via the Keypress event. Assign a delegate to each TextBox to handle the event.

   this.txt21.KeyPress += new       KeyPressEventHandler(this.KeyPressHandler)

Here’s the definition of KeyPressHandler:

   void KeyPressHandler(object sender,       System.Windows.Forms.KeyPressEventArgs e)   {      System.Windows.Forms.TextBox txt =          (System.Windows.Forms.TextBox)sender;      int keyData = (int)e.KeyChar;      if (! ( (keyData >= ASCII_ONE &&          keyData <= ASCII_NINE) || keyData ==          ASCII_BACKSPACE || keyData ==ASCII_DEL))      {         e.Handled = true;      }      else      {         if (keyData >= ASCII_ONE &&             keyData <= ASCII_NINE)         {            e.Handled = true;            txt.Text = e.KeyChar.ToString();         }      }   }

One of the KeyPressEventHandler delegate arguments is a KeyPressEventArgs instance, which provides information about the key that triggered the event. Wherever the ASCII number for the key is not within the expected range (1-9), the code simply ignores the key.

The other TextBox event you must handle is the GotFocus event. So that people can use the buttons at the top of the screen in Figure 3 to assign numbers to the text boxes, you need to keep track of the last textbox selected. The ActiveBox variable holds a reference to the most recently selected TextBox. Assign a delegate to the GotFocus event:

   this.txt33.GotFocus += new       EventHandler(this.GotFocusHandler);

Here's the GotFocusHandler definition:

   void GotFocusHandler(object sender,       System.EventArgs e)   {      if (sender is TextBox)         ActiveBox = (TextBox)sender;   }

Solving Sudoku Grids with Code
To solve Sudoku grids, you need to process ach row, column and 3 x 3 region, knowing that each number can only occur once in each. This rule allows you to identify the possible numbers that can be in the cells you're trying to fill. Usually, the rule alone is not enough to complete the grid, so you have to start looking for cells in the same row, column or region that contain identical likely candidates. For example, if you know columns 2 and 3 in row 4 both have 1 and 2 as possible candidates, then you can safely eliminate any occurrence of numbers 1 and 2 in all other columns in row 4. By following this logic for each row, column, and region, you can reduce the possible number of candidates even further. At this point, a very large number of cells would have been correctly filled.

However, when there are cells left with more than one possible candidate, you must introduce a guessing algorithm. The guessing algorithm used here is very simple. It looks for cells containing two possible candidates, selects one of them as the solution and then tries to solve the grid. If, using that "guess," you can't find a solution, the algorithm tries the other candidate. There are very impressive mathematical approaches I could have tried, but using this approach, I was able to solve all the Sudoku labeled "Difficult" in "Sudoku, Book 1" published by the The Times, a London newspaper. (I did this to pass the time during a six-hour flight in November).

The Sudoku grid is represented by an array of ArrayList objects. Each ArrayList represents a single cell in the grid and contains all the possible candidates for that cell. As the grid gets solved, the number of items in each ArrayList decreases. You have a solution when all the cells contain only one candidate.

Generating a Sudoku Grid
In my mind, the primary requirement for a generated Sudoku grid is that it should be random; every time someone requests a new game, the probability of getting a unique grid should be very high. To achieve this the application uses a random number generator to populate the grid. After generating a number for each cell, the program has to check that the grid as generated so far is a valid Sudoku grid; if not, you have to backtrack. This is why you need the two variables shown here:

   Dictionary[,]> s = new       Dictionary[,]>();   int[,] grid = new int[9, 9];

In the preceding code, one variable is a two-dimensional integer array called grid. This variable stores the Sudoku grid generated so far. The other variable, named s, is a dictionary in which each item is a two-dimensional integer array. Each step in the generation process stores the partially completed grid. Then, when the generation process needs to backtrack, it can use the dictionary to retrieve the last valid partial grid generated.

   // initialise the state to contain 1 to 9 in each    // cell   List[,] gridCopy = Initialise();   bool backTracking = false;   List used = new List();   List backTracked = new List();

In the code snippet above, gridCopy is a two-dimensional array of a list that can only contain integers. The list comes from the generic classes in the .net framework 2.0. Think of a List as a two-dimensional ArrayList where only integers are allowed to be stored. Each cell in gridCopy represents a cell in the Sudoku grid. Initially, you fill each cell in gridCopy with the allowable numbers 1 to 9, because at the start of the algorithm, any of those numbers can be assigned to any cell.

The code also declares a flag named backTracking which lets you know whether or not backtracking is required. Finally, we declare the variable used, which stores the numbers the process has attempted to use to fill a cell. Because the algorithm chooses a number between 1 and 9 at random, the used list prevents it from attempting to use a number that's already been tried unsuccessfully.

      for (int i = 0; i < 9; i++)      {         for (int j = 0; j < 9; j++)         {            used = new List();            if (backTracking)            {               i--;               j = 0;               bool getSucceeded =                   s.TryGetValue(i.ToString() +                     j.ToString(),out gridCopy);               for (int k = i; k < 9; k++)               {                  for (int z = 0; z < 9; z++)                  {                     grid[k, z] = 0;                  }               }

In backtracking mode, the code steps back one row (by decrementing the row loop counter i by 1 and resetting the column loop counter to zero). Moreover, it retrieves the last valid grid from the dictionary. The code continues:

            }                                bool assigned = false;               //try to assign  a number to this cell.            List[,] thisCopy = Copy(gridCopy);            Random rnd = new Random();            while (!assigned && used.Count < 9)            {               bool canUseValue = false;               int sudokuValue = rnd.Next(1, 10);               //can we use this value               while (used.Contains( sudokuValue) )               {                  sudokuValue = rnd.Next(1, 10);               }               canUseValue = Check(i, j, sudokuValue,                   grid);

The preceding code randomly picks an integer between 1 and 9, inclusive, and then checks whether or not that number can work in that position. The code checks by applying the three rules that govern number placement in a Sudoku grid. If the selected number is compliant with the rules, then it's a successful match. If not, the code keeps on trying different numbers until all possible numbers (1-9) are exhausted, in which case it has to backtrack.

               if (canUseValue)               {                  grid[i, j] = sudokuValue;                  if (s.ContainsKey(i.ToString() +                      j.ToString()))                  {                     s.Remove(i.ToString() +                         j.ToString());                  }                  s.Add(i.ToString() + j.ToString(),                      thisCopy);                  gridCopy = thisCopy;                  assigned = true;                  backTracking = false;               }               else               {                  if (!used.Contains(sudokuValue))                  {                     used.Add(sudokuValue);                  }               }            }            if (!assigned)            {               backTracking = true;            }         }      }      return grid;   }

As you may have noticed, I used the collection classes in System.Collections.Generic extensively in the backtracking algorithm to generate the Sudoku grid. The generic classes deliver greatly improved performance because they eliminate the boxing and unboxing that's necessary with the non-generic versions. I noticed more than 100% improvement when I switched to the generic classes. The end result of the Generate method is a valid Sudokku grid containing numbers 1 to 9 in all the 81 cells.

Observant readers probably noticed that the generator code always backtracks one row whenever it proves to be impossible to generate a valid Sudoku grid using the current row numbers. One way to improve the algorithm is make it a little bit more intelligent and backtrack by just one cell.

From Grid to Puzzle
After successfully generating a valid and complete Sudoku grid, the next thing is to turn it into a Sudoku puzzle by blanking some of the cells. Once again, the random number generator is your friend. The first step is to decide how many cells to turn blank. I used a random number generator to decide this:

   Random rnd = new Random();   int count = rnd.Next(52, 60);

That returns a number between 52 and 60?the number of cells to turn blank. To decide which cells to turn blank, again you can turn to the random number generator:

   for (int i = 0; i < count; i++)   {      int location = rnd.Next(0, 9);      int location2 = rnd.Next(0,9);      data[location, location2] = 0;   }

	?
Figure 4. Deploying the Solution: This dialog provides a list of device options for deploying the solution.

Finally, the application solves the Sudoku grid, just to ensure it's solvable, because removing numbers at random can result in a grid that doesn't have enough hints to complete.

Testing and Deployment
To review this application, you don't necessarily need a windows mobile device. Windows Mobile 5 ships with emulators for Pocket PC and Pocket PC Phone, which I used extensively during development. To deploy the application, go to the Build menu and select "Deploy Solution." You will see a dialog box similar to Figure 4 for project in your solution (unless you choose not to see the dialog by clearing the check box at the bottom of the dialog).

Choose the device type that matches the device where you want to deploy the project, or select one of the emulators.

I tested the application on both the Pocket PC Emulator and a Windows Mobile 5.0 PocketPC device, XDA Exec, manufactured by HTC. I hope this article has whetted your appetite for Smart Device development. Happy coding!