ユニーク解が求まります。
♪ プログラムコード code
% nqueens_fast.pl
%---------------------------------------------------------------------------%
main :-
set_gvar(count, 0), % グローバル変数カウンタリセット
write( 'N = ' ), % N は、N クイーン
flush_output, % 表示を反映する
read( N ), % N を入力
statistics(runtime, _), % 時間測定リセット
solution( N, Queens ), % N クイーンを求める
x/y( Queens, Queens1, 1 ), % [Y1,Y2,...]形式から[1/Y1,2/Y2,...]へ変換
min_size( Queens1, N ), % 対称性：左上から下へ早く Q に出会った？
write( Queens ), % ユニーク解を表示
gvar(count, CNT), % グローバル変数カウンタ値取得
write( ' ' ), % 空白を表示
write( CNT ), % 解の番号を表示
flush_output, % 表示を反映する
nl, % 改行
fail. % 失敗駆動：別解を求める
%---------------------------------------------------------------------------%
main :-
statistics(runtime, [_,T]), % 時間測定計時
write('CPU time = '), %
write(T), %
write(' msec'), %
nl, %
!, %
fail. %
%---------------------------------------------------------------------------%
solution( N, Queens ) :-
range( 1, N, R ),
solution( R, [], Queens ).
%---------------------------------------------------------------------------%
solution( [], Q, Q ).
solution( L, SafeQs, Q ) :-
select_A( X, L, RestQs ),
safe( [X|SafeQs] ),
solution( RestQs, [X|SafeQs], Q ).
%---------------------------------------------------------------------------%
range(N,N,[N]) :- !.
range(M,N,[M|Ns]) :-
M < N,
M1 is M+1,
range(M1,N,Ns).
%---------------------------------------------------------------------------%
permutation( [], [] ).
permutation( List, [Head|Tail] ) :-
del( Head, List, List1 ),
permutation( List1, Tail ).
%---------------------------------------------------------------------------%
select_A( Item, [Item|List], List ).
select_A( Item, [First|List], [First|List1] ) :-
select_A( Item, List, List1 ).
%---------------------------------------------------------------------------%
safe( [] ).
safe( [Queen|Others] ) :-
safe( Others ),
noattack( Queen, Others, 1 ).
%---------------------------------------------------------------------------%
noattack( _, [], _ ).
noattack( Y, [Y1|Ylist], Xdist ) :-
Y1 - Y =\= Xdist, % Up check
Y - Y1 =\= Xdist, % Down check
Dist1 is Xdist + 1,
noattack( Y, Ylist, Dist1 ).
%---------------------------------------------------------------------------%
% グローバル変数エンジン gvar(Name, X)がグローバル変数
set_gvar(Name, X) :-
nonvar(Name), retract(gvar(Name, _)), !, asserta(gvar(Name, X)).
set_gvar(Name, X) :-
nonvar(Name), asserta(gvar(Name, X)).
%---------------------------------------------------------------------------%
% -- 求まった解から上下左右反転解を求め -- %
% -- 大小関係を定義してより小さければ成功する -- %
% min_size( Queens ): 左右上下反転の同一解の内、最小解なら成功する。
min_size( Queens, N ) :-
change_90( Queens, Queens90, N ),
ck_min( Queens, Queens90 ),
change_90( Queens90, Queens180, N ),
ck_min( Queens, Queens180 ),
change_90( Queens180, Queens270, N ),
ck_min( Queens, Queens270 ),
change_l/r( Queens, QueensM0, N ),
ck_min( Queens, QueensM0 ),
change_90( QueensM0, QueensM90, N ),
ck_min( Queens, QueensM90 ),
change_90( QueensM90, QueensM180, N ),
ck_min( Queens, QueensM180 ),
change_90( QueensM180, QueensM270, N ),
ck_min( Queens, QueensM270 ),
gvar(count, CNT),
CNT1 is CNT + 1,
set_gvar(count, CNT1).
%---------------------------------------------------------------------------%
% -- チェス盤に大小関係を定義して、より小さければ成功する -- %
ck_min( A, B ) :-
sort_xy( B, B1 ),
ck( A, B1 ).
%---------------------------------------------------------------------------%
% 左側から縦に上から下に向かって、２つのチェス盤をしらべていき、より早くクイーンに出会った ほうが小さいことにする。
ck( [], [] ).
ck( [_/Y1|L1], [_/Y2|L2] ) :-
Y1 =:= Y2
->
ck( L1, L2 )
;
Y1 < Y2.
%---------------------------------------------------------------------------%
% -- [Y1,Y2,....]形式から[1/Y1,2/Y2,....]形式へ変換 -- %
x/y( [], [], _ ):-!.
x/y( [A|L1], [B|L2], N ) :-
B = N/A,
N1 is N + 1,
x/y( L1, L2, N1 ).
%---------------------------------------------------------------------------%
% -- 左右反転：ひっくり返す -- %
change_l/r( [], [], _ ) :- !.
change_l/r( [A/B|L1], [X/Y|L], N ) :-
N1 is N + 1,
X is N1 - A,
Y is B,
change_l/r( L1, L, N ).
%---------------------------------------------------------------------------%
% -- 反時計９０度回転 -- %
change_90( [], [], _ ) :- !.
change_90( [A/B|L1], [X/Y|L], N ) :-
N1 is N + 1,
X is B,
Y is N1 - A,
change_90( L1, L, N ).
%---------------------------------------------------------------------------%
% -- [X1/Y1,X2/Y2,...]形式を X を対象にしてソート。[1/Y1,2/Y2,...]へ -- %
sort_xy( A, B ) :-
swap( A, C ),
!,
sort_xy( C, B ).
sort_xy( A, A ).
swap( [A,B|C], [B,A|C] ) :-
A = A1/_, B = B1/_,
A1 > B1.
swap( [A|B], [A|C] ) :-
swap( B, C ).
%---------------------------------------------------------------------------%
実行例：Ciao-Prolog で実行してみます。
love:uema% ciao [~/love/prolog] Ciao 1.14.2-13646: Mon Aug 15 13:58:09 CEST 2011 ?- [nqueens_fast]. yes ?- main. N = 1. [1] 1 CPU time = 0.148 msec no ?- main. N = 2. CPU time = 0.026 msec no ?- main. N = 3. CPU time = 0.041 msec no ?- main. N = 4. [2,4,1,3] 1 CPU time = 0.159 msec no ?- main. N = 5. [2,5,3,1,4] 1 [1,3,5,2,4] 2 CPU time = 0.746 msec no ?- main. N = 6. [2,4,6,1,3,5] 1 CPU time = 1.477 msec no ?- main. N = 7. [2,6,3,7,4,1,5] 1 [1,4,7,3,6,2,5] 2 [2,5,7,4,1,3,6] 3 [2,4,1,7,5,3,6] 4 [2,5,1,4,7,3,6] 5 [1,3,5,7,2,4,6] 6 CPU time = 5.82 msec no ?- main. N = 8. [2,7,5,8,1,4,6,3] 1 [2,5,7,4,1,8,6,3] 2 [2,7,3,6,8,5,1,4] 3 [1,5,8,6,3,7,2,4] 4 [2,5,7,1,3,8,6,4] 5 [3,6,2,5,8,1,7,4] 6 [1,6,8,3,7,4,2,5] 7 [2,6,1,7,4,8,3,5] 8 [2,4,6,8,3,1,7,5] 9 [2,6,8,3,1,4,7,5] 10 [3,5,8,4,1,7,2,6] 11 [3,5,2,8,1,7,4,6] 12 CPU time = 20.049 msec no ?-