• Article

August 2014

Volume 29 Number 8

Test Run : Solving Sudoku Puzzles Using the MSF Library

James McCaffrey

James McCaffreyA Sudoku puzzle is an example of what’s called a constraint satisfaction problem (CSP). One way to tackle CSPs programmatically is to use the Microsoft Solver Foundation (MSF) library. Although it’s highly unlikely you’ll ever need to solve a Sudoku puzzle as part of your normal work responsibilities, there are at least three reasons why you might want to read this article. First, the techniques presented here can be used to solve many realistic problems. Second, this article will introduce you to the MSF library and its capabilities. And third, you might just find that solving Sudoku puzzles programmatically is interesting and entertaining.

To get an idea of where this article is headed, take a look at the demo program in Figure 1. The demo console application begins by setting up and displaying the data for a typical Sudoku puzzle. Next, it programmatically defines constraints (required conditions) that are common to all Sudoku puzzles, and then sets up the data constraints that are specific to the puzzle. Then, behind the scenes, the demo uses the MSF library to solve the puzzle. The demo concludes by displaying the solution.

Sudoku Using the Microsoft Solver Foundation
Figure 1 Sudoku Using the Microsoft Solver Foundation

This article assumes you have at least intermediate-level programming skills and a vague idea of what Sudoku puzzles are, but does not assume you know anything about constraint satisfaction problems or the MSF library. The demo program is coded using C# but you should be able to refactor the demo to other .NET languages without too much trouble. All the code is presented here and it is also available in the code download that accompanies this article at msdn.microsoft.com/magazine/msdnmag0814. All normal error checking has been removed to keep the main ideas clear.

The Microsoft Solver Foundation Library

The MSF version 3.1 library is available as a separate code download. The location of the download has tended to move around over time but I found it at bit.ly/1vayGh1. I prefer to use 32-bit libraries when experimenting so I clicked on that link, which gave me the option to run or save the MicrosoftSolverFoundation.msi installation package. I selected the Run option.

The installation wizard tells you you’re installing the Express Edition. MSF originally came in two versions, a free Express Edition and a for-purchase enterprise edition, but the enterprise edition has been discontinued. The MSF library is essentially no longer being actively developed, but the current 3.1 version works fine for me. After the quick but somewhat clunky installation process finishes, the key library file Microsoft.Solver.Foundation.dll is copied to your machine in directory C:\Program Files (x86)\Reference Assemblies\­Microsoft\Framework\.NETFramework\v4.0.

To create the demo program, I launched Visual Studio and selected the C# console application program template and named it SudokuSolver. The demo has no significant Microsoft .NET Framework version dependencies so any relatively recent version of Visual Studio should work. After the template code loaded, in the Solution Explorer window I renamed file Program.cs to SudokuProgram.cs and Visual Studio then automatically renamed class Program. The overall structure of the demo program, with a few minor edits to save space, is presented in Figure 2.

Figure 2 Overall Program Structure

using System;
using Microsoft.SolverFoundation.Services;
namespace SudokuSolver
{
  class SudokuProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin MS Solver Foundation Sudoku demo");
      Console.WriteLine("The problem is: ");
      int[][] data = new int[9][];
      data[0] = new int[] { 0, 0, 6,
        2, 0, 0,
        0, 8, 0 };
      data[1] = new int[] { 0, 0, 8,
        9, 7, 0,
        0, 0, 0 };
      data[2] = new int[] 
      { 0, 0, 4,
        8, 1, 0,
        5, 0, 0 };
      data[3] = new int[] 
      { 0, 0, 0,
        0, 6, 0,
        0, 0, 2 };
      data[4] = new int[] 
      { 0, 7, 0,
        0, 0, 0,
        0, 3, 0 };
      data[5] = new int[] 
      { 6, 0, 0,
        0, 5, 0,
        0, 0, 0 };
      data[6] = new int[] 
      { 0, 0, 2,
        0, 4, 7,
        1, 0, 0 };
      data[7] = new int[] 
      { 0, 0, 3,
        0, 2, 8,
        4, 0, 0 };
      data[8] = new int[] 
     { 0, 5, 0,
       0, 0, 1,
       2, 0, 0 };
      // all program logic here
      Console.WriteLine("End Solver Foundation Sudoku demo");
      Console.ReadLine();
    }
    static void AddDataConstraints(int[][] data,
      Model model, Decision[][] grid) { . . }
    static int NumberSolutions(SolverContext problem) { . . }
  }
} // ns

At the top of the Visual Studio template-generated source code, I removed all unnecessary using statements except for the one that references the top-level System namespace. Next, I added a reference to the MSF library DLL file and then added a using statement that references the library to bring it into scope.

Almost all of the work is performed inside method Main. Two helper methods, AddDataConstraints and NumberSolutions, are just conveniences to keep the code inside Main a bit tidier. After a preliminary begin-message, the demo sets up the Sudoku puzzle data in an array-of-arrays style matrix.

Unlike many languages, C# supports a true two-dimensional array, but as you’ll see, the array-of-arrays approach is easier to work with. Even if you’re an experienced programmer, if you don’t often work with numerical programming, you may not be familiar with matrix coding techniques. The demo data matrix is represented in Figure 3. Data can be accessed by individual cell, or by an entire row, but not by an entire column. For example, data[0][2] is the cell at row 0 and column 2 and has value 6, and data[1] references the entire second row. There’s no convenient way to access a column. The blank cells in Figure 3 actually have 0 values because C# automatically initializes integer-array cells to all 0s.

The Problem Data Matrix
Figure 3 The Problem Data Matrix

Setting up the Problem

After the problem data matrix has been created, the demo program displays the values to the shell:

for (int r = 0; r < 9; ++r)  {
  for (int c = 0; c < 9; ++c)  {
    if (data[r][c] == 0)
      Console.Write(" _");
    else
      Console.Write(" " + data[r][c]);
  }
  Console.WriteLine("");
}

Here, the loop limits are hardcoded as 9. In my opinion, especially with demo programs, sometimes it’s better to keep things simple rather than make code more general. Next, the demo makes the first use of MSF code:

SolverContext problem = SolverContext.GetContext();
Model model = problem.CreateModel();
Decision[][] grid = new Decision[9][];
for (int r = 0; r < 9; ++r)
  grid[r] = new Decision[9];

Working with the MSF library has a somewhat unusual feel because the code was developed in a hybrid research-development environment. You can think of the first two lines as a magic incan­tation to create a CSP object. Rather than working with a single object, as you’re likely used to, the MSF library tends to use multiple objects such as the problem and model objects here.

The grid object is an array-of-arrays style matrix where each cell is a Decision object. You can think of a Decision object as an encapsulation of an answer. Or put another way, to solve a Sudoku puzzle you need to determine 9 x 9 = 81 values. Each of these values is represented by a Decision object and the demo stores them in a matrix.

At this point, the grid matrix has uninstantiated Decision objects. The demo instantiates each cell like so:

for (int r = 0; r < 9; ++r)
  for (int c = 0; c < 9; ++c)
    grid[r][c] = new Decision(Domain.IntegerRange(1, 9),
      "grid" + r + c);
for (int r = 0; r < 9; ++r)
  model.AddDecisions(grid[r]);

The Decision constructor accepts two parameters. The first describes the data type of an answer. Here, each answer is an integer between 1 and 9. The second parameter is a non-optional name as a string. These names must be unique, so the demo programmatically assigns names “grid00,” “grid01” and so on to each of the 81 Decision objects. After the Decision objects have been instantiated, they must be added to the Model object. The AddDecisions method can accept a single Decision object or an array of Decision objects, so the demo passes the nine rows of the grid matrix. An alternative would be to use two nested loops, like this:

for (int r = 0; r < 9; ++r)
    for (int c = 0; c < 9; ++c)
      model.AddDecisions(grid[r][c]);

Adding Generic Constraints

There are three sets of generic constraints that are common to all Sudoku puzzles. First, the values in each row must all be different. Second, the values in each column must all be different. And third, the values in each 3x3 sub-cube must all be different. Taking care of the first set of constraints is easy:

Console.WriteLine("Creating generic row constraints");
for (int r = 0; r < 9; ++r)
  model.AddConstraint("rowConstraint" + r, 
  Model.AllDifferent(grid[r]));

The AddConstraint method accepts a constraint name followed by a constraint. Here, the names are “rowConstraint0,” “rowConstraint1” and so on. The demo uses the AllDifferent method to create a constraint. In words, for each of the nine rows, add a constraint that all the values in the row must be different.

Adding the generic column constraint requires a little bit more effort:

Console.WriteLine("Creating generic column constraints");
for (int c = 0; c < 9; ++c)
{
  for (int first = 0; first < 8; ++first)
    for (int second = first + 1; second < 9; ++second)
      model.AddConstraint("colConstraint" + c + first + second,
        grid[first][c] != grid[second][c]);
}

Because an entire column cannot be accessed directly, the demo works on each column separately. For column 0, the first time through the two inner nested loops sets the constraint named “colConstraint001” as grid[0][0] != grid[1][0]. The second iteration sets “colConstraint002” as grid[0][0] != grid[2][0]. To summarize, the AllDifferent method accepts a set of Decision objects as an array and behind the scenes generates explicit inequalities. In situations where your Decision objects aren’t in an array (as in the column values), you must explicitly generate the inequalities.

By far the trickiest part of the demo program is setting up the constraints that specify all the values in each of the nine 3x3 sub-cubes must be different. That code is presented in Figure 4. Bear with me—the code isn’t nearly as complex as it appears.

Figure 4 Setting up the Sub-Cube Constraints

Console.WriteLine("Creating generic sub-cube constraints");
for (int r = 0; r < 9; r += 3) {
  for (int c = 0; c < 9; c += 3) {
    for (int a = r; a < r + 3; ++a) {
      for (int b = c; b < c + 3; ++b) {
        for (int x = r; x < r + 3; ++x) {
          for (int y = c; y < c + 3; ++y) {
            if ((x == a && y > b) || (x > a))
            {
              model.AddConstraint("cubeConstraint" + a + b + x + y,
                grid[a][b] != grid[x][y]);
            }
          } // y
        } // x
      } // b
    } // a
  } // c
} // r

Consider the sub-cube in the lower-left corner of Figure 3. The necessary constraints for this sub-cube are:

grid[6][0] != grid[6][1]
grid[6][0] != grid[6][2]
grid[6][0] != grid[7][0]
...
grid[8][1] != grid[8][2]

There are 8 + 7 + 6 + … + 1 = 36 constraints for this sub-cube, and so there are 9 * 36 = 324 total inequalities for the nine sub-cube constraints. Now, it would be possible to list each one using copy-paste and some patience, but a programmatic approach is quicker.

In the code, the two outer loops establish an upper-left corner of each sub-cube. In the four innermost loops, cells are represented as grid[a][b] != grid[x][y]. If you look just at the indices in the example and image, which are just ordinary integers, you get:

60 and 61
60 and 62
...
81 and 82

Notice that in each case, there is an inequality constraint when ab < xy. The innermost four loops iterate over a, b, x, and y to generate all possible pairs of indices and the if-then condition creates a constraint on grid[a][b] and grid[x][y] only when ab < xy.

Adding Problem-Specific Constraints

After the generic constraints have been created and added to the model, the demo program adds the constraints that define the specific Sudoku puzzle. The demo puzzle has 27 fixed values, so you could use brute force, like so:

model.AddConstraint("v02", grid[0][2] == 6);
model.AddConstraint("v03", grid[0][3] == 2);
...
model.AddConstraint("v86", grid[8][6] == 2);

There’s nothing wrong with a brute force approach, but because the data already has been placed into a matrix, it’s easy to transfer the values using a program-defined helper method call like this:

AddDataConstraints(data, model, grid);
where the helper is defined as:
static void AddDataConstraints(int[][] data, Model model, 
  Decision[][] grid)
{
  for (int r = 0; r < 9; ++r) {
    for (int c = 0; c < 9; ++c) {
      if (data[r][c] != 0) {
        model.AddConstraint("v" + r + c,
          grid[r][c] == data[r][c]);
      }
    }
  }
}

Notice the strange coupling between the Model and Decision objects. Library code written by developers for developers would likely have referenced the Decision (answer) objects along the lines of model.grid[r][c]. The unusual style of the MSF library took me about three examples to get comfortable with it.

Solving the Puzzle

With everything in place, the demo program can solve the puzzle with this code:

Console.WriteLine("Solving. . . ");
int numSolutions = NumberSolutions(problem);
Console.WriteLine("There is/are " + 
  numSolutions + " Solution(s)");
Solution solution = problem.Solve();

The NumberSolutions method is a program-defined helper that’s called to check if there are zero solutions (which means conflicting constraints were somehow defined) or more than one solution:

static int NumberSolutions(SolverContext problem)
{
  int ct = 0;
  Solution soln = problem.Solve();
  while (soln.Quality == SolverQuality.Feasible) {
    ++ct;
    soln.GetNext();
  }
  return ct;
}

The MSF Solve method does just that, placing the actual answers into the Decision objects, which are in the Model object, which is associated by reference to the SolverContext object. As a side effect, the Solution object has a Quality field that can be one of eight values, including Feasible and Infeasible. The Solution GetNext method doesn’t return an explicit value but does modify the Quality field. Don’t blame me for the MSF design.

The Sudoku demo concludes by displaying the answers stored in the Decision objects inside the grid matrix:

for (int r = 0; r < 9; ++r) {
    for (int c = 0; c < 9; ++c) {
      double v = grid[r][c].GetDouble();
      Console.Write(" " + v);
    }
    Console.WriteLine("");
  }
  Console.WriteLine("End Solver Foundation Sudoku demo");
  Console.ReadLine();
} // Main

The GetDouble method extracts the answer value from the Decision object. Recall that answers were defined to be integers in the range 1 to 9. However, there’s no GetInteger method so answer values are implicitly cast to type double. Because they all end with point-zero, when displayed they appear as integers even though they are type double.

Wrapping Up

The particular type of CSP described in this article is really a combinatorial optimization problem. That is, the goal is to find the combination of values that has the fewest constraint errors. The information presented here should allow you to use the MSF library to solve many practical combinatorial optimization problems you might come across.

I have a confession. My sister’s boyfriend introduced me to Sudoku on a family trip to Palm Springs a few years ago. He consistently beats me whenever we compete for time on Sudoku or crossword puzzles or anything else. He doesn’t know it’s possible to solve any Sudoku puzzle with this code. I’m looking forward to our next family trip. I’ll have my laptop.

Dr. James McCaffrey works for Microsoft Research in Redmond, Wash. He has worked on several Microsoft products including Internet Explorer and Bing. Reach him at jammc@microsoft.com.

Thanks to the following technical expert for reviewing this article: Kirk Olynyk (Microsoft Research)