Sudoku using Microsoft Solver Foundation

• Download source - 315.5 KB

Introduction

The following is an example of how Microsoft Solver Foundation can be used to solve a constraint satisfaction problem (CSP) like generating a typical Sudoku problem.

In this article, I do not attempt to explain everything there is to know about constraint satisfaction problems, but I will go over the concepts, in the hope that even if you have never heard of CSP, you will still get the idea.

A Little About Sudoku

Although the game is pretty simple, there are a few variations. In this example we only generate a Sudoku, but the same principles can be used to solve a Sudoku. Whether we generate or solve a Sudoku, we have the same amount of constraints and pretty much the same objective. In this example, we stick to the following game rules:

1. Each row contains each digit* exactly once.
2. Each column contains each digit exactly once.
3. Each region** contains each digit exactly once.

After generating a Sudoku, we need to hide some of the values so that the player has something to do. We will refer to the digits that we show to the user as hints and we will choose these randomly at first.

* We will use digit 1 to 9.
** Regions are the sub-squares (3x3) in our grid.

Constraint Satisfaction Problem

A CSP is just a specific way to describe a problem. In order to get a problem into a CSP format, the following needs to be identified:

1. A set of variables.
2. The domain for each variable. In other words, possible values for each variable.
3. A set of constraints. The constraints will specify allowable combinations of values.

When all of the variables have values and we met all the constraints, the problem is solved. Not all problems lend themselves to this, but one of the best examples of a problem that do, is the problem of colouring a map were we can't colour 2 adjacent parts with the same colour.

In the example of colouring Australia, the variables will be Queensland, South Australia, Western Australia and so on.

The domain, the colours.

And our constraints will be that Queensland's colour should differ from South Australia, South Australia's colour should differ from Western Australia and so on.

Sudoku as a Constraint Satisfaction Problem

Let's get started on our problem, generating a Sudoku.

• Variables: We will have 81 variables, one for each square in our grid.
• Domains: We have chosen to use digits 1 to 9.
• Constraints: From our rules, we get the following constraints: Each row should contain each digit exactly once. Each column contains each digit exactly once and each region contains each digit exactly once.

The Requirements

So this is more or less what we want our application to do:

1. Generate a puzzle and use a 9x9 grid to display the puzzle.
2. Hide values, so that the player can fill them in.
3. Check to see if the generated problem has a unique solution, if not, warn the player.
4. Validate the player’s moves.
5. Congratulate the player on completion.

The Design

Since we have the concept of rows, columns and regions, I added these all into a Grid class. The Grid class will make our lives easier by providing us with getters for rows, columns and regions, each returning the values as a List of integers.

The SudokuProblem class will have to come up with the solution and also do the validation after each move.

When working with a problem like Sudoku, one often needs to generate random numbers, but not only random numbers but unique random numbers. I added a Utils class which has a method GetUniqueRandomNumbers().

Like we said earlier, we have a CSP with 81 variables. When using solver foundation, this gets wrapped in a class called Decision. This made me think that we need a DecisionFactory. This helped a lot with keeping the SudokuProblem class clean.

The Code

In order to use Microsoft solver foundation, one needs to include it as a reference and include it in the classes using it. I got the express edition from http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx

To generate a Soduko, this is all we need:

Code snippet #1 from SudokuProblem.cs

1   SolverContext context = SolverContext.GetContext();
2   Model model = context.CreateModel();
3   // See code snippet #2 for BuildDecisions
4   List<Decision> decisionList=DecisionFactory.BuildDecisions(Grid.GetAllSquares());
5   model.AddDecisions(decisionList.ToArray());
6
7   for (int j = 0; j < 9; j++)
8   {
9       model.AddConstraints("constraint_" + j,
10            Model.AllDifferent(getDecision(decisionList, Grid.GetRow(j))),
11            Model.AllDifferent(getDecision(decisionList, Grid.GetColumn(j))),
12            Model.AllDifferent(getDecision(decisionList, Grid.GetRegion(j)))
13      );
14  }
15
16  List<int> seedValues = Utils.GetUniqueRandomNumbers(1, 10, 9);
17  for (int i = 0; i < 9; i++)
18  {
19               model.AddConstraints("seed_" + i.ToString(),decisionList[i] == seedValues[i]);
20  }
21  context.Solve(new ConstraintProgrammingDirective());
22  solution = ConvertDecicionsToIntegers(decisionList);  

We start by adding a new model to our context (lines 1-2 snippet #1). We will use the model to define our CSP.

We said earlier that we will need 81 variables, one for each square in our puzzle. With the help of our Grid, we get all 81 squares. For each of these, we build a Decision. (Although the documentation wasn't that helpful to me, I am still going to add some reference to it.) A Decision is a variable with its domain. Here is how we create a Decision with the Domain of integers which range from 1 to 9 (line 13 snippet #2).

Code snippet #2 from DecisionFactory.cs

1  private static Domain domain = Domain.IntegerRange(1, 9);
2  public static List<Decision> BuildDecisions(List<int> squares)
3  {
4      if (squares == null || squares.Count == 0)
5      {
6           return new List<Decision>();
7      }
8
9      Decisions.Clear();
10
11     foreach (int i in squares)
12     {
13          Decisions.Add(new Decision(domain, Constants.StringAffix + i));
14     }
15     return Decisions;
16 }

We need to add all the 81 Decisions to the model. This gets done on line 5 of snippet #1.

Now we are ready to add constraints. We get our first 9 constraints from the first game rule stating that in each row, each digit can occur only once. This means that we should have 9 unique values in each row. The easiest way to get to this, is to use the AllDifferent function and feed it all the values from each row (line 10 snippet #1), our Grid makes this easy to do. We then also do the same for our columns and regions (line 11-12 snippet #1).

To ensure that we get a different Sudoku problem each time, I have added 9 seeds. The seeds are just nine unique random numbers which I use for the first row. I have chosen to add them as constraints (line 16-20 snippet #1).

In line 21 of snippet #1, the CSP gets solved and each of our decision will have a value.

In line 22 of snippet #1 we just convert this back to a list of integers. The list of integers gets passed to the gird where it gets displayed.

Code snippet #3 from SudokuProblem.cs

1    public static bool HasUniqueSolution()
2    {
3        SolverContext context = SolverContext.GetContext();
4    context.ClearModel();
5    Model model = context.CreateModel();
6
7    List<decision> decisionList = DecisionFactory.BuildDecisions(Grid.GetAllSquares());
8    model.AddDecisions(decisionList.ToArray());
9
10    // Add 27 constraints to model
11    for (int j = 0; j < 9; j++)
12    {
13        model.AddConstraints("constraint_" + j,      
14               Model.AllDifferent(getDecision(decisionList, Grid.GetRow(j))),
15               Model.AllDifferent(getDecision(decisionList, Grid.GetColumn(j))),
16            Model.AllDifferent(getDecision(decisionList, Grid.GetRegion(j)))
17        );
18    }
19    // Add all hints as constraints
20    for (int i = 0; i < problem.Count; i++)
21    {
22        if (problem[i] != 0)
23        {
24            // This is a hint
25        model.AddConstraints("hint_" + i.ToString(), decisionList[i] == problem[i]);
26           }
27    }
28
29    List<decisionbinding> decisionBindings = new List<decisionbinding>();
30    for (int i = 0; i < problem.Count; i++)
31    {
32        if (problem[i] == 0) // This is hidden square
33        {
34        DecisionBinding binding = decisionList[i].CreateBinding();
35        decisionBindings.Add(binding);
36        }
37    }
38    context.FindAllowedValues(decisionBindings);
39    foreach (DecisionBinding decisionBinding in decisionBindings)
40    {
41        if (decisionBinding.Int32FeasibleValues.ToList().Count > 1)
42        {
43        return false;
44        }
45    }
46    return true;
47    }

We now need to determine if the problem the user will be presented with is a real Sudoku, in other words if the problem has only one solution.

I added another method to the SudokuProblem class, HasUniqueSolution() that can be seen in snippet #3.

Determining if the problem is a real Sudoku, is yet another CSP. To keep it simple we will use 81 decisions, but instead of only the initial 27 constraints, we now also have each of the hints as a constraint.

We will again create a model, add decisions and constraints but instead of solving the problem, we will call FindAllowedValues for the hidden squares (line 38 snippet #3).

On line 29 – 37 of snippet #3, I create a list of decision bindings for the hidden squares. These gets passed to FindAllowedValues() “An allowed value is one that is part of some feasible solution to the problem. ”

Here is an example of what a decision binding might look like after line 38.

We are really only interested in the amount of feasible values of each. When we have more than one feasible value, it means that there is more than one possible solution.