% This file  implements a solution to the  N queens problem, using the
% same constraint solving approach as the code found on wikipedia at:
%
% http://en.wikipedia.org/wiki/Eight_queens_puzzle
%
% The main difference is  the generation of   the list of  N variables
% representing the  rows  of the queens.  GNU  Prolog has an optimized
% interface to constraint solving  over finite domains, this file only
% makes use of native Mercury constructs (no calls to C).

:- module queens.

:- interface.

:- import_module io.

:- pred main(io :: di, io :: uo) is det.

:- implementation.

:- import_module int, list, set, solutions, string, time.

main(! IO) :-
    command_line_arguments(Args, ! IO),
    (Args = [StringNum], to_int(StringNum, N)
    ->
        solutions((pred (S :: out)) is nondet :- queens(N, S), Q),
        clock(R, ! IO),
        foldl(print_nl, Q, ! IO),
        length(Q, Nq),
        format("%u solutions: %u seconds", [i(Nq), i(R / clocks_per_sec)], L),
        print(L, ! IO), nl(! IO),
        flush_output(! IO)
    ;
        true
    ).

:- pred print_nl(T :: in, io :: di, io :: uo) is det.
print_nl(X) --> print(X), nl.

% The reasoning behind  this predicate is  as follows: if the queen in
% column A is on the same diagonal as the  queen in column B, then the
% difference between their row numbers is 1 (A1 and B2 for example, or
% A4 and B3). If the queen  in column A and  the queen on column C are
% on the same diagonal, then the difference  between their row numbers
% is 2. It follows  that if N is  the distance between the columns  (1
% for A and B, 2 for A and C), two queens on  two columns separated by
% this distance share a diagonal  iff the difference between their row
% numbers is also N (using absolute values).
%
% The free_queens predicate first  calls not_on_same_diagonal with all
% columns,    then   with  all   but   the   first and    so   on. The
% not_on_same_diagonal  checks  only   the first  column it   receives
% against the following columns in the list. This is enough because "X
% is on the same diagonal as Y" is a symmetric property.

:- pred not_on_same_diagonal(int :: in, list(int) :: in, int :: in) is semidet.
not_on_same_diagonal(_, [], _).
not_on_same_diagonal(X, [Y | Ys], N) :-
    X \= Y + N,
    X \= Y - N,
    not_on_same_diagonal(X, Ys, N + 1).

:- pred free_queens(list(int) :: in) is semidet.
free_queens([]).
free_queens([X | Xs]) :- not_on_same_diagonal(X, Xs, 1), free_queens(Xs).

% Generate a list  of N elements whose  values are  integers between 1
% and M. These  elements represent the rows  of the queens to place on
% the board.

:- pred square_list(int :: in, int :: in, list(int) :: out) is nondet.
square_list(N, M, L) :-
    N > 0 -> member(X, 1 .. M), square_list(N - 1, M, L0), L = [X | L0]
    ; L = [].

:- pred all_different(list(int) :: in) is semidet.
all_different([]).
all_different([X | Xs]) :- not member(X, Xs), all_different(Xs).

% The solutions of this predicate are the solutions  to the problem of
% placing N chess queens on a N x N chess board.  To place N queens on
% a N x N board, there must be exactly one queen on each column of the
% board, so one  solution can be  represented as a list whose  indexes
% are the columns of the board  and whose values  are the row on which
% to place the  queens. Each solution is a  such list of length N. For
% example, on an 8 x 8 (classical) chess board, a list [1, 5, 8, 6, 3,
% 7, 2, 4] means that the queens are placed on A1, B5, C8, D6, E3, F7,
% G2 and H4.
%
% Furthermore,  in a   solution, all  values   in  the list  must   be
% different, since  no two queens may  be on the   same row. Given the
% all_different predicate, there only   remains to check that  no  two
% queens share a diagonal, which is done by the predicate free_queens.

:- pred queens(int :: in, list(int) :: out).
queens(N, L) :-
    square_list(N, N, L),
    all_different(L),
    free_queens(L).

:- end_module queens.
