1

現在、SICStus Prolog を使用して、prolog の制限を学習し始めています。これを使って簡単な問題を解く方法は知っていますが、ジグソー パズルを解かなければならない練習問題が 1 つあります。ただし、これを解決する方法がわかりません。さまざまなプロパティ (ピース) を持ついくつかの異なる要素があるためです。プロローグでピースのリストを表す方法と、どのような制限を使用する必要があるかの例を教えてください。

4

1 に答える 1

4

最初の試みとして、次の行に沿って何かを行います。

フィールドごとに、5 つの変数を使用します。最初の変数は、フィールドに入るパズルのピースを示します。各ピースには独自の ID があります。上記のコメントで言及したパズルの場合、12 個のピース​​があるため、各変数のドメインは {1..12} になります。

P #:: 1..12,

他の 4 つの変数は、各フィールドの 4 つのエッジと、フィールドに配置されたパズルのピースにへこみまたはタブがあるかどうかを示します。パズルでは、「上」または「下」の各面にタブとへこみがあるため、タブが左か右かを示します。繰り返しますが、ブール決定変数です。

[EL,EU,ER,ED] #:: 0..1,

パズルのピースは次のようにエンコードできます。

piece(1,  [](0,1,1,0)).

これは、たとえば、コメントで提供した Web サイトのパズルの説明のピース A です。

これで、隣接する 2 つのフィールド間の隣接関係を定義できるようになりました。ブール変数があり、タブがへこみを満たす必要があるため、合計が 1 になるように制約 (「制限」ではなく) を設定します。

R1 + L2 #= 1,

つまり、フィールド 1 のピースの右端は、フィールド 2 のピースの左端と一致する必要があります。

境界に沿ったエッジにも同様の制約を設定します。

すべてのフィールドに異なる要素を含める必要があるという制約を設定した場合:

alldifferent(Fields),

(ここで、Fields は P 変数を含むリストです)

パズルのピースの向きを示す変数が必要です。

O #:: 0..1,

パズルでは、すべてのピースが同じ方向を向いている必要があるため、必要なのは 1 つだけです。

最後に、各フィールドのピース、方向、およびエッジ変数を組み合わせる制約が必要です。これにより、フィールドのピースを選択したときに (方向がわかっている場合)、エッジ変数を適切に設定できます。

 once(piece(N, [](L,U,V,D))),
 ( ((P#=N) #/\ (O#=0)) #=> ((EL#=L) #/\ (EU#=  U) #/\ (ER#=R) #/\ (ED#=  D)) ),
 ( ((P#=N) #/\ (O#=1)) #=> ((EL#=R) #/\ (EU#=1-D) #/\ (ER#=L) #/\ (ED#=1-U)) ),

(構文は Sicstus 用ではなく、ECLiPSe 用です。しかし、FD 制約ライブラリは十分に似ているはずです)

ピースを上下逆さまにするときは、下端のエンコーディングを反転する必要があることに注意してください。これにより、上下のエッジの「合計が 1 に等しい」という制約を維持することができましたが、エッジ変数からピース変数に情報を簡単に伝播することができなかったため、最適ではありません (ピースはひっくり返すともう一枚）。しかし、この最初の試行でエンコーディングを変更するのが面倒でした。

(編集:これは、ダウン エッジのエンコーディングを反転することで簡単に修正できます。例: piece(1, [](0,1,1,1)).、隣接するピースのアップ エッジとダウン エッジが合計 1 ではなく同じ値を持つように要求する制約を使用します。)

すべてをまとめて P 変数に単純にラベルを付けると (向き変数を最初にインスタンス化した後)、次の 2 つの解決策が得られます。

?- rapids(S,O).
S = []([](5, 2, 8, 6), [](11, 10, 1, 4), [](3, 9, 12, 7))
O = 0
Yes (0.01s cpu, solution 1, maybe more)
S = []([](5, 3, 11, 12), [](8, 9, 7, 4), [](2, 10, 6, 1))
O = 1
Yes (0.04s cpu, solution 2, maybe more)
No (0.05s cpu)

パズル フィールドの行をより目立たせるために、リストの代わりにマトリックスを使用しました。マトリックスを使用すると、異なる行の隣接フィールドへのアクセスも高速になります。

于 2011-12-01T17:07:33.943 に答える