%	N-queens program.
%	Written by Rowland Sammut.

%	To solve for 4x4 board type: "nq(4)!"

choose(X, [X | Y], Y).
choose(X, [H | T1], [H | T2]) :-  choose(X, T1, T2).

safe(U1, D1, [square(_, U, D) | Rest]) :-
	U1 /= U,
	D1 /= D,
	safe(U1, D1, Rest).
safe(_, _, []).

solve(Input, Output, [Row | R], Columns) :-
	choose(Col, Columns, C),
	Up is   Row - Col,
	Down is Row + Col,
	safe(Up, Down, Input),
	solve([square(Col, Up, Down) | Input], Output, R, C).
solve(L, L, [], []).

print_board(N, [square(X, _, _) | L]) :-
	nl,
	nputs(' .', X - 1),
	prin(' Q'),
	nputs(' .', N - X),
	print_board(N, L).
print_board(N, []) :- nl.

inlist(1, L, [1 | L]).
inlist(X, L1, L2) :-  	X > 1,
			Y is X - 1,
			inlist(Y, [X | L1], L2).
	
queens(N, Solution) :-	inlist(N, [], L),
			solve([], Solution, L, L).

nq(N) :- queens(N, S), print_board(N, S), fail.
nq(_).
