Using Solver Foundation to generate Sudoku puzzles, Part I
I will be posting a series of articles that illustrate how to use the recently released Microsoft Solver Foundation to solve various problems. Let us start with this fun problem: generating Sudoku puzzles. We will see how to model the problem in Solver Foundation and how to drive the creation of Sudoku puzzles from Excel spreadsheet via Excel plug-in. The sample is written in VB.NET. It will be relatively straightforward to translate the code into C#. The code here is for educational purposes only. To successfully compile this sample code, one needs Visual Studio 2008 with VSTO installed.
For those who are not familiar with Sudoku puzzles, please see the wikipedia page (enhanced by Powerset.com) for the definition and history. In this sample, we will focus on the classic 9x9 puzzle. Interestingly, there has been a post that shows how to use solver foundation to solve the puzzle.
Let's start with the OML model contributed by Erwin Kalvelagen:
Model[
Parameters[Sets,I,J], Parameters[Integers,d[I,J]],
Decisions[Integers[1,9],x[I,J]],
Constraints[ FilteredForeach[{i,I},{j,J},d[i,j]>0,x[i,j]==d[i,j]], Foreach[{i,I},Unequal[Foreach[{j,J},x[i,j]]]], Foreach[{j,J},Unequal[Foreach[{i,I},x[i,j]]]], Foreach[{ib,3}, Foreach[{jb,3}, Unequal[Foreach[{i,ib*3,ib*3+3},{j,jb*3,jb*3+3},x[i,j]]] ] ] ] ] |
The parameter d[I,J] was bound to the Sudoku puzzle in the Excel spreadsheet and we skip its definition here.
To generate Sudoku puzzles, we will be using this model repeatedly in the following fashion [1].
1. We randomly fill in the empty board with a small number of values to get a random starting board configuration;
2. Then we solve the model with the generated starting board configuration and retrieve the first solution, which corresponds to a board configuration that has all cells filled in and all Sudoku rules are satisfied;
3. We repeatedly try to remove numbers one by one from the solution board configuration computed in step 2. If after removing one number, we solve the model and only get one solution, we will actually remove that number; otherwise, we keep that number.
4. Stop until we have tried to remove all the numbers.
After that, we will get a board configuration with certain number of numbers left. Because of step 3, we are guaranteed that there is exactly one solution to the board configuration.
In this sample, we are going to use Excel as the gaming interface (see the Sudoku.gif attachment below). We create a new Ribbon tab called Sudoku that has three buttons. Generate button will generate a new puzzle. Check button will check if the solution filled by the user is correct. We will explain the “Fill In Zeros” button later.
The three Ribbon buttons are routed to a new Excel add-in that we will create. We will use VB.NET with VSTO to build this add-in. To this end, we need to convert the OML model into a programmatic model in VB.NET. We will use Solver Foundation Services (or SFS for short) to build this programmatic model. Since Solver Foundation is CLS compliant, it is straight-forward to access Solver Foundation functionalities directly in any .NET languages such as VB.NET. We will also illustrate how to use the data binding feature in SFS with the support of LINQ.
Let us first define a helper class that represents each cell on the Sudoku board. We omit the implementation of the methods here to save space. The complete code will be available for download after this sample is finished.
Public Class SudokuBoardCell Private _row As Integer Private _col As Integer Private _presetVal As Integer Private _solutionVal As Integer Public Property Row() As Integer Public Property Col() As Integer Public Property PresetValue() As Integer Public Property SolutionValueDouble() As Double Public Property SolutionValue() As Integer Public Sub New(ByVal r As Integer, ByVal c As Integer) Public Sub New(ByVal r As Integer, ByVal c As Integer, _ ByVal presetVal As Integer) Public Sub New(ByVal r As Integer, ByVal c As Integer, _ ByVal presetVal As Integer, _ ByVal solutionVal As Integer) End Class |
Then the actual board will be represented by a two-dimensional array of SudokuBoardCells.
Private _board(8, 8) As SudokuBoardCell |
We have also defined a class member called _boardDec, which is the only decision variable we will use in the model. We will explain why there is only one decision variable needed in the SFS model shortly.
Private _boardDec As Decision |
In SFS, modeling starts with getting a solver context and creating a model. The following code all belong to CreateModel method. We define the following method for model creation, where context is passed in as a parameter.
Private Function CreateModel(ByRef context As SolverContext) As Model |
We create a new model in the given solver context.
context.ClearModel() Dim model As Model = context.CreateModel() |
In an SFS model, a single decision variable can represent an aggregation of variables in solver’s point of view. In this sample, we have only one SFS decision. However, we will see that it actually represents 81 solver level decision variables. The benefit of having this aggregation is that, we can write very compact algebraic model in SFS that looks almost the same as its OML version.
We now define the index sets that later will be used along with the decision to construct constraints. These two sets correspond to the sets I, J defined in the OML model.
Dim row As Microsoft.SolverFoundation.Services.Set = New _ Microsoft.SolverFoundation.Services.Set(Domain.Any, "row") Dim col As Microsoft.SolverFoundation.Services.Set = New _ Microsoft.SolverFoundation.Services.Set(Domain.Any, "col") |
Now we can create the actual decision _boardDec.
'Create decisions _boardDec = New Decision(Domain.IntegerRange(1, 9), _ "board", row, col) _boardDec.SetBinding(Of SudokuBoardCell)( _ ToEnumerable(_board), _ "SolutionValueDouble", "Row", "Col") model.AddDecision(_boardDec) |
In creating the decision, we specify that _boardDec is actually an aggregation of a two-dimensional decision array, which is indexed by the two set variables row and col.
Then we set up the binding from the aggregated decision _boardDec to the actual object _board that represents the board. The three strings in SetBinding call correspond to the three properties defined in SudokuBoardCell. The first property “SolutionValueDouble” will be used after a solution is found and a request of propagating the value assignment back via out-binding is issued. The next two properties form the key to uniquely identify a board cell.
Next, we will create a parameter instance that will be used in creating the constraints (similar to the parameters d[I,J] in the OML model).
'Create parameter Dim presetBoard As Parameter = New _ Parameter(Domain.IntegerRange(0, 9), _ "presetBoard", row, col) presetBoard.SetBinding(Of SudokuBoardCell) _ (ToEnumerable(_board), "PresetValue", _ "Row", "Col") model.AddParameter(presetBoard) |
Parameter construction is similar to decision construction. In the constructor, row and col are the two sets we defined earlier. It indicates that parameter presetBoard is also an aggregation of a two-dimensional parameter array. The binding part is also similar. The only difference is that, parameter binds to property “PresetValue” instead of “SolutionValueDouble”. From property PresetValue, the values that have been preset on the board will be read in and used in constraints. Our class member _board actually works for two purposes: both for input and for output, using different properties of SudokuBoardCell.
Now we can create constraints. The first constraint says all decisions in cell (i,j) must be equal to the preset values. We will utilize ForEachWhere operator to do it.
'FilteredForeach[{i, 9}, {j, 9}, board[i,j] > 0, boardDec[i, j] == 'board[i, j]] model.AddConstraint(Nothing, _ model.ForEach(row, Function(i) _ (model.ForEachWhere(col, _ Function(j) _ (_boardDec(i, j) = _ presetBoard(i, j)), _ Function(j) _ (presetBoard(i, j) > 0))))) |
ForEach and ForEachWhere are two operators in SFS that iterate through a set of indexes. Note that the constraints and conditions are enclosed in lambda functions. In ForEachWhere, the condition clause is specified by presetBoard(i, j) > 0. These expressions will not be evaluated or reduced at this moment. SFS will evaluate these expressions when the model gets instantiated.
The following two constraints ensure that each row and columns has number 1-9 exactly once.
'Foreach[{i, 9}, Unequal[Foreach{j, 9}, boardDec[i, j]]] model.AddConstraint(Nothing, _ model.ForEach(row, Function(i) _ (model.AllDifferent(model.ForEach(col, _ Function(j) (_boardDec(i, j))))))) 'Foreach[{j, 9}, Unequal[Foreach{i, 9}, boardDec[i, j]]] model.AddConstraint(Nothing, _ model.ForEach(col, Function(j) _ (model.AllDifferent(model.ForEach(row, _ Function(i) (_boardDec(i, j))))))) |
These constraints are constructed in almost the same was as we built them in OML.
Finally the last group of constraints is a little bit complex. They ensure that in each of the nine blocks, numbers 1-9 appear exactly once.
'Foreach[{blocki, 3}, ' Foreach[{blockj, 3}, ' Unequal[Foreach[{i, blocki*3, blocki*3+3}, ' {j, blockj*3, blockj*3+3}, boardDec[i,j]]] ' ] '] For i = 0 To 2 For j = 0 To 2 Dim blocki As Integer = i Dim blockj As Integer = j Dim boardBlock As Parameter = New _ Parameter(Domain.IntegerNonnegative, _ "boardBlock", row, col) model.AddParameters(boardBlock) boardBlock.SetBinding( _ (From block As SudokuBoardCell _ In ToEnumerable(_board) _ Select New With _ {.KeyRow = block.Row, _ .KeyCol = block.Col, _ .IsIn = IsInBlock(blocki, blockj, _ block.Row, block.Col)}), _ "IsIn", "KeyRow", "KeyCol") model.AddConstraint(Nothing, _ model.AllDifferent( _ model.ForEach(row, Function(keyi) _ (model.ForEachWhere(col, _ Function(keyj) _ (_boardDec(keyi, keyj)), _ Function(keyj) _ (boardBlock(keyi, keyj) = 1)))))) Next Next |
Note that we create dynamically a parameter for each of the nine blocks called boardBlock. With the flexible LINQ syntax, we could express in each of these parameters that, boardBlock(keyi, keyj) is 1 if and only if cell (keyi, keyj) belongs to the current block, denoted by (blocki, blockj). The helper method IsInBlock used in the LINQ expression establishes this relationship. Then constructing the constraint, we use ForEachWhere and boardBlock(keyi, keyj) = 1 becomes the condition clause.
To finish the modeling part of the sample, we have the following two helper methods.
Private Function IsInBlock(ByVal blocki As Integer, _ ByVal blockj As Integer, _ ByVal row As Integer, _ ByVal col As Integer) As Integer If blocki * 3 <= row And row <= blocki * 3 + 2 And _ blockj * 3 <= col And col <= blockj * 3 + 2 Then Return 1 Else Return 0 End If End Function Private Function ToEnumerable(ByRef board(,) _ As SudokuBoardCell) _ As IEnumerable(Of SudokuBoardCell) If (_boardAsEnumerable Is Nothing) Then _boardAsEnumerable = _board.Cast(Of SudokuBoardCell)() End If Return _boardAsEnumerable End Function |
The use of IsInBlock has been discussed earlier. ToEnumerable converts a two-dimensional array into an IEnumerable, which is the required type for the first parameter in SetBinding method.
This is the modeling part of this sample. In the next post, we will illustrate briefly how to integrate the model we have just written into an Excel Add-in. So please stay tuned.
- Lengning Liu
Reference:
[1] "So, you want to generate your own Sudoku?" by Raphael Finkel, Victor Marek, Mirek Truszczynski. https://www.cs.uky.edu/~marek/suresource.dir/supaper.pdf
Comments
- Anonymous
November 15, 2008
This post is just a roundup of some links for those of you looking for more information about Microsoft