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.