トラック
/
Nim
Nim
/
演習
/
シマウマのパズル
シマウマのパズル

シマウマのパズル

中級

はじめに

ゼブラパズルは、5軒の家が出てくる有名な論理パズルです。それぞれの家は違う色で塗られています。 家にはそれぞれ違う住人が住んでいて、国籍も、飼っているペットも、飲み物も、吸っているタバコの銘柄も違います。

パズルを解くために、答えを説明する15の文が与えられます。 ただし、_すべて_の文の情報を組み合わせてはじめて、パズルの答えを見つけることができます。

Note

ゼブラパズルは制約充足問題(CSP)です。 このような問題では、取りうる値の集合と、どの値が有効かを制限する制約の集合があります。 よく知られた制約充足問題には、数独もあります。

説明

この課題では、シマウマパズルを解いて、次の2つの質問の答えを見つけます。

  • 住人のうち、水を飲むのは誰ですか?
  • シマウマを飼っているのは誰ですか?

パズル

次の15の記述は、すべて正しいことがわかっています。

  1. 家は5軒あります。
  2. イギリス人は赤い家に住んでいます。
  3. スペイン人は犬を飼っています。
  4. 緑色の家ではコーヒーが飲まれています。
  5. ウクライナ人は紅茶を飲みます。
  6. 緑色の家は、象牙色の家のすぐ右隣にあります。
  7. Old Goldを吸う人はカタツムリを飼っています。
  8. 黄色い家ではKoolsが吸われています。
  9. 真ん中の家では牛乳が飲まれています。
  10. ノルウェー人は1軒目の家に住んでいます。
  11. Chesterfieldsを吸う人は、キツネを飼っている人の隣の家に住んでいます。
  12. Koolsは、馬が飼われている家の隣の家で吸われています。
  13. Lucky Strikeを吸う人はオレンジジュースを飲みます。
  14. 日本人はParliamentsを吸います。
  15. ノルウェー人は青い家の隣に住んでいます。

さらに、5軒の家はそれぞれ異なる色で塗られており、住人はそれぞれ異なる出身国で、異なるペットを飼い、異なる飲み物を飲み、異なるブランドのタバコを吸っています。

Note

解は240億通り(5!⁵ = 24,883,200,000)あります。ですから、できるだけ多くの解を除外してみましょう。


出典

Wikipediaリンクは新しいウィンドウまたはタブで開きます
GitHubで編集する リンクは新しいウィンドウまたはタブで開きます
Nim Exercism

シマウマのパズルを始める準備はできましたか?

Exercismに登録すれば、70個の演習、そして本物の人間によるメンタリングとともに、Nimを学んでマスターできます。すべて無料です。

シマウマのパズルを深く掘り下げよう!

240億通りある解の中からゼブラパズルを解く8通りの方法を紹介します。無効な順列をできるだけ早く除外する方法、AC-3アルゴリズム、とても簡潔な論理ベースの解法、さらには遺伝的アルゴリズムまで、さまざまなアプローチを探ってみましょう!