Hello People,
I am currently trying to write a knights tour program on a 5 x 5 chessboard that visits every square at least once. At the moment it only maps the path from 1 square to another and does not visit all squares on the board.What I am trying to get the knight to do is visit all the squares rather than map a path from one square to another.
I have tried to get the program to visit all the squares by using a list length that matches the number of squares visited by the knight on the board i.e. 25 on 5 x 5 board. Once it has visited all squares it will output the solution path on screen. Although at the moment it infinite loops and does not find a search result. I have also tried to do this using depth_first and breadth_first search and I am still having the same problems.
A copy of code I have got so far can be found below, any help you could give would be much appreciated:
/* **************************************************************
Simplified Knight's tour - In this simplified version of the knight's
tour, a knight's path is built between any two squares on the chess board.
The main predicate, path(X,Y), prints out a path between X and Y.
This version extends the initial representation
to a 5 x 5 grid, with the grid numbered as follows:
1 2 3 16 25
4 5 6 15 24
7 8 9 14 23
10 11 12 13 22
17 18 19 20 21
This version uses a recursive path/3 predicate, with the third
argument representing the list of squares visited along the path:
path(Start,End,List)
To run the program, type path(X,Y)
*************************************************************/
/* An exhaustive list of moves. These are moves for a 3 x 3 board */
move(2,9). move(2,7). move(3,4). move(3,8). move(4,9). move(4,3).
move(6,1). move(6,7). move(7,2). move(7,6). move(8,3). move(8,1).
move(9,2). move(9,4). move(1,6). move(1,8).
/* The additional moves for the 4 x 4 board */
move(2,15). move(3,14). move(4,11). move(5,10). move(5,12). move(5,14).
move(5,16). move(6,11). move(6,13). move(7,12). move(8,15). move(8,13).
move(9,10). move(9,16). move(10,5). move(10,9). move(11,4). move(11,6).
move(11,14). move(12,5). move(12,7). move(12,15). move(13,8). move(13,6).
move(14,11). move(14,5). move(14,3). move(15,12). move(15,8). move(15,2).
move(16,5). move(16,9).
/* The additional moves for the 5 x 5 board */
move(3,24). move(6,23). move(6,25). move(7,18). move(8,17). move(8,19).
move(9,18). move(9,20). move(9,22). move(9,24). move(10,19). move(11,20).
move(12,17). move(12,21). move(12,23). move(13,18). move(13,24). move(14,19).
move(14,21). move(14,25). move(15,22). move(16,23). move(17,8). move(17,12).
move(18,7). move(18,9). move(18,13). move(19,8). move(19,10). move(19,14).
move(19,22). move(20,9). move(20,11). move(20,23). move(21,12). move(21,14).
move(22,9). move(22,15). move(22,19). move(23,6). move(23,12). move(23,16).
move(23,20). move(24,3). move(24,9). move(24,13). move(25,6). move(25,14).
/*********** PROGRAM STARTS HERE ********************/
path(X,Y) :- path(X,Y,[X]). /* Build a path between X and Y by
calling path/3. */
path(Z,Z,L):- !,printlist(L),size(L,N), N = 25,nl, write(N). /* Base case: prints the solution */
path(X,Y,L):- move(X,Z), /* Recursive case: find a move from X to Z */
not(member(Z,L)), /* Cycle prevention */
path(Z,Y,[Z|L]). /* Find a path from Z to Y */
/* Print the list L in reverse order */
printlist([]).
printlist([H|T]) :- printlist(T),nl,write(H).
/* Basic utility predicates */
/*not(P):- call(P),!,fail,*/
/*not(P). */
/* member(H,[H|T]). */
/* member(M,[Y|T]) :- member(M,T). */
member(X,[X|T]).
member(X,[H|T]) :- member(X,T).
collect(L):-
retract(queue(X)),
!,
(X == bottom, !, L = []
; L = [X | Rest], collect(Rest)).
findall(X, Goal, Xlist):-
call(Goal),
assertz(queue(X)),
fail;
assertz(queue(bottom)),
collect(Xlist).
append([],L,L).
append([X|L1],L2,[X|L12]) :-
append(L1,L2,L12).
next_node(Current, Next,Path) :-
move(Current, Next),
write('next node: '), write(Next), nl,
not(member(Next,Path)).
depth_first(Start, Goal, Path) :-
depth_first1(Start, Goal, [Start], Path),
size(Path, N),
N < 25.
size([],0).
size([H|T],N):- size(T,N1),N is N1+1.
depth_first1(Current,Goal, _, [Goal]):-
size(Current,N),
/*size(Goal, N), */
N = 25.
depth_first1(Start, Goal, Visited, [Start | Path]) :-
Goal =< 25,
next_node(Start, Next_node, Visited),
write('Visited: '), write(Visited), nl,
depth_first1(Next_node, Goal, [Next_node|Visited], Path), !.
breadth_first(Start, Goal, Path) :-
breadth_first1([[Start]], Goal, Path).
breadth_first1([[Goal|Path]|_], Goal, [Goal|Path]).
breadth_first1([[Current|Trail]|OtherPaths], Goal, Path) :-
Goal =< 25,
findall([Next,Current|Trail], next_node(Current, Next, Trail), NewPaths),
write('New paths: '), write(NewPaths), nl,
append(OtherPaths, NewPaths, AllPaths),
breadth_first1(AllPaths, Goal, Path), !.
I am currently trying to write a knights tour program on a 5 x 5 chessboard that visits every square at least once. At the moment it only maps the path from 1 square to another and does not visit all squares on the board.What I am trying to get the knight to do is visit all the squares rather than map a path from one square to another.
I have tried to get the program to visit all the squares by using a list length that matches the number of squares visited by the knight on the board i.e. 25 on 5 x 5 board. Once it has visited all squares it will output the solution path on screen. Although at the moment it infinite loops and does not find a search result. I have also tried to do this using depth_first and breadth_first search and I am still having the same problems.
A copy of code I have got so far can be found below, any help you could give would be much appreciated:
/* **************************************************************
Simplified Knight's tour - In this simplified version of the knight's
tour, a knight's path is built between any two squares on the chess board.
The main predicate, path(X,Y), prints out a path between X and Y.
This version extends the initial representation
to a 5 x 5 grid, with the grid numbered as follows:
1 2 3 16 25
4 5 6 15 24
7 8 9 14 23
10 11 12 13 22
17 18 19 20 21
This version uses a recursive path/3 predicate, with the third
argument representing the list of squares visited along the path:
path(Start,End,List)
To run the program, type path(X,Y)
*************************************************************/
/* An exhaustive list of moves. These are moves for a 3 x 3 board */
move(2,9). move(2,7). move(3,4). move(3,8). move(4,9). move(4,3).
move(6,1). move(6,7). move(7,2). move(7,6). move(8,3). move(8,1).
move(9,2). move(9,4). move(1,6). move(1,8).
/* The additional moves for the 4 x 4 board */
move(2,15). move(3,14). move(4,11). move(5,10). move(5,12). move(5,14).
move(5,16). move(6,11). move(6,13). move(7,12). move(8,15). move(8,13).
move(9,10). move(9,16). move(10,5). move(10,9). move(11,4). move(11,6).
move(11,14). move(12,5). move(12,7). move(12,15). move(13,8). move(13,6).
move(14,11). move(14,5). move(14,3). move(15,12). move(15,8). move(15,2).
move(16,5). move(16,9).
/* The additional moves for the 5 x 5 board */
move(3,24). move(6,23). move(6,25). move(7,18). move(8,17). move(8,19).
move(9,18). move(9,20). move(9,22). move(9,24). move(10,19). move(11,20).
move(12,17). move(12,21). move(12,23). move(13,18). move(13,24). move(14,19).
move(14,21). move(14,25). move(15,22). move(16,23). move(17,8). move(17,12).
move(18,7). move(18,9). move(18,13). move(19,8). move(19,10). move(19,14).
move(19,22). move(20,9). move(20,11). move(20,23). move(21,12). move(21,14).
move(22,9). move(22,15). move(22,19). move(23,6). move(23,12). move(23,16).
move(23,20). move(24,3). move(24,9). move(24,13). move(25,6). move(25,14).
/*********** PROGRAM STARTS HERE ********************/
path(X,Y) :- path(X,Y,[X]). /* Build a path between X and Y by
calling path/3. */
path(Z,Z,L):- !,printlist(L),size(L,N), N = 25,nl, write(N). /* Base case: prints the solution */
path(X,Y,L):- move(X,Z), /* Recursive case: find a move from X to Z */
not(member(Z,L)), /* Cycle prevention */
path(Z,Y,[Z|L]). /* Find a path from Z to Y */
/* Print the list L in reverse order */
printlist([]).
printlist([H|T]) :- printlist(T),nl,write(H).
/* Basic utility predicates */
/*not(P):- call(P),!,fail,*/
/*not(P). */
/* member(H,[H|T]). */
/* member(M,[Y|T]) :- member(M,T). */
member(X,[X|T]).
member(X,[H|T]) :- member(X,T).
collect(L):-
retract(queue(X)),
!,
(X == bottom, !, L = []
; L = [X | Rest], collect(Rest)).
findall(X, Goal, Xlist):-
call(Goal),
assertz(queue(X)),
fail;
assertz(queue(bottom)),
collect(Xlist).
append([],L,L).
append([X|L1],L2,[X|L12]) :-
append(L1,L2,L12).
next_node(Current, Next,Path) :-
move(Current, Next),
write('next node: '), write(Next), nl,
not(member(Next,Path)).
depth_first(Start, Goal, Path) :-
depth_first1(Start, Goal, [Start], Path),
size(Path, N),
N < 25.
size([],0).
size([H|T],N):- size(T,N1),N is N1+1.
depth_first1(Current,Goal, _, [Goal]):-
size(Current,N),
/*size(Goal, N), */
N = 25.
depth_first1(Start, Goal, Visited, [Start | Path]) :-
Goal =< 25,
next_node(Start, Next_node, Visited),
write('Visited: '), write(Visited), nl,
depth_first1(Next_node, Goal, [Next_node|Visited], Path), !.
breadth_first(Start, Goal, Path) :-
breadth_first1([[Start]], Goal, Path).
breadth_first1([[Goal|Path]|_], Goal, [Goal|Path]).
breadth_first1([[Current|Trail]|OtherPaths], Goal, Path) :-
Goal =< 25,
findall([Next,Current|Trail], next_node(Current, Next, Trail), NewPaths),
write('New paths: '), write(NewPaths), nl,
append(OtherPaths, NewPaths, AllPaths),
breadth_first1(AllPaths, Goal, Path), !.