SWI-Prolog 備忘録的虎の巻

ユニーク解が求まります。

N = 1 ~ 10 を入力して下さい。N = 12 でも求まりますが、なが〜く待つ。
gnu-prolog でも実行できます。
ciao-prolog でも実行できます。高速。

♪ プログラムコード code

% nqueens.pl

main :-
	set_gvar(count, 0),		% グローバル変数カウンタリセット 
	write( 'N = ' ),		% N は、N クイーン  
	flush_output,
	read( 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 ),
	permutation( R, Queens ),
	safe( Queens ).

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 ).

del( Item, [Item|List], List ).
del( Item, [First|List], [First|List1] ) :-
	del( 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 ).

%---------------------------------------------------------------------------%

% グローバル変数エンジン 

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.
	

%---------------------------------------------------------------------------%	
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 ).
%---------------------------------------------------------------------------%
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].

yes
?- main.
N = 1.
[1] 1
CPU time = 0.147 msec

no
?- main.
N = 2.
CPU time = 0.025 msec

no
?- main.
N = 3.
CPU time = 0.059 msec

no
?- main.
N = 4.
[2,4,1,3] 1
CPU time = 0.404 msec

no
?- main.
N = 5.
[1,3,5,2,4] 1
[2,5,3,1,4] 2
CPU time = 0.575 msec

no
?- main.
N = 6.
[2,4,6,1,3,5] 1
CPU time = 2.003 msec

no
?- main.
N = 7.
[1,3,5,7,2,4,6] 1
[1,4,7,3,6,2,5] 2
[2,4,1,7,5,3,6] 3
[2,5,1,4,7,3,6] 4
[2,5,7,4,1,3,6] 5
[2,6,3,7,4,1,5] 6
CPU time = 13.241 msec

no
?- main.
N = 8.
[1,5,8,6,3,7,2,4] 1
[1,6,8,3,7,4,2,5] 2
[2,4,6,8,3,1,7,5] 3
[2,5,7,1,3,8,6,4] 4
[2,5,7,4,1,8,6,3] 5
[2,6,1,7,4,8,3,5] 6
[2,6,8,3,1,4,7,5] 7
[2,7,3,6,8,5,1,4] 8
[2,7,5,8,1,4,6,3] 9
[3,5,2,8,1,7,4,6] 10
[3,5,8,4,1,7,2,6] 11
[3,6,2,5,8,1,7,4] 12
CPU time = 84.553 msec

no
?-

N-Queens