2

山登りアルゴリズムとビーム探索アルゴリズムを使用して、nqueens パズル用に Prolog で 2 つのプログラムを作成しました。

残念ながら、プログラムが正しいかどうかを確認する経験がなく、行き詰まっています。

誰かが私を助けてくれれば幸いです。残念ながら、ヒル クライミングのプログラムは正しくありません。:( ビームサーチのプログラムは次のとおりです。

queens(N, Qs) :-  
  range(1, N, Ns), 
  queens(Ns, [], Qs).

range(N, N, [N]) :- !.
range(M, N, [M|Ns]) :- 
  M < N, 
  M1 is M+1, 
  range(M1, N, Ns).

queens([], Qs, Qs).
queens(UnplacedQs, SafeQs, Qs) :- 
  select(UnplacedQs, UnplacedQs1,Q),
  not_attack(SafeQs, Q),  
  queens(UnplacedQs1, [Q|SafeQs], Qs).  

not_attack(Xs, X) :- 
  not_attack(Xs, X, 1).
not_attack([], _, _) :- !.
not_attack([Y|Ys], X, N) :-
  X =\= Y+N,  
  X =\= Y-N, 
  N1 is N+1, 
  not_attack(Ys, X, N1).

select([X|Xs], Xs, X).
select([Y|Ys], [Y|Zs], X) :- select(Ys, Zs, X).
4

3 に答える 3

0

あなたのコードを正しく読めば、あなたが実装しようとしているアルゴリズムは、ビーム検索ではなく単純な深さ優先検索です。そうあるべきなので、それは問題ありません (この問題に対してビーム探索がどのように効果的であるかはわかりませんし、プログラムするのも難しい場合があります)。

このコードをデバッグするつもりはありませんが、提案をします: チェス盤をボトムアップでビルドします。

queens(0, []).
queens(N, [Q|Qs]) :-
    M is N-1,
    queens(M, Qs),
    between(1, N, Q),
    safe(Q, Qs).

どこにsafe(Q,Qs)もない場合は trueQsですQ。次に、簡単なチェック (SWI-Prolog のマニュアルを参照) と、一見正しいように見える述語をsafe/2組み合わせたものです。memberchk/2not_attack/2

于 2011-02-05T12:54:47.620 に答える
-1

Googleで簡単に確認したところ、コードと比較して変更する必要がある候補がいくつか見つかりました。

完全に明確にするための私の好みの解決策は、上記にリンクされているものの2番目です。

% This program finds a solution to the 8 queens problem.  That is, the problem of placing 8
% queens on an 8x8 chessboard so that no two queens attack each other.  The prototype
% board is passed in as a list with the rows instantiated from 1 to 8, and a corresponding
% variable for each column.  The Prolog program instantiates those column variables as it
%  finds the solution.

% Programmed by Ron Danielson, from an idea by Ivan Bratko.

% 2/17/00


queens([]).                                 % when place queen in empty list, solution found

queens([ Row/Col | Rest]) :-                % otherwise, for each row
            queens(Rest),                   % place a queen in each higher numbered row
            member(Col, [1,2,3,4,5,6,7,8]), % pick one of the possible column positions
            safe( Row/Col, Rest).           % and see if that is a safe position
                                            % if not, fail back and try another column, until
                                            % the columns are all tried, when fail back to
                                            % previous row

safe(Anything, []).                         % the empty board is always safe

safe(Row/Col, [Row1/Col1 | Rest]) :-        % see if attack the queen in next row down
            Col =\= Col1,                   % same column?
            Col1 - Col =\= Row1 - Row,      % check diagonal
            Col1 - Col =\= Row - Row1,
            safe(Row/Col, Rest).            % no attack on next row, try the rest of board

member(X, [X | Tail]).                      % member will pick successive column values

member(X, [Head | Tail]) :-
            member(X, Tail).

board([1/C1, 2/C2, 3/C3, 4/C4, 5/C5, 6/C6, 7/C7, 8/C8]). % prototype board

ただし、最後のリンクは 3 つの異なる方法で解決するため、3 つの既知の解決策と比較できます。

于 2011-02-05T15:58:33.207 に答える