-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsokoban.pl
134 lines (114 loc) · 4.89 KB
/
sokoban.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%% Author: Daniel Alvarez Castillo %%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/*************************************************************************************/
/* We assert the initial and final states. */
/*************************************************************************************/
% solve_problem(sokoban, X).
initial_state(sokoban, p(7,5,6)).
goal(8).
goal(9).
final_state(sokoban, p(_,X,Y)) :- goal(X), goal(Y), X \= Y.
/*************************************************************************************/
/* Now we implement our table of moves. */
/*************************************************************************************/
move(p(A1,BA1,BB1),m(A1,BA1,BB1,up,A2,BA2,BB1)) :-
BA1 is A1 - 3,
BA2 is BA1 - 3,
A2 is A1 - 3.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,up,A2,BA1,BB2)) :-
BB1 is A1 - 3,
BB2 is BB1 - 3,
A2 is A1 - 3.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,up,A2,BA1,BB1)) :-
A2 is A1 - 3.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,down,A2,BA2,BB1)) :-
BA1 is A1 + 3,
BA2 is BA1 + 3,
A2 is A1 + 3.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,down,A2,BA1,BB2)) :-
BB1 is A1 + 3,
BB2 is BB1 + 3,
A2 is A1 + 3.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,down,A2,BA1,BB1)) :-
A2 is A1 + 3.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,left,A2,BA2,BB1)) :-
A1 \= 4,
A1 \= 7,
BA1 is A1 - 1,
BA2 is BA1 - 1,
A2 is A1 - 1.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,left,A2,BA1,BB2)) :-
A1 \= 4,
A1 \= 7,
BB1 is A1 - 1,
BB2 is BB1 - 1,
A2 is A1 - 1.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,left,A2,BA1,BB1)) :-
A1 \= 4,
A1 \= 7,
A2 is A1 - 1.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,right,A2,BA2,BB1)) :-
A1 \= 3,
A1 \= 6,
BA1 is A1 + 1,
BA2 is BA1 + 1,
A2 is A1 + 1.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,right,A2,BA1,BB2)) :-
A1 \= 3,
A1 \= 6,
BB1 is A1 + 1,
BB2 is BB1 + 1,
A2 is A1 + 1.
move(p(A1,BA1,BB1),m(A1,BA1,BB1,right,A2,BA1,BB1)) :-
A1 \= 3,
A1 \= 6,
A2 is A1 + 1.
/*************************************************************************************/
/* We now implement the state update functionality. */
/*************************************************************************************/
update(p(A1,BA1,BB1),m(A1,BA1,BB1,_,A2,BA2,BB2),p(A2,BA2,BB2)).
/*************************************************************************************/
/* Implementation of the predicate that checks whether a state is legal */
/* according to the constraints imposed by the problem's statement. */
/*************************************************************************************/
legal(p(A,BA,BB)) :-
A >= 1,
A =< 9,
BA >= 1,
BA =< 9,
BB >= 1,
BB =< 9,
A \= BA,
A \= BB,
BA \= BB.
/*************************************************************************************/
/* A reusable depth-first problem solving framework. */
/*************************************************************************************/
/* The problem is solved is the current state is the final state. */
solve_dfs(Problem, State, _, []) :-
final_state(Problem, State).
/* To perform a state transition we follow the steps below: */
/* - We choose a move that can be applied from our current state. */
/* - We create the new state which results from performing the chosen move. */
/* - We check whether the new state is legal (i.e. meets the imposed constraints. */
/* - Next we check whether the newly produced state was previously visited. If so */
/* then we discard such a move, since we're most probably in a loop! */
/* - If all the above conditions are fulfilled, then we consolidate the chosen move */
/* and then we continue searching for the solution. Note that we have stored the */
/* newly created state for loop checking! */
solve_dfs(Problem, State, History, [Move|Moves]) :-
move(State, Move),
update(State, Move, NewState),
legal(NewState),
\+ member(NewState, History),
solve_dfs(Problem, NewState, [NewState|History], Moves).
/*************************************************************************************/
/* Solving the problem. */
/*************************************************************************************/
solve_problem(Problem, Solution) :-
initial_state(Problem, Initial),
solve_dfs(Problem, Initial, [Initial], Solution).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%