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).