ゼブラ・パズル

ゼブラ・パズルは広く知られた論理パズルである。1962年12月17日"Life International"にて発表されたものを含めさまざまなバージョンが存在している。1963年3月25日刊の"Life"では解法および世界中に数百人いた正答者の氏名が掲載された。
このパズルはしばしばアインシュタインのパズルやアインシュタインのなぞかけと呼ばれる。これはこのパズルが少年期のアルベルト・アインシュタインによって創案されたと言われているからである。また、ときにはルイス・キャロルによるものだとされることもある。しかしながらアインシュタインやキャロルの著作であるという証拠は知られているかぎり存在せず、加えて、"Life International"に掲載されたバージョンはなど、キャロルの存命中またはアインシュタインの少年期には存在していなかったタバコのブランドに言及している。
ゼブラ・パズルは制約充足問題を解くアルゴリズムに対するベンチマークとして用いられてきた。
概説.
"Life International"1962年刊に以下のようなパズルが掲載された。
解法.
1人の人物が水を飲み、ほかの1人がシマウマを飼っていると仮定すると、上記2つの質問の答えがわかるのみならず、誰がどこに住んでいて、どの色の家に住んでいて、何のペットを飼っていて、何を飲んでいて、どのブランドのタバコを吸っているかを完全に導くことができる。一度に少数の手がかりのみ考慮に入れることで、少しずつ推理を積み重ねていき、唯一の正答を導き出すことができる。例えば手がかり10によるとノルウェー人は家#1に住んでおり、手がかり15によって家#2は青くなければならない。したがってノルウェー人の家は青い家ではなく、手がかり2によってイギリス人が住んでいる赤い家でもなく、手がかり6によってお互いに隣家である緑色の家と象牙色の家でもない。したがってノルウェー人の家は黄色くなければならず、手がかり8からノルウェー人はクールを吸うことになる。
"Life International"1963年3月25日刊では以下の回答および世界中の数百名の正答者の氏名が掲載された。
ほかの解法.
手がかり10には「『最初の』家」という文言が現れるが、これが正面から見て左端を指すのか右端を指すのかは不明である。しかしながら、どちらを最初の家に選んでも水を飲んでいる人とシマウマを飼っている人は変わらない。
ほかのバージョン.
ほかのバージョンのパズルは"Life International"のものとはいくつか違う点がある。例えばほかの色、国籍、タバコのブランド、飲み物、ペットが用いられたり、手がかりの与えられる順番が異なっていたりする。これらはパズルの解法には関係ない。
いくつかのバージョンでは緑の家は象牙色の家の右ではなく左にあるとされている。これによりこれら2つの家は全てが入れ替わることになり、パズルはより簡単になる。