Attachment 'sokoban.core.asp.txt'
Download 1 % Written by Wolfgang Faber <wf@wfaber.com>
2 %
3 % Input:
4 % right(L1,L2) : location L2 is right of location L1
5 % top(L1,L2): location L2 is on top of location L1
6 % box(L): location L initially holds a box
7 % solution(L): location L is a target for a box
8 % sokoban(L): the sokoban is at location L initially
9 % step(S): S is a step
10 % next(S1,S2): step S2 is the successor of step S1
11
12 % actionstep: can push at any step but the final one
13 actionstep(S) :- next(S,S1).
14
15 % utility predicates: left and bottom
16 left(L1,L2) :- right(L2,L1).
17 bottom(L1,L2) :- top(L2,L1).
18
19 % utility predicates: adjacent
20 adj(L1,L2) :- right(L1,L2).
21 adj(L1,L2) :- left(L1,L2).
22 adj(L1,L2) :- top(L1,L2).
23 adj(L1,L2) :- bottom(L1,L2).
24
25 % identify locations
26 location(L) :- adj(L,_).
27
28 % Initial configuration.
29 box_step(B,F) :- box(B), initial_step(F).
30 sokoban_step(S,F) :- sokoban(S), initial_step(F).
31
32 % push(B,D,B1,S):
33 % At actionstep S push box at location B in direction D (right, left, up, down)
34 % until location B1.
35 % The sokoban must be able to get to the location "before" B in order to push
36 % the box, also there should not be any boxes between B and B1 (and also not
37 % on B1 itself at step S.
38 push(B,right,B1,S) v -push(B,right,B1,S) :-
39 reachable(L,S), right(L,B), box_step(B,S), pushable_right(B,B1,S), good_pushlocation(B1), actionstep(S).
40 push(B,left,B1,S) v -push(B,left,B1,S) :-
41 reachable(L,S), left(L,B), box_step(B,S), pushable_left(B,B1,S), good_pushlocation(B1), actionstep(S).
42 push(B,up,B1,S) v -push(B,up,B1,S) :-
43 reachable(L,S), top(L,B), box_step(B,S), pushable_top(B,B1,S), good_pushlocation(B1), actionstep(S).
44 push(B,down,B1,S) v -push(B,down,B1,S) :-
45 reachable(L,S), bottom(L,B), box_step(B,S), pushable_bottom(B,B1,S), good_pushlocation(B1), actionstep(S).
46
47 % reachable(L,S):
48 % Identifies locations L which are reachable by the sokoban at step S.
49 reachable(L,S) :- sokoban_step(L,S).
50 reachable(L,S) :- reachable(L1,S), adj(L1,L), not box_step(L,S).
51
52 % pushable_right(B,D,S):
53 % Box at B can be pushed right until D at step S.
54 % Analogous for left, top, bottom.
55 pushable_right(B,D,S) :- box_step(B,S), right(B,D), not box_step(D,S), actionstep(S).
56 pushable_right(B,D,S) :- pushable_right(B,D1,S), right(D1,D), not box_step(D,S).
57 pushable_left(B,D,S) :- box_step(B,S), left(B,D), not box_step(D,S), actionstep(S).
58 pushable_left(B,D,S) :- pushable_left(B,D1,S), left(D1,D), not box_step(D,S).
59 pushable_top(B,D,S) :- box_step(B,S), top(B,D), not box_step(D,S), actionstep(S).
60 pushable_top(B,D,S) :- pushable_top(B,D1,S), top(D1,D), not box_step(D,S).
61 pushable_bottom(B,D,S) :- box_step(B,S), bottom(B,D), not box_step(D,S), actionstep(S).
62 pushable_bottom(B,D,S) :- pushable_bottom(B,D1,S), bottom(D1,D), not box_step(D,S).
63
64 % The sokoban is at a new location after a push and no longer at its original
65 % position.
66 sokoban_step(L,S1) :- push(_,right,B1,S), next(S,S1), right(L,B1).
67 sokoban_step(L,S1) :- push(_,left,B1,S), next(S,S1), left(L,B1).
68 sokoban_step(L,S1) :- push(_,up,B1,S), next(S,S1), top(L,B1).
69 sokoban_step(L,S1) :- push(_,down,B1,S), next(S,S1), bottom(L,B1).
70 -sokoban_step(L,S1) :- push(_,_,_,S), next(S,S1), sokoban_step(L,S).
71
72 % Also the box_step has moved after having been pushed.
73 box_step(B,S1) :- push(_,_,B,S), next(S,S1).
74 -box_step(B,S1) :- push(B,_,_,S), next(S,S1).
75
76 % Inertia: Boxes and the sokoban usually remain where they are.
77 box_step(LB,S1) :- box_step(LB,S), next(S,S1), not -box_step(LB,S1).
78 sokoban_step(LS,S) :- sokoban_step(LS,S), next(S,S1), not -sokoban_step(LS,S1).
79
80 % Don't push two different boxes in one step.
81 :- push(B,_,_,S), push(B1,_,_,S), B != B1.
82 % Don't push a box in different directions in one step.
83 :- push(B,D,_,S), push(B,D1,_,S), D != D1.
84 % Don't push a box onto different locations in one step.
85 :- push(B,D,B1,S), push(B,D,B11,S), B1 != B11.
86
87 % Avoid pushing boxes into dead ends. There should be a location to the left
88 % and right or to top and bottom. Otherwise the box cannot be taken out again,
89 % for instance from corners. Obviously if the location is a target, these
90 % restrictions do not apply, as the box may remain there forever.
91 good_pushlocation(L) :- right(L,_), left(L,_).
92 good_pushlocation(L) :- top(L,_), bottom(L,_).
93 good_pushlocation(L) :- solution(L).
94
95 final_step(S) :- step(S), not no_final_step(S).
96 no_final_step(S) :- next(S,S1).
97
98 initial_step(S) :- step(S), not no_initial_step(S).
99 no_initial_step(S) :- next(S1,S).
100
101 push_happens(S) :- push(_,_,_,S).
102 push_missing :- actionstep(S), not push_happens(S).
103 :- push_missing.
104 solution_notfound :- solution(L), final_step(S), not box_step(L,S).
105 :- solution_notfound.
Attached Files
You are not allowed to attach a file to this page.