ペントミノ

ペントミノ(または5-オミノ) は、ギリシャ語で「5」と「ドミノ」を意味する言葉に由来し、5 次ポリオミノ、つまり、端と端がつながった5 つの同じ大きさの正方形でできた平面上の多角形です。回転と反射が別個の図形とみなされない場合、12 種類の自由ペントミノがあります。反射が別個であると考えられる場合、18 種類の片側ペントミノがあります。回転も別個であると考えられる場合、63 種類の固定ペントミノがあります。

ペントミノタイルパズルやゲームは、レクリエーション数学で人気があります。^[1]通常、テトリスの模倣やランパートなどのビデオゲームでは、鏡の反射は区別できるとみなされるため、18個の片面ペントミノのフルセットが使用されます。（テトリス自体は4つの正方形を使用します。）

12個のペントミノはそれぞれコンウェイの条件を満たしているため、すべてのペントミノは平面をタイル張りすることができます。^[2]各カイラルペントミノは反射されることなく平面をタイル張りすることができます。^[3]

ペントミノの完全なセットを含む最も古いパズルは、1907年に出版されたヘンリー・デュドニーの著書「カンタベリーパズル」に登場しました。 ^[4]ペントミノの完全なセットを含む長方形のタイリングの最も古いものは、1935年の「プロブレムリストフェアリーチェスサプリメント」に登場し、さらにタイリングの問題がPFCSとその後継であるフェアリーチェスレビューで探求されました。^{[5] [6] : 127}

ペントミノは、1953年にアメリカの教授ソロモン・W・ゴロムによって正式に定義され、後に1965年に著書『ポリオミノ：パズル、パターン、問題、およびパッキング』で定義されました。^{[1] [7]}ペントミノは、1965年10月のサイエンティフィック・アメリカンの「数学ゲーム」コラムでマーティン・ガードナーによって一般に紹介されました。ゴロムは、古代ギリシャ語のπέντε / pénte（5）とドミノの-ominoから「ペントミノ」という用語を造り出し、「ドミノ」の「d-」をギリシャ語の接頭辞「di-」（2）の形であるかのように空想的に解釈しました。ゴロムは、12個のフリーペントミノに、アルファベットの末尾（TUVWXYZ）とともに記憶術FILiPiNoを使用して、類似するラテンアルファベットの文字にちなんで名前を付けました。 ^{[8] ：23}

ジョン・ホートン・コンウェイは、ペントミノの別のラベル付け方式を提案した。I の代わりに O、L の代わりに Q、F の代わりに R、N の代わりに S を使用する。文字との類似性は、特に O ペントミノでは劣るが、この方式にはアルファベットの連続する 12 文字を使用できるという利点がある。これはコンウェイのライフ ゲームを議論する際に慣例的に使用され、たとえば F ペントミノの代わりに R ペントミノについて話す。

• F、L、N、P、Y は 8 通りの方向で配置できます。4 通りは回転、4 通りは鏡像です。対称群は恒等写像のみで構成されます。
• T と U は、回転によって 4 方向に方向付けることができます。グリッド線と揃った反射軸を持ちます。対称群には、恒等要素と正方形の辺に平行な線での反射という 2 つの要素があります。
• V と W も回転により 4 方向に方向付けることができます。グリッド線に対して 45° の反射対称軸を持ちます。対称群には恒等反射と対角反射の 2 つの要素があります。
• Z は 4 つの方法で方向付けることができます。2 つは回転、もう 2 つは鏡像です。点対称性があり、これは2 次回転対称性としても知られています。その対称群には、恒等と 180° 回転の 2 つの要素があります。
• 回転によって 2 通りの方向に向けることができます。 2 つの反射対称軸があり、どちらもグリッド線と一致しています。 対称群には、恒等、2 つの反射、180° 回転の 4 つの要素があります。 これは、順序 2 の二面体群であり、クラインの 4 群とも呼ばれます。
• X は一方向にしか向けることができません。グリッド線と対角線に揃った 4 つの反射対称軸と、4 次回転対称性を持ちます。対称群である 4 次二面体群には 8 つの要素があります。

F、L、N、P、Y、Z ペントミノはキラルです。これらの反射 (F′、J、N′、Q、Y′、S) を加えると、片面ペントミノの数は 18 になります。回転も別個であると見なされる場合、最初のカテゴリのペントミノは 8 倍、次の 3 つのカテゴリ (T、U、V、W、Z) のペントミノは 4 倍、I は 2 倍、X は 1 倍とカウントされます。この結果、5×8 + 5×4 + 2 + 1 = 63 個の固定ペントミノになります。

F、L、N、P、Y ペントミノの 8 つの可能な方向と、T、U、V、W、Z ペントミノの 4 つの可能な方向が図に示されています。

• 8つの可能な方向
• 
  Fペントミノ
• 
  L-ペントミノ
• 
  N-ペントミノ
• 
  P-ペントミノ
• 
  Yペントミノ

• 4つの可能な方向
• 
  Tペントミノ
• 
  Uペントミノ
• 
  Vペントミノ
• 
  Wペントミノ
• 
  Zペントミノ

一般に 2D 図形にはさらに 2 つのカテゴリがあります。

• 90° 回転することで 2 方向に方向付け可能であり、2 つの反射対称軸が対角線と一直線に並んでいます。このタイプの対称性には、少なくともヘプトミノが必要です。
• 2 つの方向に向きを変えることができ、互いの鏡像となること (例:スワスティカ)。このタイプの対称性には、少なくとも 1 つのオクトミノが必要です。

標準的なペントミノ パズルは、長方形の箱をペントミノでタイル状に並べることです。つまり、重なり合うことなく隙間なく箱を覆うことです。12 個のペントミノはそれぞれ 5 単位の正方形の面積を持っているため、箱の面積は 60 単位である必要があります。可能なサイズは 6×10、5×12、4×15、3×20 です。

6×10 の場合は、1960 年にコリン・ブライアン・ハゼルグローブとジェニファー・ハゼルグローブの夫婦によって初めて解決されました。^[9]長方形全体を回転および反転することで得られる些細なバリエーションを除き、ペントミノのサブセットの回転および反転 (これにより、簡単な方法で追加の解が得られる場合があります) を含めると、解の数は正確に 2,339 個あります。5×12 のボックスには 1010 個の解があり、4×15 のボックスには 368 個の解があり、3×20 のボックスには 2 個の解しかありません (1 つは図に示されており、もう 1 つは L、N、F、T、W、Y、および Z ペントミノで構成されるブロック全体を回転することで示されている解から取得できます)。

8×8の長方形の中央に2×2の穴がある、やや簡単な（より対称的な）パズルは、1958年にダナ・スコットによって解かれました。 ^[10]解法は65通りあります。スコットのアルゴリズムは、バックトラッキングコンピュータプログラムの最初の応用の1つでした。このパズルのバリエーションでは、4つの穴を任意の位置に配置できます。外部リンクの1つはこのルールを使用しています。

このような問題を解決するための効率的なアルゴリズムは、例えばドナルド・クヌースによって説明されています。^{[11]現代の}ハードウェアで実行すると、これらのペントミノパズルはわずか数秒で解くことができます。

このようなパターンのほとんどは解くことができますが、例外として、各穴のペアをボードの 2 つの角の近くに配置して、両方の角に P ペントミノしか取り付けられないようにしたり、T ペントミノまたは U ペントミノを角に押し込んで別の穴を作成したりすることがあります。

ペントミノ集合は、単一の長方形のみで構成される 単純なモノミノ集合とドミノ集合を除いて、長方形に詰め込むことができる唯一の自由ポリオミノ集合です。

ペンタキューブは、5 つの立方体からなるポリキューブです。片面ペンタキューブ 29 個のうち、ちょうど 12 個が平ら (1 層) で、1 マスの深さまで押し出された 12 個のペントミノに対応します。

ペンタキューブパズルまたは3Dペントミノパズルは、3次元の箱を12個の平らなペンタキューブで埋めること、つまり重なりや隙間なく覆うことに相当します。各ペンタキューブの体積は5単位立方体なので、箱の体積は60単位である必要があります。可能なサイズは2×3×10（12解）、2×5×6（264解）、3×4×5（3940解）です。^[12]

あるいは、それ自体が 3D である 5 つの立方体の組み合わせ、つまり、12 個の「平坦な」単層の厚さの立方体の組み合わせ以上のものも考えられます。ただし、ペントミノを押し出して形成される 12 個の「平坦な」ペンタキューブに加えて、6 セットのキラル ペアと 5 つの追加ピースがあり、合計 29 個の潜在的なペンタキューブ ピースが形成され、合計 145 個の立方体 (=29×5) になります。145 個は 29×5×1 のボックスにしか詰められないため、平坦でないペントミノを含めることはできません。

ペントミノだけをベースにした ボードゲームもあります。このようなゲームは単に「ペントミノ」と呼ばれることが多いです。

ゲームの 1 つは、2 人または 3 人のプレイヤーが 8×8 のグリッド上でプレイします。プレイヤーは交代でペントミノをボード上に置きますが、既存のタイルと重ならないようにし、同じタイルを複数回使用しないようにします。目的は、ボード上にタイルを最後に置けるプレイヤーになることです。このバージョンのペントミノは「ゴロムのゲーム」と呼ばれています。^[13]

2人用バージョンは1996年にヒラリー・オーマンによって弱く解かれました。約220億の盤面の位置を調べた結果、先手勝ちであることが証明されました。^[14]

ペントミノや類似の形状は、他の多くのタイルゲーム、パターン、パズルの基礎にもなっています。たとえば、フランスのボードゲーム「ブロックス」は、4 色のポリオミノセットを使用してプレイします。各セットは、ペントミノ (12)、テトロミノ (5)、トリオミノ (2)、ドミノ (1)、モノミノ (1) で構成されています。ゲーム「ペントミノ」と同様に、すべてのタイルを使い切ることが目標で、最後の動きでモノミノをプレイするとボーナスが与えられます。残っているブロックが最も少ないプレイヤーが勝ちます。

Cathedralというゲームもポリオミノに基づいています。^[15]

パーカー ブラザーズは1966 年に、マルチプレイヤー ペントミノ ボード ゲーム「ユニバース」をリリースしました。このゲームのテーマは、1968 年の映画「2001 年宇宙の旅」の削除されたシーンに基づいています。このシーンでは、宇宙飛行士がHAL 9000 コンピューターを相手に 2 人用ペントミノ ゲームをプレイしています(別の宇宙飛行士がチェスをプレイしているシーンは保持されています)。ボード ゲームのボックスの前面には、映画のシーンと、このゲームを「未来のゲーム」と説明するキャプションが描かれています。ゲームには、赤、黄、青、白のペントミノが 4 セット付属しています。ボードには 2 つのプレイ可能な領域があります。2 人用の基本 10x10 領域と、2 人以上のプレイヤー用に各サイドに 25 個のマス (10 個の列がさらに 2 つと、5 個のオフセット列が 1 つ) があります。

ゲームメーカーの Lonpos は、同じペントミノを使用するものの、ゲーム平面が異なるゲームを多数提供しています。同社の101 Game は5 x 11 の平面を使用しています。平面の形状を変更することで、何千ものパズルをプレイできますが、印刷されているパズルは比較的少数に限られています。

• テトリスはペントミノパズルからヒントを得たものですが、4ブロックのテトリミノを使用しています。ベル研究所の Plan 9に含まれるゲーム5sやMagical Tetris Challengeなど、一部のテトリスのクローンやバリエーションではペントミノが使用されています。
• Daedalian Opus では、ゲーム全体を通してペントミノ パズルが使用されます。

ペントミノはアーサー・C・クラークの1975年の小説『インペリアル・アース』の重要なサブプロットに登場した。クラークはまた、このゲームと自分がいかにしてこのゲームに夢中になったかを記したエッセイも書いている。^[16]

これらは、2003年に出版されブレット・ヘルクイストがイラストを描いたブルー・バリエットの『チェイシング・フェルメール』やその続編『ザ・ライト3』『ザ・カルダー・ゲーム』にも登場した。^[17]

2012年6月27日のニューヨークタイムズのクロスワードパズルでは、横37番目の11文字の単語のヒントは「このパズルの黒い四角で形成される12個の図形の完全なセット」でした。^[18]

• テトリミノ
• ヘキソミノ

ウィキメディア・コモンズには、ペントミノに関連するメディアがあります。

• タイルパズル
• 大聖堂のボードゲーム
• ソロモン・W・ゴロム

• ペントミノの構成と解法 多くの古典的な問題に対する解法の網羅的なリストで、各解法が他の解法とどのように関連しているかを示します。