Anonymous user
Solve a Hopido puzzle: Difference between revisions
Added Prolog
m (C# added a remark.) |
(Added Prolog) |
||
Line 1,361:
. . . 24 . . .
solution found in 67702 tries (0.09s)
</pre>
=={{header|Prolog}}==
This is a pure prolog implementation (no cuts,etc..), the only libary predicate used is select/3 witch is pure.
<lang prolog>hopido(Grid,[C|Solved],Xs,Ys) :-
select(C,Grid,RGrid),
solve(RGrid,C,Solved,Xs,Ys).
solve([],_,[],_,_).
solve(Grid,p(X,Y),[p(X1,Y1)|R],Xs,Ys) :-
valid_move(X,Y,Xs,Ys,X1,Y1),
select(p(X1,Y1),Grid,NextGrid),
solve(NextGrid,p(X1,Y1),R,Xs,Ys).
valid_move(X,Y,Xs,_,X1,Y) :- j3(X,X1,Xs). % right (3,0)
valid_move(X,Y,Xs,_,X1,Y) :- j3(X1,X,Xs). % left (-3,0)
valid_move(X,Y,_,Ys,X,Y1) :- j3(Y,Y1,Ys). % up (0,3).
valid_move(X,Y,_,Ys,X,Y1) :- j3(Y1,Y,Ys). % down (0,-3).
valid_move(X,Y,Xs,Ys,X1,Y1) :- j2(X,X1,Xs), j2(Y,Y1,Ys). % up-right (2,2).
valid_move(X,Y,Xs,Ys,X1,Y1) :- j2(X1,X,Xs), j2(Y,Y1,Ys). % up-left (-2,2).
valid_move(X,Y,Xs,Ys,X1,Y1) :- j2(X1,X,Xs), j2(Y1,Y,Ys). % down-left (-2,-2).
valid_move(X,Y,Xs,Ys,X1,Y1) :- j2(X,X1,Xs), j2(Y1,Y,Ys). % down-right (2,-2).
j2(O,N,[O,_,N|_]).
j2(O,N,[_|T]) :- j2(O,N,T).
j3(O,N,[O,_,_,N|_]).
j3(O,N,[_|T]) :- j3(O,N,T).</lang>
To test send in a list of p/2 terms that represent points that can be hopped to (order is not important).
The grid coords can be anything so need to specify the valid coordinates as a list (in this case numbers between 0 and 6).
<lang prolog>puzzle([
p(1,0),p(2,0) ,p(4,0),p(5,0),
p(0,1),p(1,1),p(2,1),p(3,1),p(4,1),p(5,1),p(6,1),
p(0,2),p(1,2),p(2,2),p(3,2),p(4,2),p(5,2),p(6,2),
p(1,3),p(2,3),p(3,3),p(4,3),p(5,3),
p(2,4),p(3,4),p(4,4),
p(3,5)
]).
test :-
puzzle(P),
XYs = [0,1,2,3,4,5,6],
hopido(P,S,XYs,XYs),
maplist(writeln,S).</lang>
{{out}}
<pre>
?- time(test).
p(1,0)
p(4,0)
p(4,3)
p(1,3)
p(3,5)
p(5,3)
p(5,0)
p(2,0)
p(4,2)
p(1,2)
p(3,4)
p(5,2)
p(2,2)
p(4,4)
p(6,2)
p(3,2)
p(0,2)
p(2,4)
p(2,1)
p(5,1)
p(3,3)
p(1,1)
p(4,1)
p(2,3)
p(0,1)
p(3,1)
p(6,1)
% 356,635 inferences, 0.062 CPU in 0.081 seconds (78% CPU, 5715268 Lips)
true
</pre>
| |||