Ферзь находится на поле A1 шахматной доски. Необходимо найти замкнутый маршрут из 14 ходов, обеспечивающий прохождение всех полей доски. При этом любые поля допускается проходить более одного раза.
VP 7.2:
domains
yn = y();n().
cell = c(integer,integer,yn).
cells = cell*.
class facts
i : unsigned:=0.
class predicates
gen_desk : (integer,integer) -> cells Desk determ(i,i).
direction : (integer*) -> integer procedure(i).
isEnd : (cells) determ (i).
nCoord : (integer,integer,integer,integer,integer) determ (i,i,o,o,i).
broken : (integer,integer,integer*,integer*,cells) nondeterm (i,i,o,i,i).
line : (integer,integer,integer,integer,integer,cells,cells,integer) multi (i,i,o,o,i,i,o,o).
mark : (integer,integer,cells,cells,integer) determ (i,i,i,o,o).
clauses
gen_desk(_,0)=[]:-!.
gen_desk(0,J)=gen_desk(8,J-1):-J>0,!.
gen_desk(I,J)=[c(I,J,n)|gen_desk(I-1,J)]:-I>0.
direction([])=1:-!.
direction([1])=3:-!.
direction([I|_])=(I+3) mod 8.
isEnd([]):-!.
isEnd([c(_,_,y)|Desk]):-isEnd(Desk).
nCoord(X,Y,X+1,Y-1, 0):-X<8,Y>1,!.
nCoord(X,Y,X+1,Y,1):-X<8,!.
nCoord(X,Y,X+1,Y+1,2):-X<8,Y<8,!.
nCoord(X,Y,X,Y+1,3):-Y<8,!.
nCoord(X,Y,X-1, Y+1,4):-X>1,Y<8,!.
nCoord(X,Y,X-1, Y,5):-X>1,!.
nCoord(X,Y,X-1, Y-1, 6):-X>1,Y>1,!.
nCoord(X,Y,X,Y-1, 7):-Y>1,!.
broken(1,1,[],_,Desk):-isEnd(Desk).
broken(X,Y,[X1,Y1|Broken],Dir,Desk):-NDir=direction(Dir),line(X,Y,X1,Y1,NDir,Desk,Desk1,L),L>2,i:=i+1,
broken(X1,Y1,Broken,[NDir|Dir],Desk1).
line(X,Y,X0,Y0,Dir,Desk,Desk0,I+J):-nCoord(X,Y,X1,Y1,Dir),mark(X1,Y1,Desk,Desk1,J),
line(X1,Y1,X0,Y0,Dir,Desk1,Desk0,I).
line(X,Y,X,Y,_,Desk,Desk,0).
mark(X,Y,[c(X,Y,n())|Desk],[c(X,Y,y())|Desk],1):-!.
mark(X,Y,[c(X,Y,y())|Desk],[c(X,Y,y())|Desk],0):-!.
mark(X,Y,[Cell|Desk],[Cell|Desk1],I):-mark(X,Y,Desk,Desk1,I).
run():-init(),
Desk=gen_desk(8,8),
broken(1,1,Broken,[],Desk),
write("\nСчётчик=",i,"\nПуть: ",[1,1|Broken]),
fail();
_=stdio::readChar().
SWI Prolog:
gen_desk(_,0,[]):-!.
gen_desk(0,J,D):- J>0, J1 is J - 1, gen_desk(8, J1, D),!.
gen_desk(I,J,[c(I,J,n) | D]) :- I>0, I1 is I-1, gen_desk(I1, J, D).
direction([],1):-!.
direction([1],3):-!.
direction([I|_],I1):- I1 is (I+3) mod 8.
isEnd([]):-!.
isEnd([c(_,_,y)|Desk]):-isEnd(Desk).
nCoord(X,Y,X1,Y1, 0):-X<8,Y>1,X1 is X+1, Y1 is Y - 1,!.
nCoord(X,Y,X1,Y,1):-X<8,X1 is X+1,!.
nCoord(X,Y,X1,Y1,2):-X<8,Y<8,X1 is X+1, Y1 is Y+1,!.
nCoord(X,Y,X,Y1,3):-Y<8,Y1 is Y+1,!.
nCoord(X,Y,X1, Y1,4):-X>1,Y<8,X1 is X-1, Y1 is Y+1,!.
nCoord(X,Y,X1, Y,5):-X>1,X1 is X-1,!.
nCoord(X,Y,X1, Y1, 6):-X>1,Y>1,X1 is X-1, Y1 is Y-1,!.
nCoord(X,Y,X,Y1, 7):-Y>1,Y1 is Y-1,!.
broken(1,1,[],_,Desk):-isEnd(Desk).
broken(X,Y,[X1,Y1|Broken],Dir,Desk):-
direction(Dir,NDir),
line(X,Y,X1,Y1,NDir,Desk,Desk1,L),
L>2,
broken(X1,Y1,Broken,[NDir|Dir],Desk1).
line(X,Y,X0,Y0,Dir,Desk,Desk0,IJ):-
nCoord(X,Y,X1,Y1,Dir),
mark(X1,Y1,Desk,Desk1,J),
line(X1,Y1,X0,Y0,Dir,Desk1,Desk0,I),
IJ is I + J.
line(X,Y,X,Y,_,Desk,Desk,0).
mark(X,Y,[c(X,Y,n)|Desk],[c(X,Y,y)|Desk],1):-!.
mark(X,Y,[c(X,Y,y)|Desk],[c(X,Y,y)|Desk],0):-!.
mark(X,Y,[Cell|Desk],[Cell|Desk1],I):-mark(X,Y,Desk,Desk1,I).
run :-
gen_desk(8,8,Desk),
broken(1,1,Broken,[],Desk),
format('Путь: ~w~n', [[1,1|Broken]]),
fail;
write('Готово.').
Результат:
?- run.
Путь: [1, 1, 8, 1, 8, 8, 2, 2, 8, 2, 2, 8, 2, 4, 6, 8, 3, 8, 7, 4, 7, 8, 2, 3, 6, 3, 1, 8, 1, 1]
Путь: [1, 1, 8, 1, 8, 8, 3, 3, 7, 3, 2, 8, 2, 4, 6, 8, 3, 8, 7, 4, 7, 8, 1, 2, 7, 2, 1, 8, 1, 1]
Готово.
true.
|
Главная
Каталог файлов
