-2

Prolog で n-queens 問題を可視化したいと考えています。

このような、

1? -queen(1,2,5).
===================
# Q # # #
# # # Q #
Q # # # #
# # Q # #
# # # # Q
===================
===================
# Q # # #
# # # # Q
# # Q # #
Q # # # #
# # # Q #
===================

Total Output is 2
true.

そこで、Prolog でこの N-queens を使用したいと思います。

solution(_, []).
solution(N, [X/Y|Others]) :-
    solution(N, Others),
    between(1, N, Y),
    noattack(X/Y, Others).

noattack(_,[]).
noattack(X/Y, [X1/Y1 | Others]) :-
    Y =\= Y1,
    Y1-Y =\= X1-X,
    Y1-Y =\= X-X1,
    noattack( X/Y, Others).

template(N, L) :-
    findall(I/_, between(1,N,I), L).

これにより、この出力が作成されます。

?- N=6, template(N, L), solution(N, L).
N = 6,
L = [1/5, 2/3, 3/1, 4/6, 5/4, 6/2] ;
N = 6,
L = [1/4, 2/1, 3/5, 4/2, 5/6, 6/3] ;
N = 6,
L = [1/3, 2/6, 3/2, 4/5, 5/1, 6/4] ;
N = 6,
L = [1/2, 2/4, 3/6, 4/1, 5/3, 6/5] ;

クイーン（X、Y、N）は

(X, Y) はクイーンの位置です。

(N) はクイーンズディグリーです。

この N-queens 問題を次のように視覚化したい

L の成分と視覚化成分を見つけます。

たとえば、L = [...,3/4,...] がわかった場合

この # は N-1 回で、Q は 4 番目です。

Prolog でエラーが発生しやすいコードを次に示します。

queen(X,Y,N):-
    position(X,Y), %consummate this L list and bring to Ls
    print_queen( Ls , N).

これを表す方法がわかりません

position(X,Y).    

print_queen(Ls, N).

queen(X,Y,N).

部。

4

1 に答える 1

0

あなたが要求したフォーマットされた出力のためのSWI-Prologソリューションを提供しようとします。

'#' と 'Q' を使用Nして、クイーンを配置したサイズの線を印刷するには、次のようにします。Col

Col1 is Col - 1, format('~|~`#t~*+Q~`#t~*|~n',[Col1, N]).

の詳細については、ドキュメントを参照してくださいformat/2。例えば：

?- Col = 3, N = 8, Col1 is Col-1, format('~|~`#t~*+Q~`#t~*|~n',[Col1,N]).
##Q#####

ここで、ソリューションがこの形式であると仮定すると、すべてのクイーン (リスト内の要素)を満たすために[1/Q1, 2/Q2, 3/Q3, ..., N/QN]使用できます。forall/2format/2

print_queens(Queens, N):-
    forall(member(_/Col, Queens),
           ( Col1 is Col-1, format('~|~`#t~*+Q~`#t~*|~n',[Col1,N]) )
          ).

上記の述語を使用すると、次のようになります。

?- print_queens([1/3,2/1,3/4,4/5,5/3,6/6], 6).
##Q###
Q#####
###Q##
####Q#
##Q###
#####Q
true.

後で編集 (コメントからの明確化後): N-queens のすべてのソリューションを印刷するには、それらのいずれかの固定位置を指定します。

queen(X, Y, N):-
    template(N, L),    % Build the template of the solution
    member(X/Y, L),    % Unify given value for Y with its corresponding variable in L
    !,                 % Green cut

    % Count solutions while printing them
    findall(s, (solution(N, L), print_queens(L, N)), All),

    % Print total number of solutions
    length(All, Len),
    format('Total Output is ~w.~n', [Len]).
于 2014-06-17T08:59:24.327 に答える