2

私は Ivan Bratko の本で Prolog を勉強しています: 人工知能のプログラミング と本で、空間状態の「グラフ」を使用して問題を解決するこのバージョンの 8 クイーン問題を見つけました。

s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]),
                             noattack(Queen, Queens).

goal([_,_,_,_,_,_,_,_]).

noattack(_,[],_).

noattack(Y,[Y1|Ylist],Xdist) :-
                                  Y1-Y =\= Xdist,
                      Y-Y1 =\= Xdist,
                                  Dist1 is Xdist + 1,
                                  noattack(Y,Ylist,Dist1).

solve(N,[N]) :- goal(N).

solve(N, [N|Sol1]) :- s(N,N1),
                      solve(N1,Sol1).

これは、順列に基づく 8 クイーン問題の解決策 (そのnoattack/3関係を使用) と、可能性のある後継状態の状態 (グラフのノード) を構築すると思われるs/2述語を組み合わせたものです。だから私は次のようなものを持っています:

s(ActualState、SuccessorState)

goal/1述語は、正確に 8 個のクイーンを配置する必要があることを指定しているだけだと思います。

この本では、次のクエリを実行すると言います: solve([],Solution)は、クイーンの数が増加するボード ポジションのリストを生成し、このリストは 8 つのクイーンの安全な構成で終了します。

しかし、このクエリを実行しようとすると機能せず、次の出力が得られます。

?- solve([],Solution).
ERROR: s/2: Undefined procedure: noattack/2
ERROR:   However, there are definitions for:
ERROR:         noattack/3

当然のことながら、行 2 で呼び出されるnoattack述語は 2 つのパラメーターしか取りませんが、noattack述語には 3 つのパラメーターが必要です。

なんで？私は何が欠けていますか？

4

1 に答える 1

3

いくつかのバグ:

s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]),
                             noattack(Queen, Queens, 1).

noattack(_,[],_) :- !.
noattack(Y,[Y1|Ylist],Xdist) :-   Y =\= Y1,
                                  Y1-Y =\= Xdist,
                                  Y-Y1 =\= Xdist,
                                  Dist1 is Xdist + 1,
                                  noattack(Y,Ylist,Dist1).

それで、

18 ?- solve([],_X), last(_X,S).
S = [4, 2, 7, 3, 6, 8, 5, 1] ;
S = [5, 2, 4, 7, 3, 8, 6, 1] ;
S = [3, 5, 2, 8, 6, 4, 7, 1] ;
S = [3, 6, 4, 2, 8, 5, 7, 1] ;
S = [5, 7, 1, 3, 8, 6, 4, 2] ;
S = [4, 6, 8, 3, 1, 7, 5, 2]

と、

25 ?- findall( X, solve([],X), _S), length(_S,N).
N = 92.
于 2013-05-08T13:14:03.100 に答える