Freigeben über

Using Solver Foundation to generate Sudoku puzzles, Part II

  • Artikel

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

Comments