Download
/*
N-queens in B-Prolog.
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my B-Prolog page: http://www.hakank.org/bprolog/
*/
% 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).
This work is licensed under a Creative Commons Attribution 4.0 International License.