12,826,142 members (31,406 online)
Add your own
alternative version

#### Stats

55K views
2K downloads
109 bookmarked
Posted 28 Jul 2012

# Sudoku using Microsoft Solver Foundation

, 26 May 2014 CPOL
 Rate this:
Please Sign up or sign in to vote.
An example of how to use Microsoft Solver Foundation on a constraint satisfaction problem.

## 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 `Decision`s 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.

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## About the Author

 Symplexity South Africa
No Biography provided

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 First Prev Next
 My vote of 5! Daniel Dhillon5-Jun-14 9:04 Daniel Dhillon 5-Jun-14 9:04
 Very good article! Volynsky Alex26-May-14 9:41 Volynsky Alex 26-May-14 9:41
 How and why to use Microsoft solver foundation for .net unicorn230-Apr-13 2:46 unicorn2 30-Apr-13 2:46
 Re: How and why to use Microsoft solver foundation for .net Southmountain16-Jul-13 7:36 Southmountain 16-Jul-13 7:36
 MS Solver Foundation with Java? Member 1001859429-Apr-13 15:03 Member 10018594 29-Apr-13 15:03
 Re: MS Solver Foundation with Java? unicorn230-Apr-13 0:07 unicorn2 30-Apr-13 0:07
 Re: MS Solver Foundation with Java? Member 1001859430-Apr-13 4:49 Member 10018594 30-Apr-13 4:49
 Re: MS Solver Foundation with Java? unicorn230-Apr-13 5:13 unicorn2 30-Apr-13 5:13
 Re: MS Solver Foundation with Java? Member 1001859430-Apr-13 5:20 Member 10018594 30-Apr-13 5:20
 My vote of 5 srinivaskumar pasumarthi29-Apr-13 4:05 srinivaskumar pasumarthi 29-Apr-13 4:05
 My vote of 5 fredatcodeproject16-Apr-13 2:46 fredatcodeproject 16-Apr-13 2:46
 :-) krysiaaa15-Feb-13 6:38 krysiaaa 15-Feb-13 6:38
 My vote of 5 VitorHugoGarcia16-Jan-13 7:25 VitorHugoGarcia 16-Jan-13 7:25
 My vote of 5 fredatcodeproject15-Oct-12 6:51 fredatcodeproject 15-Oct-12 6:51
 Cool Slacker00710-Oct-12 4:38 Slacker007 10-Oct-12 4:38
 Needs work... Dave Kreskowiak10-Oct-12 2:55 Dave Kreskowiak 10-Oct-12 2:55
 Re: Needs work... unicorn216-Jan-13 20:42 unicorn2 16-Jan-13 20:42
 My vote of 5 baemayr30-Jul-12 8:57 baemayr 30-Jul-12 8:57
 Good - but this is not the complete puzzle? Adam Clauss29-Jul-12 6:09 Adam Clauss 29-Jul-12 6:09
 Re: Good - but this is not the complete puzzle? unicorn229-Jul-12 6:21 unicorn2 29-Jul-12 6:21
 Thanks for the reply. I think what you are referring to, is sometimes referred to as a 'real' Sudoku. This can be achieved, with a bit more effort. Maybe I should add this in the next revision.
 Re: Good - but this is not the complete puzzle? Member 902822514-Feb-13 4:47 Member 9028225 14-Feb-13 4:47
 Re: Good - but this is not the complete puzzle? yloginov18-Sep-13 10:50 yloginov 18-Sep-13 10:50
 Re: Good - but this is not the complete puzzle? unicorn223-Sep-13 1:30 unicorn2 23-Sep-13 1:30
 Last Visit: 31-Dec-99 19:00     Last Update: 28-Mar-17 11:30 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170326.1 | Last Updated 26 May 2014
Article Copyright 2012 by Atalia Beukes
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid