/*

N-queens in B-Prolog.

Model created by Hakan Kjellerstrand, hakank@gmail.com

*/

% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

/*
More systematic test of queens2/2 and queens/2.

Both queens2/2 and queens/2 take long time for N=500
(but is much faster for N=499 and N=500:
For N=400:
queens2/2: 0.62s 10 backtracks
queens/2:  2.16s 1 backtrack
For N=499:
queens2/2: 0.76 1 backtracks
queens/2:  4.168 0 backtracks
For N=500: too slow
For N=501:
queens2/2: 3.14s 1 backtrack
queens/2:  3.524s 2 backtracks

For N=1000:
queens2/2: 24.2s 2 backtracks
queens/2:  34.146s 0 backtracks

*/

%
% Reporting both time and backtracks
%
time2(Goal):-
cputime(Start),
statistics(backtracks, Backtracks1),
call(Goal),
statistics(backtracks, Backtracks2),
cputime(End),
T is (End-Start)/1000,
Backtracks is Backtracks2 - Backtracks1,
format('CPU time ~w seconds. Backtracks: ~d\n', [T, Backtracks]).

% Decomposition of alldifferent
alldifferent_me(L) :-
length(L, Len),
foreach(I in 1..Len, J in I+1..Len, L[I] #\= L[J]).

%
% Decomposition of alldifferent for ip_solve
% (used in queens7/2).
%
alldifferent_mip(L) :-
length(L, Len),
foreach(I in 1..Len, J in I+1..Len, L[I] $\= L[J]). % % Testing correctness of queens/2 (using alldistinct) % go :- N = 8, findall(Q, queens(N,Q), L), length(L,Len), writeln(L), writeln(len:Len). % Larger example go2 :- N = 300, time2(queens(N,Q)), writeln(Q). % Testing queens2/2. % This is quite hard. > 35 minutes... go3 :- N = 500, time2(queens2(N,Q)), writeln(Q). % Testing queens3/2 go4 :- N = 8, time2(queens3(N,Q)), writeln(Q). go5 :- Sizes = [8,10,20,100,200,300,400,499,501], foreach(N in Sizes, [Q,Q2], ( garbage_collect, writeln(n:N), % time2(queens5(N, Q)), % writeln(queens5:Q), time2(queens(N, Q)), writeln(queens:Q), time2(queens2(N, Q2)), writeln(queens2:Q2), nl ) ). % Using the decomposition of alldifferent. % Testing correctness. go6 :- N = 8, findall(Q, queens4(N,Q), L), length(L,Len), writeln(L), writeln(len:Len). % Using the decomposition of alldifferent go7 :- N = 50, time2(queens4(N,Q)), writeln(Q). % % Systematic test of queens4/2 (decomposition of alldifferent) % go8 :- foreach(N in 8..5..100, [Q], ( writeln(n:N), time2(queens4(N, Q)), writeln(Q), nl ) ). % % Using SAT solver (sat_solve) % Not blazingly fast: % N=50: 3.18s % N=100: 25.66s % go9 :- findall(Q, queens6(8,Q), All), writeln(All), length(All, Len), writeln(len:Len), time2(queens6(100,Q2)), writeln(Q2). % % Using IP solver (ip_solve) % go9 :- time2(queens7(8,Q)), writeln(Q). % % Traditional: using 3 alldistinct. % queens(N, Q) :- length(Q, N), Q :: 1..N, % Note: We must "extract" via @= % This don't_ work: alldistinct([Q[I]+I : I in 1..N]) Q2 @= [Q[I]+I : I in 1..N], Q3 @= [Q[I]-I : I in 1..N], alldistinct(Q), alldistinct(Q2), alldistinct(Q3), labeling([ff],Q). % % Traditional: Using alldifferent instead of alldistinct % is little faster than using alldistinct. % queens2(N, Q) :- length(Q, N), Q :: 1..N, Q2 @= [Q[I]+I : I in 1..N], Q3 @= [Q[I]-I : I in 1..N], alldifferent(Q), alldifferent(Q2), alldifferent(Q3), labeling([ff],Q). % % This is - unsurprisingly - much slower. % queens3(N, Q) :- length(Q, N), Q :: 1..N, foreach(I in 1..N, J in I+1..N, ( Q[I] #\= Q[J], Q[I] + I #\= Q[J], Q[I] - I #\= Q[J] ; true ) ), labeling([ff], Q). % % Using decomposition of alldifferent. Slower. % queens4(N, Q) :- length(Q, N), Q :: 1..N, Q2 @= [Q[I]+I : I in 1..N], Q3 @= [Q[I]-I : I in 1..N], alldifferent_me(Q), alldifferent_me(Q2), alldifferent_me(Q3), labeling([ffd],Q). % % slightly different approach (from queens/2 and queens2/2) % where we start with an array A and then extract the % lists Q from A. % queens5(N, Q) :- new_array(A,[N]), % Q @= [A[I] : I in 1..N], array_to_list(A,Q), Q :: 1..N, Q2 @= [A[I]+I : I in 1..N], Q3 @= [A[I]-I : I in 1..N], % alldifferent(Q), % alldifferent(Q2), % alldifferent(Q3), alldistinct(Q), alldistinct(Q2), alldistinct(Q3), % labeling([ff],Q). labeling([ff],Q). % % SAT based solution % Note: This only generate one solution % queens6(N, Q) :- length(Q, N), Q :: 1..N, Q2 @= [Q[I]+I : I in 1..N], Q3 @= [Q[I]-I : I in 1..N], % Special constraints for SAT solve$alldifferent(Q),
$alldifferent(Q2),$alldifferent(Q3),

sat_solve(Q).

%
% LP based solution
% Note: This only generate one solution.
% Time:
%   N=8: 2.56s
%   N=10: 61.6s
%
queens7(N, Q) :-
length(Q, N),
Q :: 1..N,
foreach(QQ in Q, lp_integer(QQ)),
Q2 @= [Q[I]+I : I in 1..N],
Q3 @= [Q[I]-I : I in 1..N],

% Using $alldifferent/1 don't work % (GLPK give PROBLEM HAS NO FEASIBLE SOLUTION) %$alldifferent(Q),
% $alldifferent(Q2), %$alldifferent(Q3),

% This works, though.
alldifferent_mip(Q),
alldifferent_mip(Q2),
alldifferent_mip(Q3),
ip_solve(Q).

%
% Collecting all the alldifference in a foreach loop.
% However it's slower than queens/2 and queens2/2...
%
queens8(N, Q) :-
length(Q, N),
Q :: 1..N,
foreach(A in [-1,0,1],
[QQ],
(
QQ @= [Q[I]+I*A : I in 1..N],
alldifferent(QQ)
)
),
labeling([ffd],Q).