Solving “Greater Than” Sudoku with Answer Set Programming

Thursday, 8th January, 2015

Sergii Dymchenko recently posted a blog showing how a “greater than” sudoku can be solved with constraint logic programming and ECLiPSe CLP.

Sergii’s post inspired me to do the same for answer setprogramming, with clasp/gringo. I’ve uploaded the code to github.

Brief notes on ASP (& Sudoku)

I am just getting started with answer set prolog. Here are some first impressions:

Syntactically, it is very similar to Good Old Fashioned Prolog, with one or two additions. For example:

syntactic sugar

There’s a lot of sugar enabling concise code. e.g.,

number(1..9).

expands to


number(1).
number(2).
number(3).
number(4).
number(5).
number(6).
number(7).
number(8).
number(9).

headless predicates

A predicate without a head is known as a constraint. The sense is that the specified conjunction is not true.


:- paint(R, C1, N), paint(R, C2, N), C1 != C2.

In the sudoku code, paint/3 is a fact signifying that a cell at Row and Column has Number. The constraint above states that in a given row, a number can be at most one column.

multi-headed predicates

There seem to be various kinds of multi-headed predicates, with accompanying sugar for concise representation. A common construct is


1 { paint(R, C, P) : number(P) } 1 :- square(R, C).

The part of the head inside brackets is like a set comprehension and expands to


paint(R, C, 1) | paint(R, C, 2) | ... | paint(R, C, 8) | paint(R, C, 9).

Having this kind of disjunction in the head gives a kind of indeterminism: this disjunction is true if the body of the predicate is true.

The numbers to either side of the brackets put lower and upper bounds on the number of facts that this disjunction can introduce. So, in plain English, this predicate says something like “every square should be given exactly one number”.

semantics

Semantically there is a difference too. We understand an answer set prolog program as representing a set of states of affairs, where a state of affairs is a set of true facts (i.e., including no facts of the form ‘not P’).

Things like how many states of affairs, and which facts from each state of affairs, are reported to the user are dealt with by declarations (like #show in the sudoku script) and command line arguments.

In practice, this means that instead of passing round a data structure between predicates (e.g., a list of lists for a sudoku grid), statements inside predicates can be made which directly affect the database (i.e., the state of affairs) — e.g., the paint/3 statements scattered about sudoku.lp.

Describing it just now, that sounds scarily like global variables.

Extras for “Greater Than”

As a “Greater Than” Sudoku is just an ordinary sudoku with an extra constraint, I’ve put the required extra predicate lessEqual/4 in a separate script, sudoku_extra_gt.lp

The question grid is just the set of facts that we have initially. With standard sudoku, it’s the cell that have been given numbers, e.g., puzzle_easy.lp:


paint(1, 1, 7).
paint(1, 3, 3).
paint(1, 5, 8).
paint(1, 8, 1).
paint(2, 5, 6).
paint(3, 1, 6).
% ...

[
QUESTION FOR ASP EXPERTS: at first I tried “positive” constraints with a greaterThan/4 predicate, like this


greaterThan(1,1,1,2).
greaterThan(1,3,1,2).
greaterThan(1,4,1,5).
greaterThan(1,6,1,5).
greaterThan(1,8,1,7).
greaterThan(1,8,1,9).
% ...

but these seemed to be ignored in the answer set. Why? How should I have phrased it?
]

Running the solver on this Greater Than sudoku shows the paint predicates which are true given all the constraints:


$ clingo 0 puzzle_gt.lp sudoku.lp sudoku_extra_gt.lp
clingo version 4.4.0
Reading from puzzle_gt.lp ...
Solving...
Answer: 1
paint(8,1,1) paint(2,2,1) paint(6,3,1) paint(5,4,1) paint(9,5,1) paint(3,6,1)
paint(4,7,1) paint(7,8,1) paint(1,9,1) paint(3,1,2) paint(6,2,2) paint(8,3,2)
paint(2,4,2) paint(4,5,2) paint(7,6,2) paint(1,7,2) paint(5,8,2) paint(9,9,2)
paint(6,1,3) paint(1,2,3) paint(7,3,3) paint(4,4,3) paint(2,5,3) paint(8,6,3)
paint(9,7,3) paint(3,8,3) paint(5,9,3) paint(5,1,4) paint(7,2,4) paint(1,3,4)
paint(3,4,4) paint(6,5,4) paint(9,6,4) paint(8,7,4) paint(4,8,4) paint(2,9,4)
paint(9,1,5) paint(4,2,5) paint(2,3,5) paint(7,4,5) paint(3,5,5) paint(5,6,5)
paint(6,7,5) paint(1,8,5) paint(8,9,5) paint(4,1,6) paint(8,2,6) paint(3,3,6)
paint(9,4,6) paint(1,5,6) paint(6,6,6) paint(5,7,6) paint(2,8,6) paint(7,9,6)
paint(7,1,7) paint(3,2,7) paint(4,3,7) paint(8,4,7) paint(5,5,7) paint(1,6,7)
paint(2,7,7) paint(9,8,7) paint(6,9,7) paint(1,1,8) paint(5,2,8) paint(9,3,8)
paint(6,4,8) paint(7,5,8) paint(2,6,8) paint(3,7,8) paint(8,8,8) paint(4,9,8)
paint(2,1,9) paint(9,2,9) paint(5,3,9) paint(1,4,9) paint(8,5,9) paint(4,6,9)
paint(7,7,9) paint(6,8,9) paint(3,9,9)
SATISFIABLE

Models : 1
Calls : 1
Time : 20.837s (Solving: 17.59s 1st Model: 17.45s Unsat: 0.14s)
CPU Time : 20.836s

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: