% N-Queens benchmark (uses length/2)
%
% Many Prolog systems provide length/2 as a built-in or in a standard library.
% This version is useful for performance comparisons because it avoids spending
% most runtime in a Prolog-level list length implementation on large N.
%
% Usage:
%   ?- queens_solutions(8, Count).
%   Count = 92.

range(N, List) :-
  range_(1, N, List).

range_(I, N, []) :-
  I > N.
range_(I, N, [I|Rest]) :-
  I =< N,
  I1 is I + 1,
  range_(I1, N, Rest).

select_(X, [X|Xs], Xs).
select_(X, [Y|Ys], [Y|Zs]) :-
  select_(X, Ys, Zs).

% A pruned generator: builds a permutation incrementally while checking safety
% so we avoid exploring the full N! search space.
queens(N, Qs) :-
  range(N, Cols),
  queens_(Cols, [], Qs).

queens_([], Qs, Qs).
queens_(Cols, Placed, Qs) :-
  select_(Q, Cols, Tail),
  safe_(Q, Placed, 1),
  queens_(Tail, [Q|Placed], Qs).

safe_(_, [], _).
safe_(Q, [Q1|Qs], D) :-
  Q =\= Q1,
  abs(Q - Q1) =\= D,
  D1 is D + 1,
  safe_(Q, Qs, D1).

count_solutions(Goal, Count) :-
  findall(1, Goal, Ones),
  length(Ones, Count).

queens_solutions(N, Count) :-
  count_solutions(queens(N, _), Count).