Sudoku-Like Puzzles
Date: Tue, 3 Oct 2006
From: Paolo Ferraris
To: TAG
I have found two puzzle games similar to sudoku that seem interesting
for answer set programming.
1) In Hitori
http://en.wikipedia.org/wiki/Hitori
you have a grid filled with numbers. The goal is to cancel out some cells
so that some conditions are satisfied. One of them is that all uncancelled
cells are interconnected to each other.
2) In Hashiwokakero,
http://en.wikipedia.org/wiki/Hashiwokakero
you are given a map with some islands on them. The goal is to put bridges
between islands - with some given constraints - to connect all of them.
Those puzzles seem interesting for answer set programming as they involve
the concept of reachability, which is usually hard to express in other
kinds of formalisms such as satisfiability or constraint programming, but
relatively simple in ASP.
===========
Date: Wed, 4 Oct 2006
From: Pedro Cabalar
To: TAG
Just for fun: I send attached an encoding of Hitori in FAL (it's a
high-level language I'm using ontop of lparse/smodels). The first file
is the general domain code, and the second a particular scenario.
You can try to play with it online at
http://www.dc.fi.udc.es/~cabalar/fal/FALonline.html
Just select the "Hitori" predefined example, paste the scenario from
local file "hitori-sce1.fal" and mark the "Graphic output" (by now, only
8x8 arrays will work with this option).
As you can see, I used a predicate reach(R,C,R2,C2) that decides whether
cell R,C can reach cell R2,C2. This implies a lot of grounding. Perhaps
somebody could find a more efficient implementation in this sense...
----------
An interesting puzzle that requires reachability as well is the Sokoban
game (actually, a planning scenario).
http://en.wikipedia.org/wiki/Sokoban
For an efficient planning, it's very important that you factor out the
robot movements to get to "reachable" stones, and just express the plan
in terms of stone pushes. To this aim, a reachability fluent is required
(there exist DLV and lparse implementations of Sokoban using this
trick). I ignore whether planning languages, like PDDL, allow recursive
predicates like the one it would be required here.
Regards,
Pedro.
----------
instances
digit 1..9.
static
array : row x column -> digit.
black : row x column -> boolean = false.
vars
R,R2: row.
C,C2: column.
rules
black(R,C) in boolean.
% no repeated white digit in the same row
:- array(R,C)=array(R,C2), not black(R,C), not black(R,C2), C boolean = false.
rules
reach(R,C,R,C) :- not black(R,C).
reach(R,C,R2,C2) :- reach(R,C,R2-1,C2), not black(R2,C2).
reach(R,C,R2,C2) :- reach(R,C,R2+1,C2), not black(R2,C2).
reach(R,C,R2,C2) :- reach(R,C,R2,C2-1), not black(R2,C2).
reach(R,C,R2,C2) :- reach(R,C,R2,C2+1), not black(R2,C2).
:- not black(R,C), not black(R2,C2), not reach(R,C,R2,C2).
----------
rules
array(0,0)=4.
array(0,1)=8.
array(0,2)=1.
array(0,3)=6.
array(0,4)=3.
array(0,5)=2.
array(0,6)=5.
array(0,7)=7.
array(1,0)=3.
array(1,1)=6.
array(1,2)=7.
array(1,3)=2.
array(1,4)=1.
array(1,5)=6.
array(1,6)=5.
array(1,7)=4.
array(2,0)=2.
array(2,1)=3.
array(2,2)=4.
array(2,3)=8.
array(2,4)=2.
array(2,5)=8.
array(2,6)=6.
array(2,7)=1.
array(3,0)=4.
array(3,1)=1.
array(3,2)=6.
array(3,3)=5.
array(3,4)=7.
array(3,5)=7.
array(3,6)=3.
array(3,7)=5.
array(4,0)=7.
array(4,1)=2.
array(4,2)=3.
array(4,3)=1.
array(4,4)=8.
array(4,5)=5.
array(4,6)=1.
array(4,7)=2.
array(5,0)=3.
array(5,1)=5.
array(5,2)=6.
array(5,3)=7.
array(5,4)=3.
array(5,5)=1.
array(5,6)=8.
array(5,7)=4.
array(6,0)=6.
array(6,1)=4.
array(6,2)=2.
array(6,3)=3.
array(6,4)=5.
array(6,5)=4.
array(6,6)=7.
array(6,7)=8.
array(7,0)=8.
array(7,1)=7.
array(7,2)=1.
array(7,3)=4.
array(7,4)=2.
array(7,5)=3.
array(7,6)=5.
array(7,7)=6.
instances
row 0..7.
column 0..7.
===========
Date: Wed, 4 Oct 2006
From: Wolfgang Faber
To: TAG
In Italy (and probably also elsewhere), Kakuro has become almost as
popular as Sudoku:
http://en.wikipedia.org/wiki/Kakuro
It is fairly easy to represent in ASP if sum/weight constraints are
available.
For Sudoku, I have written a simple pre- and postprocessor, which allows
solving of traditional 9x9 Sudokus using DLV just seeing ASCII graphics.
Very useful for convincing people who are not into computer science that
what you do at work is of use for them. :) I've made it available here:
http://www.wfaber.com/software/sudokusolver/
Sokoban will be part of the upcoming ASP system competition in the MGS
(Modeling, Grounding, Solving) track:
http://asparagus.cs.uni-potsdam.de/contest/
An interesting aspect of Sokoban is that many problem instances are
available on the web in a standardized format. I have several thousands,
but probably not all of these are unique.
===========
Date: Wed, 4 Oct 2006
From: Martin Brain
To: TAG
http://www.cs.bath.ac.uk/~mjb/asp/su-doku-dist.tar.bz2
I wrote a perl script to parse the output format.
===========
Date: Wed, 4 Oct 2006
From: Paolo Ferraris
To: Pedro Cabalar
So, if I understand correctly, sokoban doesn't necessarily need the
concept of reachability but it can help making the search much simpler?
===========
Date: Thu, 5 Oct 2006
From: Wolfgang Faber
To: Paolo Ferraris
I think so. Reachability will be there in some form in any case: If
one-step robot moves that do not push a stone/box are also made actions,
then a series of moving actions implicitly also encodes reachability.
In my view, this is a question of granularity in the modelling, you can
have very basic actions, which "derive" some properties of the domain
via the planning mechanism (here being able to reach another position),
or you may have complex actions which include some of these properties
in their own definition. In the case of Sokoban, having basic actions
has the drawback of opening up the search space considerably. Moreover
it may be harder to "achieve" goal-directedness: Just wandering around
does not really approach the goal, only pushing stones/boxes does. So
one can say that the only purpose of walking in the game of Sokoban is
getting in the position to push boxes, so these actions could be
profitably united to form a more complex walk-and-push action. Doing so,
however, reduces the flexibility when the domain or goal is to be
modified.
===========
Date: Thu, 5 Oct 2006
From: Pedro Cabalar
To: TAG
I send attached an encoding of Sokoban in PDDL I've found as benchmark
at the PLANET site. As you can see, they consider both types of actions:
movements and pushes. What I don't know is whether PDDL allows doing it
in the other way, i.e., representing reachability.
Paolo Ferraris wrote:
> So, if I understand correctly, sokoban doesn't necessarily need the
> concept of reachability but it can help making the search much simpler?
Definitely. As far as I know, the best Sokoban solver ("Rolling stone")
http://www.cs.ualberta.ca/~games/Sokoban/program.html
does use reachability as a starting point (then, it uses a lot of
domain-dependent techniques).
Wolfgang Faber wrote:
>In my view, this is a question of granularity in the modelling
I've seen some titles of planning articles (I didn't read them though)
where they seem to tackle the Sokoban problem as hierarchical planning:
probably, at a first level, they'll just have a macro action to reach a
stone. As Wolfgang says, this would be comparable to reachability.
>So one can say that the only purpose of walking in the game of Sokoban is
>getting in the position to push boxes, so these actions could be
>profitably united to form a more complex walk-and-push action
In fact, some programs for playing Sokoban allow you to mark a position
and they automatically move the robot there (if they can). So, for the
game itself, moving doesn't seem to be considered a significant part of
the puzzle.
>Doing so,
>however, reduces the flexibility when the domain or goal is to be
>modified.
Sure: the scenario could be easily elaborated to force taking into
account the movements. Furthermore, I've even seen somewhere an
objection about what should be used to measure a "minimal" plan. Most
people would probably accept stone pushes, but if you consider that a
movement also has a cost, then you could get a different minimal
solution (for instance, it could be the case that you make more pushes
but less movements).
Anyway, if current "standard" planning tools cannot handle reachability,
I think it could be a valid example to support ASP planning: it would
show how reacher expressiveness may provide more efficiency too.
----------
(define (domain sokoban)
(:requirements :strips)
(:predicates (navigable ?l)
(direction ?d)
(ball ?b)
(at-robot ?l)
(at ?o ?l)
(adjacent ?l1 ?l2 ?d)
(empty ?l))
(:action move
:parameters (?from ?to ?dir)
:precondition (and (navigable ?from) (navigable ?to) (direction ?dir)
(at-robot ?from) (adjacent ?from ?to ?dir) (empty ?to))
:effect (and (empty ?from) (at-robot ?to) (not (empty ?to))
(not (at-robot ?from))))
(:action push
:parameters (?rloc ?bloc ?floc ?dir ?b)
:precondition (and (navigable ?rloc) (navigable ?bloc) (navigable ?floc)
(direction ?dir) (ball ?b) (at-robot ?rloc)
(at ?b ?bloc) (adjacent ?rloc ?bloc ?dir)
(adjacent ?bloc ?floc ?dir) (empty ?floc))
:effect (and (at-robot ?bloc) (at ?b ?floc) (empty ?rloc)
(not (at-robot ?rloc)) (not (at ?b ?bloc)) (not (empty ?floc))))
)
===========
Date: Thu, 5 Oct 2006
From: Martin Brain
To: TAG
On Thu, 2006-10-05 at 02:29 +0200, Wolfgang Faber wrote:
> On Wed, Oct 04, 2006 at 03:26:10PM -0500, Paolo Ferraris wrote:
> > So, if I understand correctly, sokoban doesn't necessarily need the
> > concept of reachability but it can help making the search much simpler?
>
> I think so. Reachability will be there in some form in any case: If
> one-step robot moves that do not push a stone/box are also made actions,
> then a series of moving actions implicitly also encodes reachability.
Reachability (or the lack thereof) is a key concept in many of the
obvious search 'optimisations' in Sokoban. I would be surprised if you
can produce anything resembling a good Sokoban solver without it.
> In my view, this is a question of granularity in the modelling, you can
> have very basic actions, which "derive" some properties of the domain
> via the planning mechanism (here being able to reach another position),
> or you may have complex actions which include some of these properties
> in their own definition. In the case of Sokoban, having basic actions
> has the drawback of opening up the search space considerably. Moreover
> it may be harder to "achieve" goal-directedness: Just wandering around
> does not really approach the goal, only pushing stones/boxes does. So
> one can say that the only purpose of walking in the game of Sokoban is
> getting in the position to push boxes, so these actions could be
> profitably united to form a more complex walk-and-push action. Doing so,
> however, reduces the flexibility when the domain or goal is to be
> modified.
FWIW I came to a similar (if less eloquent) conclusion when I was
writing Sokoban solvers in ASP. The problem I got stuck on what how to
encode the intuition "do not push a block if it will result in that or
any other block becoming perminantly unreachable" as it seem to be a
'second level' property in some sense.
I think Sokoban is one of the more interesting problems for showing what
logic based planning systems can do as it is an easy problem to
explain / grasp but has a number of difficult properties (i.e. you may
not realise that a move is wrong until a considerable time later and if
you are trying to minimise the number of moves used it has some nasty
hill climbing problems).
===========
Date: Fri, 6 Oct 2006
From: Pedro Cabalar
To: Martin Brain
>I'll see what I can do about getting encodings of Hitori and
>Hashiwokakero posted to the list in the next few days.
>
I've thought that, to save some time, perhaps you could reuse this: I
send you attached a silly C program for reading Hitori scenarios.
---------
#include
main() {
int c,i=0,j=0,n=0;
c=getchar();
while (c!=EOF) {
if (c=='\n') {
i++;
if (j>n) n=j;
j=0;
}
else
printf("array(%d,%d,%c).\n",i,j++,c);
c=getchar();
}
printf("\n");
printf("\% %d rows\n",i-1);
printf("\% %d columns\n",n-1);
}
--------
48163257
36721654
23482861
41657735
72318512
35673184
64235478
87142356
===========
Date: Fri, 6 Oct 2006
From: Martin Gebser
To: TAG
I wonder whether you would like to submit the puzzles as new benchmarks
to Asparagus. We currently extend the benchmark classes there for the
upcoming ASP solver competition.
In order to use any of the puzzles, we would need a short textual
problem description, instances as sets of facts, and an encoding if you
can provide it. All this material should be mailed to:
asparagus@cs.uni-potsdam.de
You can find further information here:
http://asparagus.cs.uni-potsdam.de/contest/
and
http://asparagus.cs.uni-potsdam.de/
===========
Date: Mon, 16 Oct 2006 11:22:49 +0200
From: Pedro Cabalar
To: Martin Brain and Paolo Ferraris
I've thought about the following trick that I guess it can be useful for
both puzzles. As we must encode "complete reachability", ie, every valid
position must be reachable from all the rest, we can try to get one
fixed position and represent that the rest are accessible from it. In
this way, we can replace 4-ary reachable(X,Y,X1,Y1) by a binary
predicate reachable(X,Y) (meaning, X,Y is reachable from our implicit
"fixed" position).
This fixed position could be, for instance, the
lexicographically-minimum one with a white cell (for Hitori) or an
island (for Hashiwokakero).
To test the effect, I've modified Martin's file hitori.lp by replacing
his reachability encoding (lines 48-54) by the new lines:
% take the "minimum" non-blacked position
existssmaller(X,Y) :- -blackOut(X,Y1), Y1 I've posted encodings of both problems to my web site:
> http://www.cs.bath.ac.uk/~mjb/asp/
I have looked at the Hitori encoding. You have ventured deep into the
lparse dungeon here...
I have also written programs for DLV and lparse (using "array" as input
predicate, as it was used by Pedro in some earlier mail, but that's easy
to change). I attach them to this message, along with the "converted"
example from Martin's tarball.
One performance issue in your program is the following rule:
reachable(X1,Y1,X2,Y2) :- reachable(X1,Y1,X,Y), reachable(X,Y,X2,Y2).
with a lot of implicit domain predicates.
You can replace that by
reachable(X1,Y1,X2,Y2) :- adjacent(X1,Y1,X,Y), reachable(X,Y,X2,Y2).
which reduces the size of the ground program considerably.
Of these three constraints
:- -blackOut(X1,Y), -blackOut(X2,Y), X1 != X2, not reachable(X1,Y,X2,Y).
:- -blackOut(X,Y1), -blackOut(X,Y2), Y1 != Y2, not reachable(X,Y1,X,Y2).
:- -blackOut(X1,Y1), -blackOut(X2,Y2), X1 != X2, Y1 != Y2, not reachable(X1,Y1,X2,Y2).
the third one seems to be redundant.
With these changes, the example in your tarball takes about 4 seconds
instead of 24 on my notebook...
Moreover, I'm not sure why you have used true negation here, I think you
can do without (reducing some further implicit constraints).
Ceterum censeo praedicata dominiorum esse delenda.
Seriously: I think that domain predicates are evil.
On Mon, Oct 16, 2006 at 11:22:49AM +0200, Pedro Cabalar wrote:
> I've thought about the following trick that I guess it can be useful for
> both puzzles. As we must encode "complete reachability", ie, every valid
> position must be reachable from all the rest, we can try to get one
> fixed position and represent that the rest are accessible from it. In
> this way, we can replace 4-ary reachable(X,Y,X1,Y1) by a binary
> predicate reachable(X,Y) (meaning, X,Y is reachable from our implicit
> "fixed" position).
Yes, this should work and should gain a lot!
FWIW, I have downloaded and converted to facts 20000 Hitori puzzles
available at http://ihsan.biz/math.html#hitoriDesc . I can put that
online if you want.
---------------
% Can have numbers up to some large upper bound.
#maxint=999999.
inked(R,C) v white(R,C) :- array(R,C,_).
row(R) :- array(R,_,_).
column(C) :- array(_,C,_).
symbol(S) :- array(_,_,S).
:- row(R), symbol(S), #count{ C: array(R,C,S), white(R,C) } > 1.
:- column(C), symbol(S), #count{ R: array(R,C,S), white(R,C) } > 1.
:- inked(R1,C), inked(R2,C), #succ(R1,R2).
:- inked(R,C1), inked(R,C2), #succ(C1,C2).
adj(R1,C,R2,C) :- row(R1), row(R2), #succ(R1,R2), column(C).
adj(R1,C,R2,C) :- row(R1), row(R2), #succ(R2,R1), column(C).
adj(R,C1,R,C2) :- column(C1), column(C2), #succ(C1,C2), row(R).
adj(R,C1,R,C2) :- column(C1), column(C2), #succ(C2,C1), row(R).
reached(R1,C1,R2,C2) :- adj(R1,C1,R2,C2), white(R1,C1), white(R2,C2).
reached(R1,C1,R2,C2) :- adj(R1,C1,R3,C3), reached(R3,C3,R2,C2), white(R1,C1).
tobereachable(R1,C1,R2,C2) :- white(R1,C1), white(R2,C2), R1 != R2.
tobereachable(R1,C1,R2,C2) :- white(R1,C1), white(R2,C2), C1 != C2.
:- tobereachable(R1,C1,R2,C2), not reached(R1,C1,R2,C2).
--------------
hide.
show inked(R,C).
row(R) :- array(R,C,S).
column(C) :- array(R,C,S).
symbol(S) :- array(R,C,S).
position(R,C) :- array(R,C,S).
{ inked(R,C) } :- position(R,C).
ninked(R,C,S) :- array(R,C,S), not inked(R,C).
:- 2 { ninked(R,C,S) : column(C) }, row(R), symbol(S).
:- 2 { ninked(R,C,S) : row(R) }, column(C), symbol(S).
:- inked(R,C), inked(R+1,C), position(R,C), position(R+1,C).
:- inked(R,C), inked(R,C+1), position(R,C), position(R,C+1).
adj(R,C,R+1,C) :- row(R), column(C).
adj(R+1,C,R,C) :- row(R), column(C).
adj(R,C+1,R,C) :- row(R), column(C).
adj(R,C,R,C+1) :- row(R), column(C).
reachable(R1,C1,R2,C2) :- adj(R1,C1,R2,C2), not inked(R1,C1), not inked(R2,C2).
reachable(R1,C1,R2,C2) :- adj(R1,C1,R3,C3), reachable(R3,C3,R2,C2), not inked(R1,C1), position(R2,C2).
:- position(R1,C1), position(R2,C2), not inked(R1,C1), not inked(R2,C2), not reachable(R1,C1,R2,C2).
---------------
% Example from http://en.wikipedia.org/wiki/Hitori
% Pictures (Hitori.jpg and Hitori_completed.jpg) are public domain
% Without reachability condition has over 100,000 answer sets - with it has 1
%#const height=8.
%#const width=8.
%#const n=8.
% array(X,Y,N)
array(1,1,4).
array(1,2,3).
array(1,3,2).
array(1,4,4).
array(1,5,7).
array(1,6,3).
array(1,7,6).
array(1,8,8).
array(2,1,8).
array(2,2,6).
array(2,3,3).
array(2,4,1).
array(2,5,2).
array(2,6,5).
array(2,7,4).
array(2,8,7).
array(3,1,1).
array(3,2,7).
array(3,3,4).
array(3,4,6).
array(3,5,3).
array(3,6,6).
array(3,7,2).
array(3,8,1).
array(4,1,6).
array(4,2,2).
array(4,3,8).
array(4,4,5).
array(4,5,1).
array(4,6,7).
array(4,7,3).
array(4,8,4).
array(5,1,3).
array(5,2,1).
array(5,3,2).
array(5,4,7).
array(5,5,8).
array(5,6,3).
array(5,7,5).
array(5,8,2).
array(6,1,2).
array(6,2,6).
array(6,3,8).
array(6,4,7).
array(6,5,5).
array(6,6,1).
array(6,7,4).
array(6,8,3).
array(7,1,5).
array(7,2,5).
array(7,3,6).
array(7,4,3).
array(7,5,1).
array(7,6,8).
array(7,7,7).
array(7,8,5).
array(8,1,7).
array(8,2,4).
array(8,3,1).
array(8,4,5).
array(8,5,2).
array(8,6,4).
array(8,7,8).
array(8,8,6).
===========
Date: Fri, 20 Oct 2006
From: Martin Brain
To: Wolfgang Faber
> Ceterum censeo praedicata dominiorum esse delenda.
>
> Seriously: I think that domain predicates are evil.
Would you mind if I asked why? I feel that using a variable over
different domains in different rules is poor coding style. Doing the
oppersite is only one step away from using domain predicates. In my
opinion they help keep the program small and more readable.
===========
Date: Sat, 21 Oct 2006
From: Wolfgang Faber
To: Martin Brain
For instance, given a 'database' (input) predicate r, I would like to
define the transitive closure t over it as follows:
t(X,Y) :- r(X,Y).
t(X,Y) :- t(X,Z), t(Z,Y).
or
t(X,Y) :- r(X,Y).
t(X,Y) :- r(X,Z), t(Z,Y).
With lparse, apparently I cannot do that, as in the first variant X,Y,Z
do not have a domain in the second rule, and in the second variant, Y
misses a domain in the second rule.
I can "repair" that by writing e.g.
t(X,Y) :- r(X,Y).
t(X,Y) :- t(X,Z), t(Z,Y), r(X,Z), r(Z,Y).
or
t(X,Y) :- r(X,Y).
t(X,Y) :- r(X,Z), t(Z,Y), r(Z,Y).
These are the "more informed" variants, one could also write
d(D) :- r(D,Y). d(D) :- r(X,D).
t(X,Y) :- r(X,Y).
t(X,Y) :- t(X,Z), t(Z,Y), d(X), d(Z), d(Y).
or
d(D) :- r(D,Y). d(D) :- r(X,D).
t(X,Y) :- r(X,Y).
t(X,Y) :- r(X,Z), t(Z,Y), d(Y).
or
rd1(D1) :- r(D1,Y). rd2(D2) :- r(X,D2).
t(X,Y) :- r(X,Y).
t(X,Y) :- t(X,Z), t(Z,Y), rd1(X), rd1(Z), rd2(Y).
etc.
The point is that doing this is not intuitive. The "domains" are
implicit in my original definitions, and I don't see the point of
being obliged to make them explicit - in fact in this example it is not
really clear in which way this should be done.
Now people may say: 'Who cares about transitive closure?'
Well, I do, but let's consider another example (still using r as input
predicate):
v(X,Y) :- r(X,Y), not w(X,Y).
w(X,Y) :- r(X,Y), not v(X,Y).
A frequent pattern in ASP, I would say. Now I want to do something with
v; let's do a simple projection on v and add:
y(X) :- v(X,Y).
Again it seems that I cannot do that with lparse, I should add "domains"
for X and Y. But I don't see why; this has already been done in the
definition for v that I wrote just before.
I heard arguments like "domain predicates are like enforcing safety". I
don't agree with that. The concept of safety can be motivated very well,
as the semantics of unsafe programs is ambiguous (it depends on the
universe you consider). The semantics of safe programs which are not
domain restricted is well-defined, however. For the concept of domain
restricted rules, I did not yet learn about a convincing motivation.
Concerning "using a variable over different domains in different rules":
The semantics of variables in ASP confines their meaning to one rule (or
constraint). For people who are new to ASP, this is often a difficult,
yet important issue to understand. I'm not very happy about blurring
this peculiarity, as I feel that doing so will really confuse people.
Moreover, I believe that in ASP one should use predicates/relations for
representing information, not variables; these should be used for
"linking" information.
I hope that this message will not start a flame-war...
===========
Date: Date: Mon, 23 Oct 2006
From: Martin Brain
To: Wolfgang Faber
> I have a problem with the concept of domain predicate in general.
Ah. I thought you were specifically objecting to the use of #domain to
set implict domain predicates rather than the more usual, explicit ones.
I'd agree that conceptually domain predicates are not a good solution.
Practically, I've run into a few problems with them but nothing that has
been inconvenient enough for me to try to write a replacement for
lparse. Then again I'd also say that, conceptually having a separate
grounding / instantiation phase is not a good solution - but I've yet to
create a better way of doing things so I guess my opinion doesn't count
for much.
> For instance, given a 'database' (input) predicate r, I would like to
> define the transitive closure t over it as follows:
>
> t(X,Y) :- r(X,Y).
> t(X,Y) :- t(X,Z), t(Z,Y).
>
> or
>
> t(X,Y) :- r(X,Y).
> t(X,Y) :- r(X,Z), t(Z,Y).
Ofcourse it would be ideal if systems treated these as equivalent -
rather than the current situation where the later is 'faster'.
> The point is that doing this is not intuitive. The "domains" are
> implicit in my original definitions, and I don't see the point of
> being obliged to make them explicit - in fact in this example it is not
> really clear in which way this should be done.
This seems reasonable.
> Now people may say: 'Who cares about transitive closure?'
IMHO anyone who cares about answer set solvers as a computational tool
should. Without transitive closure there aren't currently very many
things that require non-tight programs. If you don't care about
non-tight programs then, in terms of computation, you might as well work
with SAT solvers.
> Well, I do, but let's consider another example (still using r as input
> predicate):
>
> v(X,Y) :- r(X,Y), not w(X,Y).
> w(X,Y) :- r(X,Y), not v(X,Y).
>
> A frequent pattern in ASP, I would say. Now I want to do something with
> v; let's do a simple projection on v and add:
>
> y(X) :- v(X,Y).
>
> Again it seems that I cannot do that with lparse, I should add "domains"
> for X and Y. But I don't see why; this has already been done in the
> definition for v that I wrote just before.
Again, implicitly rather than explicitly.
> I heard arguments like "domain predicates are like enforcing safety". I
> don't agree with that. The concept of safety can be motivated very well,
> as the semantics of unsafe programs is ambiguous (it depends on the
> universe you consider). The semantics of safe programs which are not
> domain restricted is well-defined, however.
Pratically, I don't think this is a very good way of trying to reduce
the number of errors as domain predicates (as implemented in lparse)
don't give any real feedback to the user.
> For the concept of domain
> restricted rules, I did not yet learn about a convincing motivation.
My impression was that they were an implementation constraint.
> Concerning "using a variable over different domains in different rules":
> The semantics of variables in ASP confines their meaning to one rule (or
> constraint). For people who are new to ASP, this is often a difficult,
> yet important issue to understand. I'm not very happy about blurring
> this peculiarity, as I feel that doing so will really confuse people.
I don't see keeping variables linked with the (implicit or explicit)
domains as blurring this. I'm suggesting this as a programming style
rather than a hard and fast rule.
> Moreover, I believe that in ASP one should use predicates/relations for
> representing information, not variables; these should be used for
> "linking" information.
Again, I agree but this isn't what I was proposing. I was simply
suggesting that willfully reusing the same few variables, attached to
different domains in each rule could make programs less readable. For
example, I'd suggest that encoding the constraints in su-doku as:
:- state(XA,Y,N), state(XB,Y,N), XA != XB.
:- state(X,YA,N), state(X,YB,N), YA != YB.
:- state(XA,YA,N), state(XB,YB,N), sameSubSquare(XA,XB),
sameSubSquare(YA,YB), XA != XB, YA != YB.
rather than
:- state(A,B,C), state(D,B,C), A != D.
:- state(A,B,C), state(A,D,C), B != D.
:- state(A,B,C), state(D,E,C), sameSubSquare(A,D), sameSubSquare(B,E),
A != D, B != E.
or even
:- state(A,B,C), state(D,B,C), A != D.
:- state(C,A,B), state(C,D,B), A != D.
:- state(D,B,A), state(E,C,A), sameSubSquare(E,D), sameSubSquare(C,B),
D != E, B != C.
if you accept that (roughly) keeping a variable associated with a domain
is a good way of programming - then the #domain construct seems a better
way of creating domain predicates than adding in explicit extra atoms.
This point is essentially independant of whether domain predicates are a
good idea at all.
=============
Date: Fri, 27 Oct 2006
From: Richard Watson
To: TAG
Here is another Hitori solver. I put a lot of the explanation
in the code, including some propositions about the types of Hitori
puzzles it can solve and the solutions it gives. I used different
a different encoding for reachable, as well as a different way of
choosing which squares ot blank out. Based on some benchmarking
runs, the change in reachable leads to a substancial decrease in
time over the other solutions. I have only run a few tests so far,
but for those tests, changing between the encodings for choosing blank
squares didn't seem have an impact on the timing.
----------
% Solution for Hitori puzzles
% by Richard Watson, Texas Tech University
% richard.watson@ttu.edu
%
%
% Input: A puzzle given as a set of facts of the form
% array(r,c,v). - where r is the row,
% c is the column,
% v is the value in (r,c).
% Predicates:
% position(r,c) - true if (r,c) is a grid position in the puzzle
% blanked(r,c) - true if (r,c) is blanked out
% adjacent(r,c,r1,c1) - true if (r,c) and (r1,c1) are adjacent positions
% reachable(r,c) - true if (r,c) is an unblanked square and there is a
% path between (r,c) and any other unblanked square.
% Output: Answer sets such that, if the positions indicated by the
% "blanked" predicate were blanked out in the puzzle given as
% input, then the resulting grid is a solution to the puzzle.
% Note that, under rules of Hitori stated on Wikipedia, a board
% may have multiple solutions. Take for instance a 2X2 board
% containing 4 different numbers. Not blanking out anything
% would be a valid solution, as would blanking out any one of
% the four squares. This program would only return the solution
% in which no squares were blanked out.
% Assumptions:
% The puzzle grid contains position (1,1).
% If the puzzle gird contains at least two positions, (1,2) is a
% valid position.
% Proposition 1: Any solvable Hitori puzzle can be input given the
% the assumptions above via translation and rotation.
% Proposition 2: This program will find all solutions in which the
% number of squares blanked out is minimal.
% Proposition 3: This will solve even irregular shaped Hitori puzzles.
% If there is a value given to a row column pair, then
% that row column pair is a position.
position(R,C) :- array(R,C,V).
% If two positions in the same column have the same
% value and one is not blanked, the other must be.
blanked(R2,C) :- array(R1,C,V),
array(R2,C,V),
neq(R1,R2),
not blanked(R1,C).
% If two positions in the same row have the same
% value and one is not blanked, the other must be.
blanked(R,C2) :- array(R,C1,V),
array(R,C2,V),
neq(C1,C2),
not blanked(R,C1).
% Simple declaration of when two positions were adjacent
adjacent(R,C,R,C+1) :- position(R,C), position(R,C+1).
adjacent(R,C,R,C-1) :- position(R,C), position(R,C-1).
adjacent(R,C,R+1,C) :- position(R,C), position(R+1,C).
adjacent(R,C,R-1,C) :- position(R,C), position(R-1,C).
% We declare 1,1 and 1,2 to be reachable positions if
% they are not blanked. We are abusing the positions
% a little here in that for a 1X1 board, 1,2 is not
% a valid position. By the rules of Hitori, since
% adjacent squares cannot be blanked, one of these two
% must not be blanked.
reachable(1,1) :- not blanked(1,1).
reachable(1,2) :- not blanked(1,2).
% A position is reachable if it is not blanked and it
% is adjacent to a reachable position. It can easily
% be shown that there is a path of non-blank positions
% between any pair of reachable positions.
reachable(R,C) :- not blanked(R,C),
adjacent(R,C,R1,C1),
reachable(R1,C1).
% Every position that is not blanked must be reachable.
:- position(R,C), not blanked(R,C), not reachable(R,C).
% Adjacent positions cannot both be blanked.
:- blanked(R,C), blanked(R1,C1), adjacent(R,C,R1,C1).
hide.
show blanked(R,C).