% Knight tour problem for a NxN board % % Given an NxN chess board and a knight standing at pos(Row,Col), % print out a sequence of knight's moves that pass through % every cell on the board exactly once. The last cell of the tour % may or may not coincide with the starting cell: the tour does not % have to be closed. % % With every move, a knight covers three cells on the board, not % counting the initial cell. Therefore, if a knight is to % visit every cell exactly once (the end and the starting positions % being different), then it must hold 1+3*k = N*N. Here k is the % number of knight's moves. If the starting and the ending positions % are the same, then 1+3*k = N*N+1. % Therefore, the open tour problem can have a solution only if % N*N-1 is divisible by three. For example, 4x4, 5x5, 7x7, 8x8 % boards may have open tour solutions. % The closed-tour solution is plausible only on boards where % N is divisible by 3. A 3x3 board however does not allow any % solution as the central cell is obviously beyond knight's reach. % The knight_tour(N,Pos) predicate below tries to solve the open % tour problem for an NxN board. The predicate can be back-tracked % to find another solution if exists. % For example, % knight_tour(4,pos(0,1)). % found solution % Board of 4 dim % 3: 8 7 6 5 % 2: 9 10 11 4 % 1: 14 13 12 3 % 0: 15 0 1 2 % yes % The number in a cell is that cell's positions in a tour.The % tour starts at the cell marked 0 and continues to the cell % marked 1, 2, 3...15. % knight_tour(5,pos(0,1)). % No solution % knight_tour(5,pos(0,0)). % % found solution % Board of 5 dim % 4: 16 17 18 19 24 % 3: 15 14 13 20 23 % 2: 2 3 12 21 22 % 1: 1 4 11 10 9 % 0: 0 5 6 7 8 % The code below can be modified to print out all _closed_ tours % starting from a given position -- not necessarily complete tours % of the board. The latter may exist only if N is divisible by 3 and % is at least 6. % This code demonstrates an implementation of a Matrix in Prolog, % as a list of lists. The code shows off "updating" of matrix elements % as well as back-tracking, undoing of the "updates". The word "update" % is quoted above because Prolog of course does not permit % mutation of values. % $Id$ % The current configuration is maintained by a term % board(N,C,Cmax,Rows) % % where % N is the size of the board % C is the current counter (enumerates the path in knight's tour) % The starting cell on the board has the counter of 0 % the last-but-one cell has the counter Cmax % Cmax = N*N, the max value assigned to the counter plus 1 % Rows is the list of 'row's; the list has exactly N elements. % % A term row(RowIndex,Cells) -- an element of the list Rows above -- % describes one row of the board. RowIndex is the rows's index (0 through N-1) % and Cells is the list of cells (see below). % % A term cell(ColIndex,Counter) represents one cell on the board. % ColIndex is the cell's index within a row (0 through N-1), % Counter if bound represents this cell's place in the tour. If Counter % is not bound, the corresponding cell hasn't been traversed yet. % Given N, make an empty board. A deterministic predicate. make_board(N,board(N,0,Cmax,Rows)) :- !, Cmax is N*N, make_rows(0,N,[],Rows). make_rows(N,N,Rows,Rows) :- !. make_rows(I,N,Rows,Out) :- I1 is I+1, make_cells(N,[],Cells), make_rows(I1,N,[row(I,Cells)|Rows],Out). make_cells(0,Cells,Cells) :-!. make_cells(I,Cells,Out) :- I1 is I-1, make_cells(I1,[cell(I1,_)|Cells],Out). % A deterministic predicate to nicely print out the board. print_board(board(N,C,_,Rows)) :- !, nl, print('Board of '), print(N), print(' dim'), print_rows(Rows). print_rows([]) :- nl. print_rows([row(Index,Cells)|OtherRows]) :- nl, print(Index), print(': '), print_cells(Cells), print_rows(OtherRows). print_cells([cell(CellIndex,Counter)]) :- !, print_counter(Counter). print_cells([H|T]) :- !, print_cells([H]), print_cells(T). print_counter(C) :- integer(C), C >= 10, !, tab(1), print(C), tab(1). print_counter(C) :- integer(C), !, tab(2), print(C), tab(1). print_counter(C) :- print(' _ '). % test the above predicates... % ?- make_board(4,B), print_board(B). % pos(Row,Col) specifies a position of the knight (and identifies a cell) % The following deterministic predicate is to place the current counter to a given % position on the board. A new board with an incremented counter and a marked cell % is generated. % The predicate may fail if the position is already assigned a (different) counter, % that is, the position have already been traversed in a tour. % When C is already Cmax, we verify that the position to be marked is already marked % by 0 (that is, it is the beginning of the tour). If so, we print out the complete % solution. Otherwise, we fail. %mark_pos(board(N,Cmax,Cmax,Rows),pos(Rind,Cind),_) % :- !, % B = board(N,Cmax,Cmax,Rows), % mark_rows(B,Cmax,pos(Rind,Cind),Rows,_), nl, print('Found complete solution'), % print_board(B). mark_pos(board(N,C,Cmax,Rows),pos(Rind,Cind),board(N,C1,Cmax,RowsMarked)) :- !, mark_rows(board(N,C,Cmax,Rows),C,pos(Rind,Cind),Rows,RowsMarked),C1 is C+1. mark_rows(B,C,pos(Rind,Cind),[row(Rind,Cells)|T],[row(Rind,CellsMarked)|T]) :- !, mark_cells(B,C,Cind,Cells,CellsMarked). mark_rows(B,C,Pos,[H|T],[H|TMarked]) :- mark_rows(B,C,Pos,T,TMarked). mark_cells(B,C,Cind,[cell(Cind,C)|T],[cell(Cind,C)|T]) :- !. % Note, the ending position of Knight's move always has Counter being % an exact multiple of three. % Uncomment the following three lines to see all (partial) closed tours %mark_cells(B,C,Cind,[cell(Cind,0)|T],[cell(Cind,0)|T]) :- !, % CCheck is C mod 3, CCheck == 0, % print('Back to where we started'), print_board(B), !, fail. mark_cells(B,C,Cind,[H|T],[H|TMarked]) :- !, mark_cells(B,C,Cind,T,TMarked). % Verify marking of positions... % ?- make_board(2,B), mark_pos(B,pos(1,0),B1), mark_pos(B1,pos(1,1),B2), mark_pos(B2,pos(0,1),B3), mark_pos(B3,pos(0,0),B4), mark_pos(B4,pos(1,0),B5). % The main puzzle predicate % Call it with the dimension of the board and the starting position, eg % knight_tour(4,pos(0,1)). % Note only boards with N*N-1 divisible by three have complete solutions. knight_tour(N,Pos) :- make_board(N,BC), mark_pos(BC,Pos,B), knight_tour1(B,Pos). knight_tour1(B,PosStart) :- knight_move(B,PosStart,BEnd,PosEnd), % Uncomment the following to print out all the moves attempted. % print(PosStart), print(' => '), print(PosEnd), nl, knight_tour2(BEnd,PosEnd). knight_tour2(board(N,Cmax,Cmax,Rows),_) :- !, nl, print('found solution'), print_board(board(N,Cmax,Cmax,Rows)). knight_tour2(B,PosStart) :- knight_tour1(B,PosStart). %knight_tour1(_,_). % Movements of the Knight knight_move(B,PosStart,BEnd,PosEnd) :- move_2up(B,PosStart,B1,P1), move_1left(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_2up(B,PosStart,B1,P1), move_1right(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_2down(B,PosStart,B1,P1), move_1left(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_2down(B,PosStart,B1,P1), move_1right(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_1up(B,PosStart,B1,P1), move_2left(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_1up(B,PosStart,B1,P1), move_2right(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_1down(B,PosStart,B1,P1), move_2left(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_1down(B,PosStart,B1,P1), move_2right(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_2left(B,PosStart,B1,P1), move_1up(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_2left(B,PosStart,B1,P1), move_1down(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_2right(B,PosStart,B1,P1), move_1up(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_2right(B,PosStart,B1,P1), move_1down(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_1left(B,PosStart,B1,P1), move_2up(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_1left(B,PosStart,B1,P1), move_2down(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_1right(B,PosStart,B1,P1), move_2up(B1,P1,BEnd,PosEnd). knight_move(B,PosStart,BEnd,PosEnd) :- move_1right(B,PosStart,B1,P1), move_2down(B1,P1,BEnd,PosEnd). % Elementary movements of the Knight. We "update" the board after every move. move_2up(B,pos(RS,CS),BEnd,PosEnd) :- B = board(N,_,_,_), RE is RS + 2, RE < N, RM is RS + 1, mark_pos(B,pos(RM,CS),B1), mark_pos(B1,pos(RE,CS),BEnd), PosEnd = pos(RE,CS). move_2down(B,pos(RS,CS),BEnd,PosEnd) :- RE is RS - 2, RE >= 0, RM is RS - 1, mark_pos(B,pos(RM,CS),B1), mark_pos(B1,pos(RE,CS),BEnd), PosEnd = pos(RE,CS). move_1up(B,pos(RS,CS),BEnd,PosEnd) :- B = board(N,_,_,_), RE is RS + 1, RE < N, mark_pos(B,pos(RE,CS),BEnd), PosEnd = pos(RE,CS). move_1down(B,pos(RS,CS),BEnd,PosEnd) :- RS > 0, RE is RS - 1, mark_pos(B,pos(RE,CS),BEnd), PosEnd = pos(RE,CS). move_1left(B,pos(RS,CS),BEnd,PosEnd) :- CS > 0, CE is CS - 1, mark_pos(B,pos(RS,CE),BEnd), PosEnd = pos(RS,CE). move_1right(B,pos(RS,CS),BEnd,PosEnd) :- B = board(N,_,_,_), CE is CS + 1, CE < N, mark_pos(B,pos(RS,CE),BEnd), PosEnd = pos(RS,CE). move_2left(B,pos(RS,CS),BEnd,PosEnd) :- CE is CS - 2, CE >= 0, CM is CS - 1, mark_pos(B,pos(RS,CM),B1), mark_pos(B1,pos(RS,CE),BEnd), PosEnd = pos(RS,CE). move_2right(B,pos(RS,CS),BEnd,PosEnd) :- B = board(N,_,_,_), CE is CS + 2, CE < N, CM is CS + 1, mark_pos(B,pos(RS,CM),B1), mark_pos(B1,pos(RS,CE),BEnd), PosEnd = pos(RS,CE). % unknown(X,trace).