Bad algorithm?
Author Message
Bad algorithm?

Hello, everybody!

Here's a question: Further is written a program, that supposed to play
"horse move":
you've got a board, like a chess board, and a horse in the corner. it has
to visit all the squares of the board (once). The problem is, that
when I give it a goal

horse_route([point(1,1) | Tail]), list_length(Tail,10).

It says "Out of trail during execution", not to mention list of
length 63 (which would mean: visit ALL the squares on the board).

Using options -h xxxx -l xxxx -g xxxx (I use C-Prolog) doesn't
help much. Maybe there is a way to increase the efficiency of this
algorithm?

horse_route([]).
horse_route([point(_,_)]).
horse_route([point(Xold,Yold),point(Xnew,Ynew) | Tail]) :-
horse_move(Xold,Yold,Xnew,Ynew),
horse_route([point(Xnew,Ynew) | Tail]),
not(list_member(point(Xold,Yold),Tail)).

list_length([],0).
list_length([_ | Tail], N) :-
list_length(Tail,N1),
N is N1+1.

list_member(X,[X | _]).
list_member(X,[Y | Tail]) :-
list_member(X,Tail).

horse_move( OldRow , OldColumn, NewRow , NewColumn) :-
(d(DX,DY); d(DY,DX)),
NewRow is OldRow+DX,
NewColumn is OldColumn+DY,
on_board(NewRow),
on_board(NewColumn).

on_board(X) :-
X>0,
X<9.

d(2,1).
d(2,-1).
d(-2,1).
d(-2,-1).

--
DDD   I  M     M  AA
D  D  I  MM   MM  A A
D  D  I  M M M M  AAAA
DDD   I  M  M  M  A   A

Mon, 27 Jul 1998 03:00:00 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages

Powered by phpBB® Forum Software