同一解を省いた１２解を表示します。
♪ プログラムコード code
love:uema% cat queens.pl
% queens.pl
main :- template( Q ), /* Q = [1/Y1,2/Y2,...........] */
solution( Q ), /* Q = 8Queen の解 */
min_size( Q ), /* Q = "左右上下反転の同一解の内、最小解" */
Q = [1/Q1,2/Q2,3/Q3,4/Q4,5/Q5,6/Q6,7/Q7,8/Q8],/* Q = [Q1,Q2,....]形式に */
write( [Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8] ), /* 表示 */
nl, /* 改行 */
fail. /* 失敗駆動：別解を見つける */
solution( [] ) :- !.
solution( [X/Y|Others] ) :-
solution( Others ),
member( Y, [1,2,3,4,5,6,7,8] ),
noattack( X/Y, Others ).
noattack( _, [] ).
noattack( X/Y, [X1/Y1|Others] ) :-
Y =\= Y1,
Y - Y1 =\= X1 - X,
Y - Y1 =\= X - X1,
noattack( X/Y, Others ).
member( X, [X|_] ).
member( X, [_|L] ) :-
member( X, L ).
template( [1/_, 2/_, 3/_, 4/_, 5/_, 6/_, 7/_, 8/_] ).
%---------------------------------------------------------------------------%
% min_size( Queens ): 左右上下反転の同一解の内、最小解なら成功する。
min_size( Queens ) :-
change_90( Queens, Queens90 ),
ck_min( Queens, Queens90 ),
change_90( Queens90, Queens180 ),
ck_min( Queens, Queens180 ),
change_90( Queens180, Queens270 ),
ck_min( Queens, Queens270 ),
change_l/r( Queens, QueensM0 ),
ck_min( Queens, QueensM0 ),
change_90( QueensM0, QueensM90 ),
ck_min( Queens, QueensM90 ),
change_90( QueensM90, QueensM180 ),
ck_min( Queens, QueensM180 ),
change_90( QueensM180, QueensM270 ),
ck_min( Queens, QueensM270 ).
%---------------------------------------------------------------------------%
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] ) :-
X is 9-A,
Y is B,
change_l/r( L1, L ).
%---------------------------------------------------------------------------%
change_90( [], [] ) :- !.
change_90( [A/B|L1], [X/Y|L] ) :-
X is B,
Y is 9-A,
change_90( L1, L ).
%---------------------------------------------------------------------------%
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 ).
%---------------------------------------------------------------------------%
love:uema%
実行例
love:uema% swipl -q -s queens.pl ?- main. [2,7,5,8,1,4,6,3] [2,5,7,4,1,8,6,3] [2,7,3,6,8,5,1,4] [1,5,8,6,3,7,2,4] [2,5,7,1,3,8,6,4] [3,6,2,5,8,1,7,4] [1,6,8,3,7,4,2,5] [2,6,1,7,4,8,3,5] [2,4,6,8,3,1,7,5] [2,6,8,3,1,4,7,5] [3,5,8,4,1,7,2,6] [3,5,2,8,1,7,4,6] false. ?-
♪ 図を表示してみます。
♪ プログラムコード
code
% queens_pic.pl
main :- template( Q ), /* Q = [1/Y1,2/Y2,...........] */
solution( Q ), /* Q = 8Queen の解 */
min_size( Q ), /* Q = "左右上下反転の同一解の内、最小解" */
Q = [1/Q1,2/Q2,3/Q3,4/Q4,5/Q5,6/Q6,7/Q7,8/Q8],/* Q = [Q1,Q2,....]形式に */
nl, /* 改行 */
write( [Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8] ), /* 表示：リスト */
nl, /* 改行 */
printboard( [Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8] ),/* 表示：図 */
nl, /* 改行 */
fail. /* 失敗駆動：別解を見つける */
solution( [] ) :- !.
solution( [X/Y|Others] ) :-
solution( Others ),
member( Y, [1,2,3,4,5,6,7,8] ),
noattack( X/Y, Others ).
noattack( _, [] ).
noattack( X/Y, [X1/Y1|Others] ) :-
Y =\= Y1,
Y - Y1 =\= X1 - X,
Y - Y1 =\= X - X1,
noattack( X/Y, Others ).
member( X, [X|_] ).
member( X, [_|L] ) :-
member( X, L ).
template( [1/_, 2/_, 3/_, 4/_, 5/_, 6/_, 7/_, 8/_] ).
%---------------------------------------------------------------------------%
% min_size( Queens ): 左右上下反転の同一解の内、最小解なら成功する。
min_size( Queens ) :-
change_90( Queens, Queens90 ),
ck_min( Queens, Queens90 ),
change_90( Queens90, Queens180 ),
ck_min( Queens, Queens180 ),
change_90( Queens180, Queens270 ),
ck_min( Queens, Queens270 ),
change_l/r( Queens, QueensM0 ),
ck_min( Queens, QueensM0 ),
change_90( QueensM0, QueensM90 ),
ck_min( Queens, QueensM90 ),
change_90( QueensM90, QueensM180 ),
ck_min( Queens, QueensM180 ),
change_90( QueensM180, QueensM270 ),
ck_min( Queens, QueensM270 ).
%---------------------------------------------------------------------------%
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] ) :-
X is 9-A,
Y is B,
change_l/r( L1, L ).
%---------------------------------------------------------------------------%
change_90( [], [] ) :- !.
change_90( [A/B|L1], [X/Y|L] ) :-
X is B,
Y is 9-A,
change_90( L1, L ).
%---------------------------------------------------------------------------%
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 ).
%---------------------------------------------------------------------------%
printboard( Q ) :-
member( N, [1,2,3,4,5,6,7,8] ),
nth1( I, Q, N ),
print( I ).
print( I ) :-
I =:= 8,
write( ' . . . . . . . Q' ),
nl,
fail.
print( I ) :-
I =:= 7,
write( ' . . . . . . Q .' ),
nl,
fail.
print( I ) :-
I =:= 6,
write( ' . . . . . Q . .' ),
nl,
fail.
print( I ) :-
I =:= 5,
write( ' . . . . Q . . .' ),
nl,
fail.
print( I ) :-
I =:= 4,
write( ' . . . Q . . . .' ),
nl,
fail.
print( I ) :-
I =:= 3,
write( ' . . Q . . . . .' ),
nl,
fail.
print( I ) :-
I =:= 2,
write( ' . Q . . . . . .' ),
nl,
fail.
print( I ) :-
I =:= 1,
write( ' Q . . . . . . .' ),
nl,
fail.
%---------------------------------------------------------------------------%
実行例
love:uema% swipl -q -s queens_pic.pl [~/love/prolog] ?- main. [2,7,5,8,1,4,6,3] . . . . Q . . . Q . . . . . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . . [2,5,7,4,1,8,6,3] . . . . Q . . . Q . . . . . . . . . . . . . . Q . . . Q . . . . . Q . . . . . . . . . . . . Q . . . Q . . . . . . . . . . Q . . [2,7,3,6,8,5,1,4] . . . . . . Q . Q . . . . . . . . . Q . . . . . . . . . . . . Q . . . . . Q . . . . . Q . . . . . Q . . . . . . . . . . Q . . . [1,5,8,6,3,7,2,4] Q . . . . . . . . . . . . . Q . . . . . Q . . . . . . . . . . Q . Q . . . . . . . . . Q . . . . . . . . . Q . . . . Q . . . . . [2,5,7,1,3,8,6,4] . . . Q . . . . Q . . . . . . . . . . . Q . . . . . . . . . . Q . Q . . . . . . . . . . . . Q . . . Q . . . . . . . . . . Q . . [3,6,2,5,8,1,7,4] . . . . . Q . . . . Q . . . . . Q . . . . . . . . . . . . . . Q . . . Q . . . . . Q . . . . . . . . . . . . Q . . . . . Q . . . [1,6,8,3,7,4,2,5] Q . . . . . . . . . . . . . Q . . . . Q . . . . . . . . . Q . . . . . . . . . Q . Q . . . . . . . . . . Q . . . . . Q . . . . . [2,6,1,7,4,8,3,5] . . Q . . . . . Q . . . . . . . . . . . . . Q . . . . . Q . . . . . . . . . . Q . Q . . . . . . . . . Q . . . . . . . . . Q . . [2,4,6,8,3,1,7,5] . . . . . Q . . Q . . . . . . . . . . . Q . . . . Q . . . . . . . . . . . . . Q . . Q . . . . . . . . . . . Q . . . . Q . . . . [2,6,8,3,1,4,7,5] . . . . Q . . . Q . . . . . . . . . . Q . . . . . . . . . Q . . . . . . . . . Q . Q . . . . . . . . . . . . Q . . . Q . . . . . [3,5,8,4,1,7,2,6] . . . . Q . . . . . . . . . Q . Q . . . . . . . . . . Q . . . . . Q . . . . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . [3,5,2,8,1,7,4,6] . . . . Q . . . . . Q . . . . . Q . . . . . . . . . . . . . Q . . Q . . . . . . . . . . . . . Q . . . . . Q . . . . . Q . . . . false. ?-
♪ 8クイーンの一つの解を取り上げ、９０度回転と左右反転の座標変換を考えます。
８クイーンの解の例：
. . . . . Q . .
. Q . . . . . .
. . . . . . Q .
Q . . . . . . .
. . Q . . . . .
. . . . Q . . .
. . . . . . . Q
. . . Q . . . .
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------
左右反転 [4,2,5,8,6,1,3,7] --> [7,3,1,6,8,5,2,4]
[.][.][.][.][.][Q][.][.]----->[.][.][Q][.][.][.][.][.]
[.][Q][.][.][.][.][.][.]----->[.][.][.][.][.][.][Q][.]
[.][.][.][.][.][.][Q][.]----->[.][Q][.][.][.][.][.][.]
[Q][.][.][.][.][.][.][.]----->[.][.][.][.][.][.][.][Q]
[.][.][Q][.][.][.][.][.]----->[.][.][.][.][.][Q][.][.]
[.][.][.][.][Q][.][.][.]----->[.][.][.][Q][.][.][.][.]
[.][.][.][.][.][.][.][Q]----->[Q][.][.][.][.][.][.][.]
[.][.][.][Q][.][.][.][.]----->[.][.][.][.][Q][.][.][.]
(x,y)->(X,Y)
-----------------------------------------
(1,4)->(8,4) X <- 9 - x Y <- y
(2,2)->(7,2) 上に同じ
(3,5)->(6,5) 上に同じ
(4,8)->(5,8) 上に同じ
(5,6)->(4,6) 上に同じ
(6,1)->(3,1) 上に同じ
(7,3)->(2,3) 上に同じ
(8,7)->(1,7) 上に同じ
X/Y=(9-x)/(y)
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------
反時計周り90度回転 [4,2,5,8,6,1,3,7] --> [3,7,2,8,6,4,1,5]
[.][.][.][.][.][Q][.][.]----->[.][.][.][.][.][.][Q][.]
[.][Q][.][.][.][.][.][.]----->[.][.][Q][.][.][.][.][.]
[.][.][.][.][.][.][Q][.]----->[Q][.][.][.][.][.][.][.]
[Q][.][.][.][.][.][.][.]----->[.][.][.][.][.][Q][.][.]
[.][.][Q][.][.][.][.][.]----->[.][.][.][.][.][.][.][Q]
[.][.][.][.][Q][.][.][.]----->[.][.][.][.][Q][.][.][.]
[.][.][.][.][.][.][.][Q]----->[.][Q][.][.][.][.][.][.]
[.][.][.][Q][.][.][.][.]----->[.][.][.][Q][.][.][.][.]
(x,y)->(X,Y)
-----------------------------------------
(1,4)->(4,8) X <- y Y <- 9 - x
(2,2)->(2,7) 上に同じ
(3,5)->(5,6) 上に同じ
(4,8)->(8,5) 上に同じ
(5,6)->(6,4) 上に同じ
(6,1)->(1,3) 上に同じ
(7,3)->(3,2) 上に同じ
(8,7)->(7,1) 上に同じ
X/Y=(y)/(9-x)