% dimension(3, 4).
% instead of hard coded dimension(M, N), use read_integer/asserta/retract
go :-  write('Enter the number of rows of the chessboard: '),
    read_integer(M),
    write('Enter the number of columns of the chessboard: '),
    read_integer(N),
    TermChessboardSize =.. [dimension, M, N],
    asserta(TermChessboardSize),
    sol(X),
    write(X), nl, nl,
    display_board(X),
    retract(TermChessboardSize).

% sol(X) succeeds if X is a solution of the Knights tour for a board 
% of dimension(M, N).    
sol(X) :-
    dimension(M, N),             % get the dimension of the board
    generate_positions(M, N, L), % generate all positions of the board.
    select(1/1, L, L1),          % remove the initial position 1/1.
    knight(1/1, L1, X).          % look for |L| moves starting from 1/1

% knight(T, P, L, S) succeeds if a knight can visit all positions of L once 
% from the current position P consecutively, 
% and S is the list of positions in the order of moves (S is a permutation of [P|L]).
knight(P, [], [P]) :- !.         % L = []
knight(X/Y, L, [X/Y | R]) :-     % |L| > 0
    select(X1/Y1, L, L1),
    move(X, Y, X1, Y1),
    knight(X1/Y1, L1, R).
    
% move(X, Y, X1, Y1) succeeds if a knight can move from X/Y to X1/Y1.
move(X, Y, X1, Y1) :- X>2, Y>1, X1 is X-2, Y1 is Y-1.
move(X, Y, X1, Y1) :- X>2, dimension(_, N), Y<N, X1 is X-2, Y1 is Y+1.
move(X, Y, X1, Y1) :- X>1, Y>2, X1 is X-1, Y1 is Y-2.
move(X, Y, X1, Y1) :- X>1, dimension(_, N), Y<N-1, X1 is X-1, Y1 is Y+2.
move(X, Y, X1, Y1) :- dimension(M, _), X<M, Y>2, X1 is X+1, Y1 is Y-2.
move(X, Y, X1, Y1) :- dimension(M, N), X<M, Y<N-1, X1 is X+1, Y1 is Y+2.
move(X, Y, X1, Y1) :- dimension(M, _), X<M-1, Y>1, X1 is X+2, Y1 is Y-1.
move(X, Y, X1, Y1) :- dimension(M, N), X<M-1, Y<N, X1 is X+2, Y1 is Y+1.

% generate(M, N, L) succeeds if L is a list of pairs x/y, 1<=x<=M, 1<=y<=N.
generate_positions(M, N, L) :-
    gen_list(1, M, X),
    gen_list(1, N, Y),
    gen_pairs(X, Y, L).

% gen_list( X, N, R) succeeds if R = [X, X+1, X+2, ..., N].
gen_list( X, N, []) :- X>N, !.    
gen_list( X, N, [X | Res]) :- Y is X+1, gen_list( Y, N, Res).

% gen_pairs(X, Y, L) succeeds if X=[a1, ..., am], Y=[b1, ..., bn] and L = [a1/b1, am/bn]
gen_pairs( [], _, []).
gen_pairs( [A|X], Y, Z) :- pairs(A, Y, R), gen_pairs(X, Y, Res), append(R, Res, Z).

% pairs(X, Y, R) succeeds if Y=[b1, ..., bn] and R=[X/b1, ..., X/bn].
pairs(_, [], []).
pairs(X, [Y | L], [X/Y | R]) :- pairs(X, L, R).


% display_board(X) displays X as a matrix.
display_board(X) :-
    dimension(M, N),              % get the dimension of the board
    T is M*N,
    generate_code(1, X, N, T, C), % generate all the codes of positions.
    sort(C, S),
    print_board(S, N, T).

generate_code(_, [], _, _, []).
generate_code(A, [X/Y | L], N, T, [Z|R]) :- 
    Z is (X*N+Y)*T+A, B is A+1,
    generate_code(B, L, N, T, R).

print_board([], _, _) :- !, nl.
print_board(L, N, T) :-
    print_row(L, N, T, R),
    write('|'), nl,
    print_board(R, N, T).

print_row(L, 0, _, L).
print_row([X|L], N, T, R) :-
    N>0, N1 is N-1,
    Y is (X-1) rem T + 1, 
    write_space(Y), 
    print_row(L, N1, T, R).

write_space(Y) :- (Y<10), !, write('| '), write(Y).
write_space(Y) :- write('|'), write(Y).
