Using Solver Foundation to generate Sudoku puzzles, Part II

In our last post, we saw the model for completing a Sudoku board given a particular board configuration. In this post, we will show how to repeatedly use this model to generate a Sudoku puzzle.

Let us first take a look at the main procedure of the puzzle generation.

 Public Function GeneratePuzzle() As SudokuBoardCell(,)   Dim context As SolverContext = SolverContext.GetContext()   Dim model As Model   Dim solution As Solution     _board = GenerateRandomStartingPoint(3)   model = CreateModel(context)   solution = context.Solve()     If solution.Quality <> SolverQuality.Feasible Then     Return Nothing   End If     PopulateSolution(solution, context)     Dim candidates As List(Of Integer) = New List(Of Integer)   For i = 0 To 80     candidates.Add(i)   Next     Dim rand As New Random()     While candidates.Count > 0     Dim pos As Integer = rand.Next(0, candidates.Count)     Dim coordX As Integer = candidates(pos) \ 9     Dim coordY As Integer = candidates(pos) Mod 9     candidates.RemoveAt(pos)     If IsRemovable(context, coordX, coordY) Then       _board(coordX, coordY) = New _         SudokuBoardCell(coordX, coordY, 0, _                         _board(coordX, coordY).SolutionValue)     End If   End While     Return _board End Function

We start by randomly generating a board configuration that contains only four preset values and computing a solution from that initial board configuration.

 _board = GenerateRandomStartingPoint(3)   model = CreateModel(context)   solution = context.Solve()

Note that in CreateModel, we will use the preset numbers stored in _board via data binding. We skip the error handling case. In reality, given that we only preset three numbers, it is highly unlikely that we get an infeasible initial configuration (meaning that the initial configuration cannot be extended to a complete configuration while satisfying all Sudoku constraints).

Once the model is solved and we get a feasible solution, we can populate the values of aggregated decision variables back to _board (using Property SolutionValueDouble defined in SudokuBoardCell). This is done via the output data binding we specified in the model when we created decision _boardDec. We then use the computed solution as the starting point to generate the actual puzzle. To this end, we create a candidate list of integers that initially contains all the board cells.

 PopulateSolution(solution, context)     Dim candidates As List(Of Integer) = New List(Of Integer)   For i = 0 To 80     candidates.Add(i)   Next

Next, we will start removing numbers from the complete board configuration one by one. Remember that we will actually remove a number if and only if, after it is removed, the board configuration has exactly one way to be completed (a.k.a. exactly one feasible solution can be found after the number is removed).

In the while loop, we randomly pick a cell position from the candidate list. Then we use method IsRemovable to test if the number in that position can be removed according to the condition we just mentioned above. If so, we will put 0 in that cell as the PresetValue. Note that we still keep its original value from the solution for the checking purpose later (verifying if user fills in a correct number in this position).

 While candidates.Count > 0     Dim pos As Integer = rand.Next(0, candidates.Count)     Dim coordX As Integer = candidates(pos) \ 9     Dim coordY As Integer = candidates(pos) Mod 9     candidates.RemoveAt(pos)     If IsRemovable(context, coordX, coordY) Then       _board(coordX, coordY) = New _         SudokuBoardCell(coordX, coordY, 0, _                         _board(coordX, coordY).SolutionValue)     End If   End While

The three major sub-routines involved are GenerateRandomStartingPoint, PopulateSolution, and IsRemovable. We will now show them one by one.

 Private Function GenerateRandomStartingPoint(ByVal numPrefill _   As Integer) As SudokuBoardCell(,)   Dim rand As New Random()   Dim coordX As Integer   Dim coordY As Integer     For i = 0 To 8     For j = 0 To 8       _board(i, j) = New SudokuBoardCell(i, j)     Next   Next     Dim values(9) As Integer     If numPrefill > 8 Then     numPrefill = 8   End If     For i = 0 To numPrefill     For repeat = 0 To 5       coordX = rand.Next(0, 9)       coordY = rand.Next(0, 9)       If board(coordX, coordY).PresetValue = 0 Then         Dim k = rand.Next(1, 10)         Do While values(k) <> 0           k = k + 1           If k = 10 Then             k = 1           End If         Loop         values(k) = 1         _board(coordX, coordY) = New _           SudokuBoardCell(coordX, coordY, k)         Exit For       End If     Next   Next     Return _board End Function

This procedure is straight-forward. We note that we do not use repeated values to avoid obvious conflict in generating the initial board configuration. This means the largest possible value of the input parameter is 8. Another place to note is that, even if the initial starting points are different, we may still end up with the same complete board configuration after the model is solved. We will not worry about this case in this sample though.

PopulateSolution procedure is defined as follows.

 Private Sub PopulateSolution(ByRef sol As Solution, _                              ByRef context As SolverContext)   If sol.Quality = SolverQuality.Feasible Then     context.PropagateDecisions()       For i = 0 To 8       For j = 0 To 8         Board(i, j).PresetValue = Board(i, j).SolutionValue       Next     Next   End If End Sub

We only perform this operation if the solution found is feasible. As we mentioned earlier, we set all cells’ PresetValue to their SolutionValue (rounded version of SolutionValueDouble).

Finally, IsRemovable method is defined as follows.

 Private Function IsRemovable(ByRef context _   As SolverContext, ByVal coordX As Integer, _   ByVal coordY As Integer) As Boolean   Dim value As Integer = _board(coordX, coordY).PresetValue   _board(coordX, coordY) = New SudokuBoardCell( _     coordX, coordY, 0, _     _board(coordX, coordY).SolutionValue)     Dim solution As Solution = context.Solve()   solution.GetNext()     Dim removable As Boolean = (solution.Quality = _     SolverQuality.Infeasible)     If Not removable Then Board(coordX, coordY) = New _   SudokuBoardCell(coordX, coordY, value, value)   End If     Return removable End Function

We first record the original PresetValue in the cell (coordX, coordY). Then we change its PresetValue to 0. Next we call context.Solve() and solution.GetNext() . The call to context.Solve() should always return a feasible solution as we started from a valid complete board configuration. The call to solution.GetNext() tries to compute a second feasible solution. If there is no other feasible solution, SFS will set the Quality of the Solution instance to Infeasible. So we will decide if the PresetValue of the cell should be set to 0 based on solution.Quality.

That’s all we need to generate a random Sudoku puzzle. Pretty easy, isn’t it? It’s worth pointing out that, IsRemovable method is called repeatedly in the main loop. Each time it is called, we need to solve the Sudoku model with a different preset board configuration. By using Solver Foundation Services and its data binding feature, we actually have separated the model from its input data, in this case the preset board configuration. So every time we want to solve the Sudoku model with a different preset board configuration, we do not need to reconstruct the model. The only thing we need to do is to change the data source to which the Parameter instances are bound to in the model. In this example, we only need to change PresetValue (the property to which the Parameter instance is bound to) of the given cell. In other words, the model is generic to all preset board configurations. The separation of model from data is really convenient in such scenarios where the model remains the same while the input data change from time to time.

In the next and the final post, we will briefly show how to build a new Ribbon tab in Excel for this add-in and how to trigger the Sudoku puzzle generation.

- Lengning Liu

1. Using Solver Foundation to generate Sudoku puzzles, Part II | Tmao Coders says: