3

Prolog CLP FD を介して制限プログラミングを使用して、提案されたパズルを解こうとしています。このパズルは、次の簡単なルールで構成されています。

陰陽パズルの説明

さて、私のコードでは、すでに 2x2 グリッドの制限をカバーしており、1 つのピースを少なくとも同じ色の 1 つに接続する必要があります。

問題は、反対の色のピースを通過せずに、1 つのピースが同じ色の他のすべてのピースへのパスを持っている (接続されている) 必要があるという制限を構築する方法を見つけることができないことです。この種の出力:

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 0

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 1

1 がすべて互いに接続されているわけではありません。

この種のグラフ制限を CLP FD に記述するにはどうすればよいですか?

編集: SICStus Prolog を使用しています。

4

2 に答える 2

2

あなたの状況をより明確に考えることができるように言い換えると：

  1. あなたはすでに答えを生み出すことができます
  2. しかし、現在の答えは一般的すぎます。

プログラムをより具体的にするには、生成する回答の 1 つで現在違反しているが、すべてのソリューションで保持する必要がある条件を見つけ、この条件を制約で表現する必要があります。

たとえば、次のケースをもう一度考えてみましょう。

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 1

ここで違反している条件はどれですか? 明らかに、1ピースはパスに沿っていません。しかし、CLP(FD) でフル パスを記述するのは非常に面倒です。これは明らかに試験や宿題の問題から取られているため、目的の条件を表現するための単純なローカル基準があることを示唆しています。

「ローカル」とは、ボード全体ではなく、いくつかの隣人だけを考慮する必要があることを意味します。

それで、もう一度1ピースを考えてみましょう。明らかに、すべて1のピースには、 この答えでも1 である隣人がいます。ほかに何か？すべて1のピースには2つ の隣人がいますか? いいえ、現在ではありません。すべてのピースには 2 つの隣人も 含まれている必要がありますか? そうでない場合、いくつの例外が許容されますか?11

これらの条件に沿って考えれば、必ず良い解決策が得られます。

1 つのヒント:具体化された制約がそのようなタスクで役立つ場合があります。これは、たとえば次のように言うことができることをB #<==> (X #= Y)意味しBます 。この場合、これは必要ないかもしれないことに注意してください。 X #= Y

于 2016-12-20T20:28:10.917 に答える