エタニティ II パズル

エタニティIIパズル（E2またはE II）は、2007年7月28日に発表されたエッジマッチングパズルです。 ^[1]^[2]クリストファー・モンクトンが開発し、オリジナルのエタニティパズルの後継としてTOMY UK Ltdが販売および著作権を取得しました。このパズルは、最初の完全な解答に200万ドルの賞金が提供されるコンテストの一部でした。コンテストは2010年12月31日正午に終了しましたが、解答は見つかりませんでした。

説明

Eternity II パズルは、隣接するエッジを一致させるという制約のもと、256 個の正方形のパズルピースを 16 × 16 のグリッドに配置するエッジマッチングパズルです。このパズルは、コンピューターによる総当たり検索では解くのが困難になるように設計されています。

各パズルピースの片側の縁には、異なる形と色の組み合わせ (ここではまとめて「色」と呼びます) が付けられており、パズルが完成すると、各縁は隣接するピースの隣の辺と正確に一致する必要があります。各ピースのもう一方の面は、識別番号以外は空白で、パズルには使用されません。したがって、各ピースは 4 つの方向でのみ使用できます。グレーの縁を除いて 22 色あります。5 色は、最も外側のリング、つまり境界ピースとコーナーピースの間の 60 の縁ペア (「ダイヤモンド」) にのみ見られ、他の 17 色は、残りの 420 の「内部」縁ペアに使用されます。色は均等に使用され、5 色の縁はそれぞれ 12 の縁ペアに使用され、17 色の内側はそれぞれ 24 の縁ペア (5 色) または 25 の縁ペア (12 色) に使用されます。エッジペアの総数は 480 です。5 つの境界色のうち 1 つはどのコーナーピースにも見当たりませんが、17 の内側色はすべて境界ピースに少なくとも 1 回は使用されています。

コーナーピースは 4 個 (2 つの側面が灰色)、境界ピースは 56 個 (1 つの側面が灰色)、内側ピースは 14 ² = 196 個 (4 つの側面が色付き) あります。各ピースの色の配置はそれぞれ異なり、回転対称のピースは 1 つもありません。そのため、256 × 4 = 1024 通りのピースと向きの選択肢によって、エッジの色のパターンが異なります。

このパズルは、最初のエタニティパズルとは異なり、ボードの中央付近の指定された位置と方向に配置する必要がある、オプションではないスターターピース（必須のヒント）があります。^[3]

製品の発売と同時に2つのヒントパズルが発売され、それぞれを解くと、メインの256ピースパズルのピースの位置（ヒント）が分かります。ヒントパズル1は36ピースの正方形（6×6）パズルで、ヒントパズル2は72ピースの長方形（12×6）パズルです。2008年には、同じ大きさの2つのヒントパズル、36ピースのヒントパズル3と72ピースのヒントパズル4が追加で発売されました。ルールブックには、ヒントを使わずにパズルを解くことができると記載されています。^[3]

複雑

Eternity II パズルの可能な配置の数は、すべてのピースが異なっており、位置が事前に決められた固定ピースを無視すると、256! × 4 ²⁵⁶で、およそ 1.15 × 10 ⁶⁶¹です。中央の固定ピースと端のピースに設定された制約を考慮すると、可能な配置の数の上限は 1 × 4! × 56! × 195! × 4 1 ⁹⁵で、およそ 1.12 × 10 ⁵⁵⁷になります。手がかりパズルで得られたヒントピースの位置と方向を考慮すると、さらに上限が得られます。この場合、5 つのピースの位置と方向がわかっているため、上限は 4! × 56! × 191! になります。 × 4 ¹⁹¹ = 3.11 × 10 ⁵⁴⁵となり、最初の近似値よりも 3.70 × 10 ¹¹⁵倍小さい探索空間が得られます。

第一近似では、エッジマッチング制約により、有効な構成の数は、すべての境界エッジペアで (1/5) 倍、すべての内側エッジペアで (1/17) 倍に減少します。有効な構成の数は、4! × 56! × 196! × 4 ¹⁹⁶ × (1/5) ⁶⁰ × (1/17) ⁴²⁰ ≈ 16.4 と近似され、1 に非常に近くなります。これは、パズルが 1 つまたは少数の解のみを持つように設計されている可能性が高いことを示しています。^[4]^[5]これにより、難易度が最大化されます。解の数が多いほど (制約が緩い、たとえば色数が少ないほど)、解 (多数の中から 1 つ) を見つけやすくなりますが、制約が厳しいほど、検索空間が狭まり、(一意の) 解を見つけやすくなります。色の数の最適化は、より小さなパズルで経験的に調査されており、この観察を裏付けています。^[6]

競争と解決策

2008年12月31日の最初の精査日の後、完全な解は見つからなかったことが発表されました。480辺のうち467辺が一致する部分解^{[7]を出したスウェーデンのルンド出身のルイス・ヴェルハードに1万ドルの賞金が授与されました。}^[8]ヴェルハードは、同じ数の一致する辺を持つさらに3つの部分解を発表しました。^[7]

2011年1月30日現在、エタニティIIの公式サイトでは「エタニティIIパズルの正解発表の最終日が勝者無しで過ぎ、エタニティIIパズルの正解者に贈られる200万ドルの賞金は未だに受け取られていない」と発表している。^[9]

Eternity 2 パズルの完全な解答は、これまで検証されて公開されたことはありません。これには、未公開のままになっている Christopher Monckton の意図した解答も含まれます。オンラインでは、いくつかの偽の解答が出回っていることが知られています。

歴史とデザイン

オリジナルのエタニティパズルは、モンクトンが考案した賞金100万ポンドのタイルパズルでした。1999年6月に発表され、アレックス・セルビーとオリバー・リオーダンが設計した、オリジナルのパズル設計の組み合わせ上の弱点を突いたコンピューター検索アルゴリズムによって解かれました。 ^[10]賞金はセルビーとリオーダンに全額支払われました。

両方の永遠パズルと驚くほど類似したパズルであるダイヤモンドのジレンマは、期限が最初の永遠パズルの期限より 10 年前の 1990 年で、パズルのピースの数は最初の 2 つの永遠パズルの 209 個と 256 個に比べて 160 個と少ないにもかかわらず、25 年以上もの間まだ解かれていません。

エターニティ II パズルは 2005 年にモンクトンが設計したが、今回はセルビーとリオーダンとの共同作業で、最終的なエターニティ II 設計を生成するコンピュータプログラムを設計した。^[11]数学ゲーム愛好家のブレンダンオーウェンによると、エターニティ II パズルは以前のパズルの組み合わせの欠陥を回避するように設計されており、設計パラメータはパズルをできるだけ解くのが難しくなるように選択されたようだ。特に、元のエターニティパズルとは異なり、問題に対する可能な解の数はおそらく非常に少ない。^[4] オーウェンは、総当たりバックトラック検索には約 2 × 10^{完了するまでに47}ステップあります。^[12]

2005年にタイムズ紙はモンクトンの次の発言を引用した。

「我々の計算では、世界で最も強力なコンピュータを今から宇宙の終わりまで稼働させても、解決策の1つに偶然出会うことはないかもしれない。」^[11]

Eternity IIが特別なケースであるエッジマッチングパズルのクラスは一般にNP完全であることが実証されているが、^[13] オリジナルのEternityパズルが特別なケースであったポリゴンパッキング問題の一般的なクラスについても同じことが言える。

オリジナルの Eternity パズルと同様に、エッジがすべて一致する多数のピースをボード上に配置する方法は多数あるため、このパズルは簡単であるように見えます。ただし、考えられる解決法の数が予想より少ないため、与えられた部分的な解決法が完全な解決法につながる可能性は天文学的に低いと考えられます。

参照

TetraVexは、 Microsoft Entertainment Packの同様のより単純な（ピースの回転や境界ピースのない）エッジマッチングパズルゲームであり、^[14]NP完全であることが示されている。^[15]

参考文献

^ 「Investegate |TOMY Announcements | TOMY: Eternity II Global Launch at Hamleys With US$2 ...」investegate.co.uk . PR Newswire。2007年7月26日。 2020年10月5日閲覧。
^ 「クリストファー・モンクトンとブレンダン・オーウェンのテレビインタビュー」。Mornings with Kerri-Anne、ブレンダン・オーウェンのチャンネル、YouTube。2007年7月26日。2021年12月21日時点のオリジナルよりアーカイブ。
^ ab 取扱説明書（PDF、アーカイブ）、公式ウェブサイトで公開
^ ab Owen, Brendan (2007). 「Eternity II – Design」. Brendan OwenのEternity IIウェブサイト。2007年12月10日時点のオリジナルよりアーカイブ。 2007年11月9日閲覧。
^ Ansótegui, Carlos; Béjar, Ramon; Fernández, Cèsar; Mateu, Carles (2008 年 7 月 3 日)。「商業用パズルの難易度: Eternity II チャレンジ」。2008年人工知能研究開発会議の議事録: カタロニア人工知能協会の第 11 回国際会議の議事録。NLD: IOS Press: 99–108。doi : 10.3233 / 978-1-58603-925-7-99。ISBN 978-1-58603-925-7。
^ Willems, Daysel (2016 年 6 月 24 日)。「フレーム付きエッジマッチングパズルの難しさについて」(PDF)。アムステルダム大学理学部学士論文。
^ ab ヴァーハード、ルイ。「EII ソルバー – 最良の結果」。最短パス.se 。2020 年10 月 9 日に取得。
^ http://www.sydsvenskan.se/2009-01-20/lundafamilj-bast-i-varlden-pa-svarknackt-pussel スウェーデン語のリンク
^ 「Eternity II」。 2010年2月8日時点のオリジナル（公式サイト）よりアーカイブ。 2011年1月30日閲覧。
^ 「Selby と Riordan の Eternity I ソルバー法の説明」Alex Selby (および Oliver Riordan) 2007 年 6 月 16 日2007 年6 月 16 日閲覧。
^ ab 「£1mによると、これは本当に最も難しいジグソーパズルです」。米国：ウッドトリック。2023年4月4日。 2023年4月4日閲覧。
^ 「Brendan Owen の Eternity II ウェブサイトの「Solving」ページ」。2007 年 12 月 10 日時点のオリジナルよりアーカイブ。2007年11 月 9 日閲覧。
^ Erik D. Demaine、Martin L. Demaine。「ジグソーパズル、エッジマッチング、ポリオミノパッキング：接続と複雑性」（PDF）。 2007年8月12日閲覧。
^ 「LGR – TetraVexと解決不可能なパズル」。2016年2月5日。2021年12月21日時点のオリジナルよりアーカイブ。YouTube経由。
^ 竹永、安彦;トビー、ウォルシュ (2006 年 9 月 15 日)。「テトラベックスはNP完全です」。情報処理レター。99 (5): 171–174。土井：10.1016/j.ipl.2006.04.010。ISSN 0020-0190。S2CID 7228681。

外部リンク

公式サイト（アーカイブ）
オリジナルのウェブサイト（現在は閉鎖）からの 4x4 パズルの Flash デモ
オンラインソリューションビジュアライザー
Eternity II ディスカッションフォーラム (Groups.io)
Eternity IIの説明とソルバーの議論
アンナ・カールソンが使用したルイ・ヴェルハールのEternity IIソルバーの説明

ソフトウェア：

オープンソースの Matlab Eternity II ソルバー
オープンソースのEternity IIエディタ/ソルバーソフトウェア
オープンソースのEternity IIパズルソフトウェア
E2Lab : 無料の Eternity II エディター/ソルバーソフトウェア
E2Solver : オープンソースの Eternity II パズルソルバー
Eternity II タイプのエッジマッチングパズルの Android アプリ。
Eternity II タイプのエッジマッチングパズル用の iPhone および iPad アプリ。

[1] 「Investegate |TOMY Announcements | TOMY: Eternity II Global Launch at Hamleys With US$2 ...」investegate.co.uk . PR Newswire。2007年7月26日。 2020年10月5日閲覧。

[2] 「クリストファー・モンクトンとブレンダン・オーウェンのテレビインタビュー」。Mornings with Kerri-Anne、ブレンダン・オーウェンのチャンネル、YouTube。2007年7月26日。2021年12月21日時点のオリジナルよりアーカイブ。

[:0-3] 取扱説明書（PDF、アーカイブ）、公式ウェブサイトで公開

[:2-4] Owen, Brendan (2007). 「Eternity II – Design」. Brendan OwenのEternity IIウェブサイト。2007年12月10日時点のオリジナルよりアーカイブ。 2007年11月9日閲覧。

[5] Ansótegui, Carlos; Béjar, Ramon; Fernández, Cèsar; Mateu, Carles (2008 年 7 月 3 日)。「商業用パズルの難易度: Eternity II チャレンジ」。2008年人工知能研究開発会議の議事録: カタロニア人工知能協会の第 11 回国際会議の議事録。NLD: IOS Press: 99–108。doi : 10.3233 / 978-1-58603-925-7-99。ISBN 978-1-58603-925-7。

[6] Willems, Daysel (2016 年 6 月 24 日)。「フレーム付きエッジマッチングパズルの難しさについて」(PDF)。アムステルダム大学理学部学士論文。

[:1-7] ヴァーハード、ルイ。「EII ソルバー – 最良の結果」。最短パス.se 。2020 年10 月 9 日に取得。

[8] ttp://www.sydsvenskan.se/2009-01-20/lundafamilj-bast-i-varlden-pa-svarknackt-pussel スウェーデン語のリンク

[officialsite-9] ^ 「Eternity II」。 2010年2月8日時点のオリジナル（公式サイト）よりアーカイブ。 2011年1月30日閲覧。

[archduke061607-10] 「Selby と Riordan の Eternity I ソルバー法の説明」Alex Selby (および Oliver Riordan) 2007 年 6 月 16 日2007 年6 月 16 日閲覧。

[times2005-11] 「£1mによると、これは本当に最も難しいジグソーパズルです」。米国：ウッドトリック。2023年4月4日。 2023年4月4日閲覧。

[12] 「Brendan Owen の Eternity II ウェブサイトの「Solving」ページ」。2007 年 12 月 10 日時点のオリジナルよりアーカイブ。2007年11 月 9 日閲覧。

[Demaine-13] Erik D. Demaine、Martin L. Demaine。「ジグソーパズル、エッジマッチング、ポリオミノパッキング：接続と複雑性」（PDF）。 2007年8月12日閲覧。

[14] 「LGR – TetraVexと解決不可能なパズル」。2016年2月5日。2021年12月21日時点のオリジナルよりアーカイブ。YouTube経由。

[15] 竹永、安彦;トビー、ウォルシュ (2006 年 9 月 15 日)。「テトラベックスはNP完全です」。情報処理レター。99 (5): 171–174。土井：10.1016/j.ipl.2006.04.010。ISSN 0020-0190。S2CID 7228681。