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
| include "laba.inc"
domains
kletka=c(integer,integer)
list=kletka*
list1=list*
list2=integer*
predicates
state(list)
mandist(kletka,kletka,integer)
poisk(list,list1)
diff(integer,integer,integer)
goal_state(list)
select(list1,list,integer,list)
generate(list,list1,list1)
member(list,list1)
member(integer,list2)
score(kletka,kletka,integer)
totdist(list,list,integer)
seq(list,integer)
seq(list,kletka,integer)
swap(list,list,kletka,kletka)
s(list,list)
h(list,integer)
invert(list1,list1)
invert(list1,list1,list1)
writeresult(list1)
write_pos(list)
num(kletka,list,integer)
run
clauses
goal_state([c(2,2),c(1,3),c(2,3),c(3,3),c(3,2),c(3,1),c(2,1),c (1,1),c(1,2)]).
state([c(3,3),c(1,3),c(2,2),c(2,3),c(3,2),c(3,1),c(2,1),c (1,1),c(1,2)]).
poisk(S,R):- goal_state(S),invert(R,R1),writeresult(R1),nl.
poisk (S, R) :-
generate (S,[],R1),
select(R1,S1,1000,S),
poisk( S1, [S1|R]).
generate (S,R,RR):-
s(S,S1),
not(member(S1,R)),
generate(S,[S1|R],RR).
generate(_,R,R).
mandist ( c(X1,Y1), c(X2,Y2), D):-
diff(X1,Y1,DX),diff(X2,Y2,DY),
D=DX+DY.
diff(X,Y,Z):-Z=X-Y,Z>0;
Z=Y-X.
select([],SS,_,SS):- !.
select([S1|T],SS,N,_S):-
h(S1,H),
H<N,
select(T,SS,H,S1).
select([_|T],SS,N,S):-
select(T,SS,N,S).
totdist([],[],0).
totdist([S1|T],[S|T1],SS):-
totdist(T,T1,T2),
mandist(S1,S,M),SS=M+T2.
score(c(2,2),_,1).
score(c(1,3),c(2,3),0).
score(c(2,3),c(3,3),0).
score(c(3,2),c(3,1),0).
score(c(2,1),c(1,1),0).
score(c(1,1),c(1,2),0).
score(c(1,2),c(1,3),0).
score(_,_,2).
h([_E|S1],H):-goal_state([_E1|S]),
totdist(S1,S,T),
seq(S1,SS),
H=T+SS*3.
seq([First|Tail],S):-
seq([First|Tail],First,S).
seq([X,Y|Tail],First,S):-
score(X,Y,K),
seq([Y|Tail],First,S1),
S=S1+K.
seq([Lost],First,S):-
score(Lost,First,S).
[COLOR=red]s([Empty|Tail1],[Node|Tail2]):-
swap(Tail1,Tail2,Empty,Node).
swap([Node|Tail],[Empty|Tail],Empty,Node):-
mandist(Node,Empty,1).
swap([H|Tail1],[H|Tail2],Empty,Node):-
swap(Tail1,Tail2,Empty,Node).[/COLOR]
member(Name,[Name|_]).
member(Name,[_|Tail]):-member(Name,Tail).
write_pos(S):-
member(Y,[3,2,1]),nl,
member(X,[1,2,3]),
num(c(X,Y),S,N),
write(N," "),
fail.
write_pos(_):-nl,nl.
num(S,[S|_],0):-!.
num(S,[_|R],N):-
num(S,R,N1),N=N1+1.
writeresult([]):-!.
writeresult([S|R]):-
write_pos(S),writeresult(R).
invert(X,Y):-invert(X,[],Y).
invert([],L,L):-!.
invert([H|T1],T2,T3):-
invert(T1,[H|T2],T3).
run :- state(S),
poisk(S,[S]).
goal
run. |
:
(
