Sudoku Puzzle
- an Exercise in Constraint Programming and Visual Prolog 7

Abstract

A currently very popular logical Sudoku puzzle is used as an example. We show how such a problem can be solved using constraint programming and explain a simple approach to finite domains constraint solving. Furthermore, we show how to build an interactive GUI that visualizes the workings of the constraint solver.
The exercise was presented at Visual Prolog Applications & Language Conference (VIP-APL'06).

The example project described below is included into Visual Prolog distribution. If you do not have Visual Prolog, you are welcome to buy Visual Prolog Commercial Edition or download Visual Prolog Personal Edition.

Introduction

A Sudoku consists of a 9 by 9 grid which have to be filled with the numbers 1 to 9 such that each number is used exactly once in each row, column and 3 by 3 group. Initially a Sudoku has numbers in some of the fields such that there is exactly one solution to the Sudoku.

    1 7       8  
7 5   9       4  
                3
8   5   9   1    
  4           5  
    7   5   2   4
5                
  1       5   6 2
  2       3 5    

Depending on the initial configuration of the Sudoku they can be graded as easy to difficult or tofu to sumo.

A Constraint Formulation

We have 81 constraint variables over the domain 1..9 and 27 constraints one for each row, column, and group saying that the fields are a permutation of the numbers from 1 to 9.

Fi,j : 1..9                  i,j = 1..9
permutation(Rowi)       i = 1..9
permutation(Columni)  i = 1..9
permutation(Groupi)    i = 1..9

One can chose different formulations; instead of

permutation(F1,..,F9) 

one could have

notEqual(Fi,Fj) for i,j = 1..9 and i ≠ j.

This would give a total of 1944 simpler constraints or discarding symmetries 972 constraints.

Simple Constraint Solving

A constraint variable is an object which contains the set of possible values and a constrain method which restricts the possible values.

F:getValues() = [2,4,8,9],
F:constrain([3,8,9]),
F:getValues() = [8,9]

constrain is determ and should fail if the set of possible values becomes empty; the variable is over constrained.

A constraint is an object with a propagate method that constrain the variables in the constraint. E.g., notEqual will look like:

implement notEqual

facts
    x : variable.
    y : variable.

clauses
     new(X,Y):- x := X, y := Y.

clauses
    propagate():-
        y:constrain(complement(x:getValues())),
        x:constrain(complement(y:getValues())).

clauses
     complement([X]) = [Y || Y = fromto(1,9), not(Y = X)].
     complement(_) = [1,2,3,4,5,6,7,8,9].

end implement

This example illustrates a new vip7 feature list comprehensions:

[ exp || body ] <=> findAll(exp, body)

Here it just implements diff([1..9],X).

propagate is determ and fails if one of the variables becomes over constrained.

It is clear that this constraint is rather weak as it only propagate constrains when one of the ingoing variables are grounded (have only one possible value).

Constraint Propagation

We say a constraint net (set of variables and constraint over these variables) is arc-consistent if all the constraints are satisfied, i.e., none of the constraints will constrain variables further.

Example:
Two variables x, y over the domain {1,2} and one constrain notEqual(x,y).

x = {1,2}, y = {1,2} is arc-consistent.

x = {1}, y = {1,2} is not arc-consistent since applying notEqual(x,y) will constrain y to {2}.

A solution is an assignment of values to variables such that all variables are grounded and the net is arc-consistent.

A constraint solver propagates constraints until the constraint net is arc-consistent and it searches by repeatedly constraining or grounding variables until a solution is found.

When a variable is constrained effectively, i.e., the set of possible values is smaller than before, we should try to propagate that information by invoking propagate on all the constraints depending on that variable.

First step is to make the constraint variable observable so we can get notified when it changes value. Then let the constraint register itself as listener to its ingoing variables and, when one of the variables is constrained, notify the solver that the constraint should be propagated again.

The solver is an object that keeps a queue of constraints that have to be propagated. There are two reasons for using a solver object instead of just letting the constraint propagate when a variable is constrained: we invoke the constraint propagation fewer times because the solver ignores a constraint if it already is in the queue, and in a more complex setting, the solver can prioritize the constraints and propagate them in prioritized order.

implement solver
clauses
    addConstraint(Constraint):-
        not(pending(Constraint)),
        !,
        assertz(pending(Constraint)).
    addConstraint(_).

clauses
    propagate():-
        retract(pending(Constraint)),
        !,
        Constraint:propagate(),
        propagate().
    propagate().

propagate is determ and fails if a variable becomes over constrained during propagation.

Searching

To keep things simple we haven’t implemented search in this constraint solver. Nevertheless, it is interesting to consider how it could be done.

The aim of the game is to find a solution where all the variables are grounded and all the constraints are satisfied. The definition of a Sudoku guarantees that there is only one such solution, but in other cases there could be more than one. Furthermore, if we had used a weaker constraint, e.g., the notEqual constraint, constraint propagation wouldn’t have given a grounded solution.

A simple search algorithm starts with an arc-consistent net, which isn’t grounded.

Pick a variable that isn’t grounded for each possible value of that variable ground the variable to that value and try to solve the constrained net.

setBackTrackPoint saves the value of all the variables on the way in and reset them on the way out. This can be implemented such that only the variables that are changed have to be saved and reset.

clauses
    solve(Net):-
        Net:isGrounded(),
        !,
        Net:printSolution().
    solve(Net):-
        Var = Net:pickNotGroundedVariable(),
        Val = Var:getValue_nd(),
            Net:setBackTrackPoint(),
            V:ground(Val),
            Net:propagate(),
            solve(Net),
        fail.
    solve(_).

clauses
    setBackTrackPoint():-
        btp := btp + 1,
        saveVariables().
    setBackTrackPoint():-
        btp := btp - 1,
        rollBackVariables(),
        fail.

Permutation

Instead of the notEqual constraint, we can use the originally suggested permutation constraint. The following implementation is interesting because it allows us to find the solution without searching.

Before looking at the algorithm, we will illustrate how it works with some examples.

Consider the domain{1..4}

X = {1}
Y, Z, W = {1,2,3,4}
permutation(X,Y,Z,W)

Because X is grounded to 1, Y,Z,W cannot take the value 1 and propagation gives:

Y, Z, W = {2,3,4}

Another example, which illustrate why this constraint is better than the corresponding set of notEqual constraints.

X, Y = {1,2}
Z, W = {1,2,3,4}
permutation(X,Y,Z,W)

We have 2 variables, X and Y, which can take on exactly 2 different values, 1 and 2. That means that none of the other variables can have any of the values 1 or 2, because if they did there would not be enough values to give both X and Y one. So, propagation removes 1 and 2 from the other variables.

Z, W = {3, 4}

The last example generalizes this principle further:

X = {1,2}, Y = {2,3}, Z = {1,3}
W = {1,2,3,4}
permutation(X,Y,Z,W)

Here we have 3 variables which together can have 3 different values; X, Y, Z can have the values 1, 2, 3. That means that the rest of the variables, here W, cannot have any of these values, so W must be {4}.

In general, if we have N variables, which together can have N different values, then the remaining variables cannot have any of these values.

In code, this looks as follows:

clauses
    propagate():-
        N = fromto(1,8),
        NVars = getNSubset_nd(N, [V || variable(V)]),
            Values = getValues(NVars),
            length(Values) = N,
            constrainOther(complement(Values), NVars),
        fail.
    propagate ().

clauses    
    getNSubset_nd(0,_) = [].
    getNSubset_nd(N,[X|Xs]) = [X|getNSubset_nd(N-1,Xs)].
    getNSubset_nd(N,[_|Xs]) = getNSubset_nd(N,Xs).

For each N we look at N-subsets (NVars) of the full set of variables in the permutation. If they can have exactly N different values (length(Values) = N) then other variables cannot have these values, i.e., they can be constrained to the complement of these values.

It turns out that the 27 instances of this constraint 9 rows, 9 columns and 9 groups on the 81 variables together with a proper initial Sudoku problem formulation has the property that the solution can be found by constraint propagation alone.

Challenge: The property stated above has not been proven. Either prove it or find a Sudoku where it doesn’t hold.

A nineSetControl

One of the purposes of this project was to visualize the work of the constraint propagation. I.e., when writing 4 in a cell we want to see that 4 no longer is a possible value in the row, column and group containing that cell. A typical way of doing that when solving Sudoku by hand is to write dots or crosses in the cells in a pattern resembling the numbers on a phone pad. So one writes

X

X

X

to indicate that 2, 3, and 6 are not possible values in the cell.

We make a custom control (nineSetControl) that display a subset of {1..9} in this way. The full set is a blank cell, the empty set is a red cell to indicate that the problem is over constrained, a singleton set is just the number and all other subsets are display by “dotting” out the numbers not in the set.

This group shows some of the possible looks of the “nineSetControl”.

Model-View-Control

The constraint variables are already “observable” so it comes natural to use an MVC-pattern and let the control “listen” to the constraint variable, which is also a model of subsets of {1..9}, and redraw itself whenever the variable changes value.

The control part of the MVC-pattern comes when the user types a number in one of the cells or when the solver constrains the variables.

A sudokuControl

Having defined the “nineSetControl”, it is easy to define a “sudokuControl” which place 81 “nineSetControls” in a 9 by 9 grid.

Finally, we add the possibility to load and save Sudokus and we add a delay to the constraint solver so it becomes possible to see the individual steps in the propagation properly.

We can now type a Sudoku into the Sudoku dialog press solve and see the propagation work.


The 4 pictures above illustrate different stages of the propagation.

Conclusion

It has been fun to develop this small application and experiment with some of the new Visual Prolog 7 features, although it has taken some of the fun out of solving Sudoku puzzles by hand. Initially I implemented the notEqualConstraint and it was possible to use the dialog to solve Sudokus by hand, the constraint propagation only showed the obvious constrains on the fields. I then considered the natural extension with 2 fields with 2 values and the only one field can hold the value constraints and realized that they were instances of the more general permutation or allDiff constraint. Somewhat to my surprise it turned out that the constraint solved most Sudoku puzzles by propagation alone.

The performance of the solution is excellent in the sense that without the delay the solution appears instantly.

The Object System

Having worked with a similar constraint solver in Visual Prolog 5, I can say with confidence that the object system is a great help. Both by structuring the solver and because of subsumption polymorphism it is easy to extend with new variable domains and constraints.

New PFC

The new PFC made it easy to make custom controls. Both the “nineSetControl” and the “sudokuControl” with the 81 “nineSetContols”.

Also the new “anchor” system made it easy to make resizable dialogs.

There was only one place, where I was left with trial and error. Finding the correct font size for the number in the “nineSetControl” was beyond my reasoning capabilities.

Visual Prolog 7

Polymorphism, if-then-else, and list comprehensions have been a small help. But in this application they are not essential. It has been nice to be able to write:

predicates
    getValues : (set Variable*) -> integer* Values.

instead of having to declare the list domains.

Future Work

One can extend this program in many directions. The obvious would be to find extra constraint to make the solution solve all Sudoku puzzles. Another possibility would be to have a selection of weaker constraints and allow the user to select which constraints should be used in the net. It would thus be possible to grade Sudoku puzzles depending on what kind of rules you need to solve the Sudoku. You can generalize the layout so it can handle 6 by 9 and 4 by 4 Sudoku as well as 16 by 16 Sudoku (Hex Sudoku). One could add backtracking and search to the solver as suggested.

Discuss the example in Visual prolog Discussion Forum.