% 9-queens program

#ifndef	MERCURY

#include "harness.cpp"

benchmark(Data, Out) :-
	queen(Data, Out).

#else

#if	defined(CONSTRAINT_PROPAGATION)
:- module cqueens.
#else
:- module queens.
#endif

:- interface.

:- import_module list, int, io, printlist.

:- pred benchmark(list(int)).
:- mode benchmark(out) is nondet.

:- pred main(io__state, io__state).
:- mode main(di, uo) is multidet.

:- implementation.

benchmark(Out) :-	
	data(Data),
	queen(Data, Out).

main -->
	( { benchmark(Out) } ->
		print_list(Out)
	;
		io__write_string("no solutions\n")
	).

:- pred data(list(int)).
:- mode data(out) is det.

:- pred queen(list(int), list(int)).
:- mode queen(in, out) is nondet.

#if	defined(CONSTRAINT_PROPAGATION)
:- pred queen_2(list(int), list(int), list(int)).
:- mode queen_2(in, in, out) is nondet.
#endif

#ifdef	POLYMORPHISM
:- pred qperm(list(T), list(T)).
:- mode qperm(in, out) is nondet.

:- pred qdelete(T, list(T), list(T)).
:- mode qdelete(out, in, out) is nondet.
#else
:- pred qperm(list(int), list(int)).
:- mode qperm(in, out) is nondet.

:- pred qdelete(int, list(int), list(int)).
:- mode qdelete(out, in, out) is nondet.
#endif

:- pred safe(list(int)).
:- mode safe(in) is semidet.

:- pred nodiag(int, int, list(int)).
:- mode nodiag(in, in, in) is semidet.

#endif

#ifdef AQUARIUS_DECLS

#if	defined(CONSTRAINT_PROPAGATION)
:- mode((queen_2(L1, L2, L3) :-
 		ground(L1),
		deref(L1),
		list(L1),
		ground(L2),
		deref(L2),
		list(L2)
	)).
#endif

:- mode((queen(D, L) :-
 		ground(D),
		deref(D),
		list(D)
	)).
:- mode((qperm(L1, L2) :-
 		ground(L1),
		deref(L1),
		list(L1)
	)).
:- mode((qdelete(L1, L2, L3) :-
 		ground(L2),
		deref(L2),
		list(L2)
	)).
:- mode((safe(L1) :-
 		ground(L1),
		deref(L1),
		list(L1)
	)).
:- mode((nodiag(A1, A2, L3) :-
		ground(A1),
		ground(A2),
		ground(L3),
		deref(L3),
		list(L3)
	)).

#endif

data([1,2,3,4,5,6,7,8,9]).

#if	defined(CONSTRAINT_PROPAGATION)

queen(Data, Out) :-
	queen_2(Data, [], Out).

queen_2([], _, []).
queen_2(L, History, [Q|M]) :-
	L = [_|_],
	qdelete(Q, L, L1),
	nodiag(Q, 1, History),
	queen_2(L1, [Q|History], M).

#elif	defined(COROUTINING)

queen(Data, Out) :-
	safe(Out),
	qperm(Data, Out).

#else

queen(Data, Out) :-
	qperm(Data, Out),
	safe(Out).

#endif

qperm([], []).
qperm([X|Y], K) :-
	qdelete(U, [X|Y], Z),
	K = [U|V],
	qperm(Z, V).

qdelete(A, [A|L], L).
qdelete(X, [A|Z], [A|R]) :-
	qdelete(X, Z, R).

#ifdef NUPROLOG_DECLS
:- safe(X) when X.
#endif

#ifdef SICSTUS_DECLS
:- block safe(-).
#endif

safe([]).
safe([N|L]) :-
	nodiag(N, 1, L),
	safe(L).

#ifdef NUPROLOG_DECLS
:- nodiag(_, _, X) when X.
#endif

#ifdef SICSTUS_DECLS
:- block nodiag(?, ?, -).
#endif

#ifdef	MERCURY

nodiag(_, _, []).
nodiag(B, D, [N|L]) :-
	NmB is N - B,
	D \= NmB,
	BmN is B - N,
	D \= BmN,
	D1 is D + 1,
	nodiag(B, D1, L).

#else

nodiag(_, _, []).
nodiag(B, D, [N|L]) :-
	D =\= N - B,
	D =\= B - N,
	D1 is D + 1,
	nodiag(B, D1, L).

#endif