22

まず、私は必ずしも完全なアルゴリズムを探しているわけではありません。コピーして貼り付けて、それを1日と呼ぶことができます。どんな「一般的なアプローチ」の解決策でも私には問題ありません！

この投稿全体は、仕事が遅い日、このサイトに出くわし、ジェネレーターをどのように実装したかを理解できなかったことに拍車をかけました。

問題

ご存じない方のために説明すると、「ゼブラパズル」や「アインシュタインのパズル」は、おそらく以前に遭遇したことのある有名なロジックパズルです。

完全なwiki記事はここにありますが、関連するビットを投稿します。

There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house.
The Norwegian lives in the first house.
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept. 
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.

Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be
added that each of the five houses is painted a different color, and their inhabitants
are of different national extractions, own different pets, drink different beverages 
and smoke different brands of American cigarets [sic]. One other thing: in statement 
6, right means your right.

これはすべてうまくいっています。特に制約プログラミングを使用して、この問題を解決するための簡潔で巧妙な方法をオンラインでいくつか見つけました。しかし、私が興味を持っているのは、これらのタイプのパズルをもっと作ることです。

もっと作る

明らかに、行列表現はこれについて考える論理的な方法です。各列には、人、家、飲むもの、運転する車の種類などが含まれています。

私の最初の考えは、ランダムに生成された完全な（つまり、解決された）グリッドから始めて、（何らかの方法で）解決されたバージョンからそれを一意に識別するヒントを作成することでした。何かを決定できるたびに、それはグリッドから削除されます。

最初にリストしたサイトをリッピングすると、グリッドを解決するために使用できる次の「ヒント」は次のタイプになります。

  • 人/動物/植物は与えられた家に住んで/成長します。

  • 人/動物/植物は特定の家に住んでいない/成長していません。

  • 人/動物/植物は他の人/動物/植物と同じ家に住んでいます。

  • 人/動物/植物は、他の人/動物/植物の直接の隣人です。

  • 人/動物/植物は、他の人/動物/植物の左または右の隣人です。

  • 人/動物/植物と他の人/動物/植物の間に1つの家があります。

  • 左または右の人/動物/計画と他の人/動物/植物の間に1つの家があります。

  • 人/動物/植物と他の人/動物/植物の間に2つの家があります。

  • 左または右の人/動物/計画と他の人/動物/植物の間に2つの家があります。

  • 人/動物/植物は、他の人/動物/植物から左または右に住んでいます。

これらを一般化、拡張する方法などを確認できます。

難しいのは、私のアプローチ（完全なグリッドから始めてこれらのヒントを生成する）を使用して、作成するヒントのセットが絶対にターゲットグリッドになることを確認する方法がわからないことです。

たとえば、「イギリス人は松の木を所有していない」と言った場合、パズルのどの時点でも2つのものを決定的に組み合わせることができません。しかし、解決する必要のある木が2つしかない場合、これは実際には決定的な証拠となる可能性があります。

私はこれを完全に間違った方法で考えていますか？より良いアプローチは、ランダム化された事前定義された既知の要素を使用してグリッドを作成し（つまり、赤い家が中央にある）、これらのヒントを構築のルールとして使用してグリッドを構築することです。

アドバイス、読むべき記事、学ぶためのプログラミング技術など、大歓迎です！

4

5 に答える 5

11

ソルバーを利用した簡単なアルゴリズムは次のとおりです。

  1. ランダムなパズルインスタンスを生成します。

  2. このパズルインスタンスに関連するすべての可能な手がかりのセットCを作成します。（考えられる手がかりは有限で、実際には非常に少数です。たとえば、家が5つある場合、「人Aは家Bに住んでいます」という形式の手がかりが5つ、「人Aが住んでいる」という形式の手がかりが8つあります。家Bの隣」など。）

  3. Cの手がかりのランダム順列c1、c 2、...、cnを選択します。

  4. i =1に設定します。

  5. i > nの場合、これで完了です。手がかりのセットCは最小限です。

  6. D = C −{ ci }とします。手がかりのセットDでソルバーを実行し、可能な解決策の数を数えます。

  7. 解が1つしかない場合は、C = Dに設定します。

  8. i = i + 1に設定し、手順5に戻ります。

（一度に1つずつではなく、バッチで手がかりを削除することでこれを高速化できますが、アルゴリズムの記述がより複雑になります。）

于 2013-01-28T20:00:14.073 に答える
3

私はこのソリューションに完全に自信があるわけではありませんが、これが私がそれにアプローチする方法です：

ランダムな解決策から始めます（つまり、温室はLMを吸う磨きを保持し、赤い家はクローブを吸うアイルランドを保持します）。そのソリューションは、ステートメント間の関係のグラフとして見ることができます。ここで、すべての要素（ポリッシュ、赤い家など）は、「はい」のエッジまたは「いいえのエッジ」のいずれかによって他のすべての要素に接続されます（この場合、ポリッシュは「はい」のエッジで緑の家に接続され、 「エッジなし」のクローブ（他の多くのエッジの中で、この最初のグラフは完全な方向性グラフです））。

ここで、エッジをランダムに取り除くと、最小限の連結グラフが残るまで、解決可能なパズルを表すグラフが作成されます。すべてのyesエッジを「foois/does bar」に変換し、すべてのnoエッジを「foois n't / doesn'tbar」に変換します。

直感的に、これは私には正しいと思います。しかし、繰り返しになりますが、これはこれを行うための正式なまたは認識された方法ではなく、完全に間違っている可能性があります。

于 2013-01-28T19:40:11.017 に答える
2

逆の方法で行うこともできます（これにより、ソルバーも取得できます）。

  1. 考えられるすべてのソリューション（つまりテーブル）のリストであるSを生成します。
  2. ランダムなファクトfを生成します（たとえば、ノルウェー人には猫がいます）。
  3. T=Sに設定
  4. fに違反するすべてのソリューションをTから除外します。
  5. |T|の場合 = 0次に2に進みます（事実は前のものと矛盾します）
  6. |T|の場合 <| S | 次に、S = TおよびF.append（f）を設定します（ファクトは以前のファクトによってまだ具体化されていません）
  7. IF | S | >1次にgoto2

完了すると、 FはSに残された唯一のテーブルにつながるファクトのリストになります。

確かに、これは非常にブルートフォースであり、5X5以上のテーブルではおそらくうまく機能しません。

于 2013-12-09T10:08:04.373 に答える
1

興味深いことに、「アインシュタイン」パズル（引用が意図されている、すべての「賢い」はアインシュタインに割り当てられる傾向があり、より魅力的である可能性があります）は、数独生成アルゴリズム（用語の適切な翻訳による）およびルービックキューブ（3x3x3）に関連しています解くアルゴリズム

数独の場合、手がかりはグリッド上ですでに割り当てられている番号に対応し、不足している情報は空のスロットに対応します

ルービックキューブ（私はもっと面白いと思います）の場合、手がかりはキューブの対称性に対応します（たとえば、緑色は赤色の隣にあります、そのようなものです）そして不足しているデータは再調整（解決）することによって見つけられますキューブ

これは大まかな概要です、ありがとう

于 2014-05-05T19:26:19.427 に答える
0

別の考えがあります-完全なグリッドを生成したら、手がかりを提供するときにアイテムを削除する前に、携帯電話でその写真を撮ります（またはデザインを複製します）。タスクの途中で、元の/最終的なレイアウトがどのように見えるかを忘れて、被験者/受験者に誤った情報を与えることを回避できる場合があります。

イースターのために1つを行うことを考えて、同様のパターン、5人、5種類のチョコレート、5年齢、5種類のイースター帽子、5種類のお気に入りの飲み物、アイスクリームなど。

于 2019-03-26T13:56:51.083 に答える