前戯
少し前に、「 アインシュタインのなぞなぞ 」または「ゼブラパズル」と呼ばれる興味深いパズルを思い出させたHabréの記事を読みました 。 おそらくあなたの多くは、この問題を紙で解決し、世界人口の数パーセントがこの能力を持っていることを誇りに思っていました。
この記事を読んだ後、この問題に対するソフトウェアソリューションについて考えました。 この記事で紹介したアプローチは興味深いものであり、ブログの名前を完全に正当化しましたが、私には完全に明確ではないように思われました。 現時点では、Haskellプログラミング言語に興味があります。これは、単独で脳を温めるのにも最適ですが、パズルを解くことは私にとって大きな挑戦に思えました。
アルゴリズム
一般に、タスクは次のようになります。
- 順序付けられたオブジェクトのセットがあります（条件に5つあり、これらは同じ通りにある家です）。
- 各オブジェクトには一連の属性があり、これらは順番に固定値を取ります（このような属性の条件では、所有者の国籍、家の色、ペット、好きな飲み物、所有者のタバコのブランドも5つあります）。
- 異なるオブジェクトの属性値を同じにすることはできず、各属性の値の数はオブジェクトの数と等しくなります。
- さらに、属性値の組み合わせを説明する多くの制限があります（記事の冒頭にあるリンクの1つから条件の全文を読むことができます）。
最初の考えは、タスクの条件の充足をチェックするオプションの完全な列挙でしたが、単純な計算では、組み合わせの数が
5! 5 = 24.883.200.000
5! 5 = 24.883.200.000
、これはかなりの量です。
いくつかの考えの中で、次のアプローチが生まれました：許容できるソリューションのスペースがあり、制約がソリューションのサブセットを記述し、正しいソリューションがそのようなサブセットの交差点にあります（つまり、すべての条件が満たされる領域にあります）。
次のステップは、ソリューションのサブセットを一連のテンプレートの形式で記述することでした。つまり、一部のオブジェクトの属性は固定され、他の属性は有効な値を取ることができるソリューションです。 そして、そのような記述があれば、この方法で記述されたセットを交差させる方法を学ぶ必要があるだけです。
解決策
Haskellでソリューションをコンパイルおよび書き換えるとき、問題の解決策を見つけたいという欲求だけでなく、アルゴリズムと美しいHaskell言語の両方を簡単に実証できる理解可能なプログラムを作成したいという欲求もありました。
したがって、私は訓練されていない人々によるプログラムの読み取りを妨げるアプローチの使用を最小限にしようとしました。 解決策は完全に普遍的であると主張していませんが、この種の問題を解決するためのいくつかのツールが説明されています。
しかし、あなた自身のために読んでください-私はあなたのために多くのコメントを残しました。
しかし、私もあなたのコメントに喜んでいるでしょう。
- インポートデータ。 リスト（ lookup 、 nub）
- インポートデータ。 たぶん （fromMaybe 、 catMaybes）
- -----------------------------------------------
- -アインシュタインの謎-
- -アタムール-
- -----------------------------------------------
- ---------------------------
- -タスクの一般的な説明-
- ---------------------------
- -問題の解決策はオブジェクトのシーケンスです
- タイプ Solution = [Object]
- -各オブジェクトは、一連の属性ペアとその値によって記述されます
- タイプ Object = [（ String 、 String ）]
- -=記号による属性と値のペアの表示：
- attr = ：value = （attr 、 value）
- 属性= [ "国籍" 、 "家" 、 "ペット" 、 "飲み物" 、 "煙" ]
- サイズ= 5
- -私たちはいくつかを満たすソリューションを見つける問題を解決します
- -制限
- -すべての決定のセットから開始し、徐々に明確にします
- は、1つのソリューションに還元されるまでのセットです。
- -本当。
- -したがって、オブジェクトはすぐに多くの実際のオブジェクトを記述できます。
- -いくつかの属性が設定され、残りは設定されていない
- -どれでもかまいません。 したがって、空のオブジェクトはすべての可能なテンプレートです
- -オブジェクト：
- anyObject = [] ::オブジェクト
- -そして、空のオブジェクトのセットは、与えられた前のすべての決定のセットです
- -寸法：
- anySolution = [anyObject | n ← [1 ..サイズ]]
- -各ソリューションは、ソリューションなどの互換性のあるソリューションのセットを記述します
- -[["nationality" =： "Englishman"]、anyObject、anyObject]
- -すべてのトリプルのオブジェクトを説明します。最初のオブジェクトには属性があります
- -「国籍は英語です」
- -しかし、決定を明確にするためには、多くの互換性がないことが必要です。
- -決定（たとえば、「英国人または最初または2番目だが同時にではない」）：
- タイプ Solutions = [Solution]
- empty = [] ::ソリューション
- -問題を解決するには、ソリューションに制限を課す必要があります
- -各制約は多くの決定を変換します
- -結果は、いくつかの無関係なセットまたは
- -空の決定セット
- タイプ制限=ソリューション→ソリューション
- -多くの決定に制限を適用する
- -多くのソリューションを変換するとき、私たちはチェックします
- -属性値の一意性：
- 適用::制限→ソリューション→ソリューション
- 制限ゾルを適用する=
- concat [ filter （ not。duplicates ）（制限ソリューション） | ソリューション←ソルス]
- どこで
- duplicates sols = 任意の duplicateValues（ map （values sols）属性）
- 値sols attr = map （ lookup attr）sols
- duplicateValues vals ' =
- let vals = catMaybes vals '
- in （vals ≠ nub vals）
- -オブジェクトを記述する2つのパターンの交差点
- -両方のソーステンプレートの属性を含むテンプレートの場合があります。
- -ソーステンプレートに異なる内容が含まれている場合、互換性がない可能性があります
- -同じ属性の値
- both ::オブジェクト→オブジェクト→ 多分オブジェクト
- both obj obj ' = foldl join（Just []）属性-属性に従って結合します
- どこで
- -すでに空のセットがある場合、結果も空です
- Join Nothing _ = Nothing
- -それ以外の場合は、属性ごとに制約の値を比較します
- 参加（ちょうど休息）attr =
- の場合 （ lookup attr obj 、 lookup attr obj '） の
- （無、無） →ただ休む
- （値だけ、なし） → Just（（attr = ：value）：rest）
- （Nothing 、 Just value） → Just（（attr = ：value）：rest）
- （ちょうど値、ちょうど値 '） →
- 値==値の場合 '
- 次に Just（（attr = ：value）：rest）
- それ以外は何もありません
- -基本的な制限-ある位置にあるオブジェクトは
- -プリセットテンプレート
- objectAt :: Int →オブジェクト→制限
- objectAt n obj solution =
- 両方のobj（ソリューション!! （n - 1）） の
- なし→空-テンプレートが既にそこにあるテンプレートと互換性がない場合
- ちょうど解像度→ [n resソリューションを置き換える]
- どこで
- replace nx xs = take （n - 1）xs ++ [x] ++ drop n xs
- -制限の操作---------------------------------------------
- -交差点-両方の制限が当てはまる
- （ < ＆ > ）rs rs 'solution = apply rs（rs' solution）
- r _ all = foldl1 （ < ＆ > ） -セットのすべての制限
- -ユニオン-どちらかが正しい
- （ <|> ）rs rs 'solution = rs solution ++ rs' solution
- r _ any = foldl1 （ <|> ） -制限の1つ
- -派生制限---------------------------------------------- -
- -何らかのオブジェクトがあります（最初の位置、または2番目の位置など）。
- exists obj = r _ any [objectAt n obj | n ← [1 .. 5]]
- -1つのオブジェクトは常に別のオブジェクトの後に続きます
- before obj obj ' = r _ any [
- objectAt n obj < ＆ > objectAt（n + 1）obj ' | n ← [1 ..サイズ-1]]
- -近く（または2番目の前の1つ、または最初の前の2番目）
- near obj obj ' = （obj `before` obj'） <|> （obj '` before` obj）
- ------------------------------------------------
- -特定の問題の説明-
- ------------------------------------------------
- 制限=
- objectAt 1 [ "国籍" = ： "ノルウェー語" ] < ＆ >
- exists [ "国籍" = ： "イギリス人" 、 "家" = ： "赤" ] < ＆ >
- （[ "" house " = ： " Green " ]` before` [ "house" = ： "White" ]） < ＆ >
- exists [ "国籍" = ： "デーン" 、 "ドリンク" = ： "ティー" ] < ＆ >
- （[ "" smoke " = ： " Malboro " ]` near` [ "pet" = ： "Cat" ]） < ＆ >
- exists [ "煙" = ： "ダンヒル" 、 "家" = ： "黄色" ] < ＆ >
- exists [ "国籍" = ： "ドイツ語" 、 "煙" = ： "ロスマン" ] < ＆ >
- objectAt 3 [ "drink" = ： "Milk" ] < ＆ >
- （[ "smoke" = ： "Malboro" ] `near` [ " drink " = ： " Water " ]） < ＆ >
- exists [ "smoke" = ： "Pallmall" 、 "pet" = ： "Bird" ] < ＆ >
- exists [ "国籍" = ： "スウェーデン" 、 "ペット" = ： "犬" ] < ＆ >
- （[ "nationality" = ： "Norwegian" ] `near` [ " house " = ： " Blue " ]） < ＆ >
- exists [ "pet" = ： "馬" 、 "house" = ： "青" ] < ＆ >
- exists [ "煙" = ： "Winfield" 、 "drink" = ： "ビール" ] < ＆ >
- exists [ "house" = ： "Green" 、 "drink" = ： "Coffee" ] < ＆ >
- exists [ "pet" = ： "魚" ]
- -魚はどこにも現れません、それが何であるかを尋ねる必要があります
- main =解決策=制限の適用[anySolution]
- 長さの解が1より大きい場合
- 次に putStrLn （ 「合計ソリューションセット：」 ++ ショー （ 長さソリューション））
- それ以外の場合 putStrLn $ descrSolution $ ヘッドソリューション
- -----------------------------
- -文字列表現-
- -----------------------------
- -人の文字列表現：
- descrMan man = descr "国籍" ++ "住む" ++
- descr "house" ++ "house、owns" ++
- descr "pet" ++ "、drinks" ++
- descr "drink" ++ "and smokes" ++
- descr 「煙」
- ここで descr attr = fromMaybe "？" （ lookup attr man）
- -ソリューションの文字列表現：
- descrSolution sol = concat [descrMan man ++ " \ n " | 男←ソル]