-1

私は SWI Prolog の実装に関する大学の試験のために Prolog を勉強しています。

順列を使用して問題を解決するこのバージョンの 8 クイーン問題がどのように機能するかについて、私は疑問を持っています。

solution(Queens) :-
 permutation([1,2,3,4,5,6,7,8], Queens),
 safe(Queens).

permutation([],[]).

permutation([Head|Tail],PermList) :-
 permutation(Tail,PermTail),
 del(Head,PermList,PermTail).

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,
 Y-Y1=\=Xdist,
 Dist1 is Xdist + 1,
 noattack(Y,Ylist,Dist1).

以前の解決策では、次のソリューション テンプレートを使用しました: [1\Y1、2\Y2、3\Y3、4\Y4、5\Y5、6\Y6、7\Y7、8\Y8] これは、すべての女王が異なる行にある場合、X 値が制限される可能性があります。

このバージョンのプログラムでは、垂直方向の攻撃を防ぐためにすべてのクイーンが異なる行にある必要があることがわかります。そのため、各行にクイーンがあります。

したがって、情報を失うことなく、解決策はリストの順列になると言えます: [1,2,3,4,5,6,7,8]で、すべての要素が女王の Y 座標を表します。

したがって、この場合、私はその Y 座標 (その行インデックス) だけでクイーンの位置を rappresenting しています。

したがって、Queensが元のリスト[1,2,3,4,5,6,7,8]の前置突然変異であり、この順列が安全な場合(すべてのQueensこの順列リストは、他のクイーンを攻撃しません)。

OK、これは明らかです...これで安全な関係が定義されました。

リストが空の場合、攻撃がないため安全であるという基本的なケースがあります。

また、リストが空でない一般的なケースがあります。リストが空でない場合は、 [Queen|Others]に分割できます。ここで、Queenはリストの最初のクイーンで、 Othersは残りのサブリストです...したがって、サブリスト Others の場合、元のリスト[Queen|Others]は安全です。それ自体が解決策であり (安全であれば、Others に攻撃がない場合)、最初のアイテムのQueenが Othersサブリストの他の Queen を攻撃しない場合...

わかりました...今までは、私には明らかだと思います...

今、noattack関係の定義に問題があります!!!

問題は、私がクイーンの位置を Y 座標と X 座標だけで明示的に表現していないことです。

私は、ラププレゼンテーションのこの制限を回避するために、次の一般化があることを理解しています (よく理解できていることを願っています...よくわかりません...): ** また、各列に女王がいなければならないことも知っていますしたがって、リストの最初のクイーン (Queen) とサブリスト Others からの X 距離は 1** でなければなりません

最初の項目 Queen とサブリスト Others からの距離は、最初の項目 Queen とそれに最も近い Queen からの X 距離です。

したがって、クイーンが異なる列にある場合、 noattack関係は TRUE であり (コンストラクションでは常に true)、クイーンと Others サブリストの最も近いクイーンからの X 距離が 1 であると言って、別の行にある必要があることを表現できます。

しかし、私の推論が真実であれば、コードのこの部分でこのことをどのように表現するかを理解しようとすると、多くの問題が発生します。

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

2 に答える 2

2

あなたの問題は次の2行だけだと思います：

Y-Y1=/=Xdist,
Y1-Y=/=Xdist,

Y を持つクイーンが Xdist の距離で列のクイーンを斜めに攻撃するかどうかをチェックします。( |Y - Y1| = Xdist --> diagonal attack )。

他のクイーンを攻撃するもう 1 つの方法は、同じ行でそれらを攻撃することです。これは、解決策が の順列であるという理由だけで起こるわけではありません[1,2,3,4,5,6,7,8]。そのような[1,1,3,4,5,6,7,8]ことは決して起こらず、対角線をチェックするのに十分です。

問題が解決したことを願っています。

ps は、ルールY1の頭の Y 座標であることに注意してください。したがって、最初は が 1 のクイーンで、その後他の行に戻ります。OthersSafe/1Xdist

説明

について話しているnoattack/3。次の 3 つの引数を指定します。

最初：Y 現在の女王の座標、

2番目：リスト内 [Y1| Ylist] のどこかの後のどこかで始まり Y 、プライマリリストの最後まで続く右端のリスト（はい、これはソリューションのサブリストです）、および

third :Xdist 現在のクイーン (Y を持つ) と現在のクイーン (Y1 を持つ 2 番目の引数の先頭) でチェックされるクイーンの間のインデックス距離です。

3 番目の引数が必要です。これがないと、現在のクイーンと Y1 を持つクイーンの間の対角線の相互作用を確認できないからです。それは本当に基本的な数学です。座標系には自然数のみを持つ2つの点があります。abs(x1 - x2) = abs(y1 - y2)の場合にのみ、これらの 2 点が対角線上で互いに攻撃するとします。

例 #1 。私の説明がよく理解できたら、Accepted にチェックを入れてください。

P1 = (3, 4) および P2 = (1, 2) abs(3-1) = abs(4-2) = 2 で-->あるため、これらのポイントには斜めの攻撃があります。

例 #2

P1 = (3, 4) および P2 = (7, 0) abs(3-7) = abs(4-0) = 4 で-->あるため、これらのポイントには斜めの攻撃があります。

Y1-Y =\= Xdist これが、 と の両方をチェックする理由 Y-Y1 =\= Xdist です。斜め攻撃があるときはいつでも、それらの少なくとも1つがtrue. Yいずれも真でない場合は、 のクイーンと のクイーンの間に斜め攻撃がないことを意味しY1ます。の頭である次のクイーンのチェックに進むことができますYlist。

それで十分だといいです。これは非常に簡単な問題です。注意深く読んで、理解できない場合は、アルゴリズムを紙に書き写してみてください。それは常に機能する方法です。

于 2013-04-06T22:48:05.880 に答える
0

C を使用して再帰で同じ問題を解決するときに、同じ混乱があります。対角攻撃には 2 つの方向があります。左上が 0,0 の x、y 座標で各正方形に番号を付けます。次に、これら 2 つの攻撃対角線の検出または計算が条件を満たしていることがわかります。

  • x1 - y1 == x2 - y2
  • x1 + y1 == x2 + y2

上記の比較には、Prolog 表記ではなく、C の等値表記で注釈を付けました。2 点 (x1,y1) と (x2,y2) の間で、上記の条件のいずれかが満たされた場合、クイーン斜め攻撃があります。

于 2016-01-19T21:45:45.620 に答える