# Solving Greater Than Sudoku using constraint logic programming

Greater Than Sudoku (Compdoku) is a variant of sudoku where no initial values are given, but there are greater-than relations inside 3×3 squares that the values must satisfy (the picture from http://avva.livejournal.com/2832977.html): I want to show how the puzzle can be solved with constraint logic programming and ECLiPSe CLP.

Constraint logic programming is a logic programming extension that includes concepts from constraint satisfaction. This paradigm can be very handy for solving grid puzzles like Greater Than Sudoku.

ECLiPSe CLP is an open-source Prolog-based system with a good support for modeling and solving problems with constraint logic programming.

Here is a complete program to solve the puzzle using ECLiPSe (https://github.com/kit1980/grid-puzzle-solver/blob/master/greater-than-sudoku.ecl):

```:- lib(ic).
:- lib(ic_global).

% http://ic.pics.livejournal.com/avva/111931/80092/80092_original.jpg
problem([](
[](>,<,>,<,<,>),
[](^,v,^,v,v,^,^,^,^),
[](>,<,<,<,>,>),
[](v,^,^,^,^,v,^,v,^),
[](<,>,<,>,>,<),
[](>,<,>,<,<,<),
[](v,^,^,v,^,v,^,v,v),
[](<,<,<,>,>,<),
[](v,v,v,^,v,^,v,^,^),
[](>,>,>,<,<,>),
[](>,>,<,>,>,<),
[](v,^,v,^,^,^,v,^,v),
[](<,>,<,>,<,>),
[](^,^,^,v,v,^,v,v,v),
[](<,>,>,<,<,>)
)).

model(Sudoku) :-
% standard sudoku constraints
dim(Sudoku, [9, 9]),
Sudoku :: 1..9,
alldifferent_matrix(Sudoku),
( multifor([I, J], 0, 2), param(Sudoku) do
Square is Sudoku[3*I+1..3*I+3, 3*J+1..3*J+3],
flatten(Square, SquareVars),
ic:alldifferent(SquareVars)
),
problem(Problem),
% greater-than horizontal constraints
( for(I, 1, 9), param(Sudoku, Problem) do
( for(B, 1, 6), param(Sudoku, Problem, I) do
A is 5 * ((I - 1) div 3) + 2 * ((I - 1) mod 3) + 1,
J is 3 * ((B - 1) div 2) + ((B - 1) mod 2) + 1,
Rel is Problem[A, B],
call(Rel, Sudoku[I, J], Sudoku[I, J + 1])@ic
)
),
% greater-than vertical constraints
( for(J, 1, 9), param(Sudoku, Problem) do
( for(T, 1, 6), param(Sudoku, Problem, J) do
A is 5 * ((T - 1) div 2) + 2 * ((T - 1) mod 2 + 1),
B is J,
I is 3 * ((T - 1) div 2) + ((T - 1) mod 2) + 1,
RelSymb is Problem[A, B],
( RelSymb == '^' ->
Rel = '<'
;
Rel = '>'
),
call(Rel, Sudoku[I, J], Sudoku[I + 1, J])@ic
)
).

find(Sudoku) :-
search(Sudoku, 0, most_constrained, indomain_min, complete, []).

main :-
model(Sudoku),
find(Sudoku),
( foreacharg(Row, Sudoku) do
array_list(Row, List),
concat_string(List, Str),
writeln(Str)
).
```

Conceptually, the program is very simple: we define a 9×9 array of integer 1..9 variables, constraint every row, column and square to have different values, and impose greater-than constraints according to the problem. Then using the `find` predicate we find concrete values of the variables that satisfy the model constraints. `most_constrained` and `indomain_min` are heuristics that the search will use, but any other heuristics should work for our small problem (see http://eclipseclp.org/doc/bips/lib/ic/search-6.html for all possible options).

The `problem` predicate encodes rows of horizontal and vertical greater-than signs of the given puzzle (`v` and `^` denote vertical greater-than signs). Most of the (somewhat complicated) code in `model` is for finding row and column value indexes for a particular greater-than sign.

The program is declarative: we don't say how to find the values we want, we only say which constraints the values we want must satisfy.

Here is the answer to the puzzle according to the program:

```834967251
915238764
276451839
657329148
489175623
321846597
743582916
162793485
598614372
```

Almost every modern logic programming system supports constraint programming, so it shouldn't be too hard to translate my program to SWI-Prolog, Mercury or Picat.

For more examples of solving grid puzzles with ECLiPSe see Hakan Kjellerstrand's ECLiPSe page.