ゼブラパズルは、5軒の家がそれぞれ違う色で塗られている、有名な論理パズルです。 家にはそれぞれ違う住人が住んでいて、国籍も、飼っているペットも、飲み物も、趣味も異なります。
パズルを解くために、解答を説明する15個の文が与えられます。 ただし、_すべての_文の情報を組み合わせてはじめて、パズルの解答を見つけることができます。
ゼブラパズルは、制約充足問題(CSP)です。 このような問題では、取りうる値の集合と、どの値が有効かを制限する制約の集合があります。 よく知られた制約充足問題としては、ほかにも数独があります。
課題は、ゼブラパズルを解いて、次の2つの問いの答えを見つけることです。
次の15の命題は、すべて真であることがわかっています。
さらに、5軒の家はそれぞれ異なる色に塗られ、住人はそれぞれ異なる国籍で、異なるペットを飼い、異なる飲み物を飲み、異なる趣味を持っています。
解の候補は240億通り(5!⁵ = 24,883,200,000)あります。できるだけ多くの解を排除してみましょう。
それぞれの国籍は、1文字で指定します。(E = Englishman、J = Japanese、N = Norwegian、S = Spaniard、U = Ukrainian)
Exercismに登録すれば、78個の演習、そして本物の人間によるメンタリングとともに、ARM64 Assemblyを学んでマスターできます。すべて無料です。
240億通りある解の中からゼブラパズルを解く8通りの方法を紹介します。無効な順列をできるだけ早く除外する方法、AC-3アルゴリズム、とても簡潔な論理ベースの解法、さらには遺伝的アルゴリズムまで、さまざまなアプローチを探ってみましょう!