エッジマッチングパズル
タイルパズル
部分的に完成したEternity IIのエッジマッチングパズル

エッジマッチング パズルは、隣接するタイルのエッジが一致するように、エッジが色やパターンで区別される (通常は正多角形) 領域をタイル化するタイル パズルの一種です。

エッジマッチングパズルはNP完全であることが知られており、同等のジグソーパズルやポリオミノパッキングパズルとの変換に適応できます。[1]

最初のエッジマッチングパズルは、1892年に米国でELサーストンによって特許を取得しました。[2]現在市販されているエッジマッチングパズルの例としては、エターニティIIパズル、タントリックス、カドンエンタープライズのエッジマッチングパズルシリーズ、iPhoneアプリのエッジマッチパズルなどがあります。

注目すべき変化

マクマホンスクエア

マクマホン方陣の最大の単色領域を持つ解法[3]

マクマホン・スクエアは、1921年に様々な図形の辺の色分けに関する論文を発表したイギリスの数学者パーシー・マクマホンによって考案された、娯楽的な数学パズルの名称です。[4]このパズルでは、正方形の辺として3色のあらゆる組み合わせからなる24枚のタイルを使用します。タイルは6×4の長方形領域に、すべての辺が一致するように配置する必要があります。さらに、長方形の外側の辺には1色のみを使用します。[5]

このパズルは、4色の順列を持つタイルを10×7のマスに配置することで拡張できます。[6]いずれの場合も、正方形は王牌の部分集合であり、回転によって類似する牌の数が減少します。解の数は数千に及びます。[7]

マクマホン スクエアは、そのアイデアのバリエーションとともに、マルチマッチとして商品化されました。

テトラベックス

GNOME テトラベックス

TetraVexは、プレイヤーに正方形のグリッドとタイルの集合を提示するコンピュータゲームです。デフォルトでは、3×3のグリッドに9つの正方形タイルが配置されます。各タイルには、各辺に1桁の数字が1つずつ、合計4つあります。ゲームの目的は、タイルをグリッドの正しい位置に配置して、できるだけ早くパズルを完成させることです。タイルは回転させることはできません。また、隣接する辺の数字が一致している場合にのみ、2つのタイルを隣り合わせに配置することができます。[8] [9]

TetraVexは、ドナルド・クヌースが『The Art of Computer Programming』シリーズの最初の著書『第1巻：基礎アルゴリズム』の382ページで述べた「平面のタイリング問題」に着想を得たものです。この名前は、 Windows Entertainment Pack 3向けにVisual Basicを開発し、その初代バージョンの設計者であり開発リーダーを務めたスコット・ファーガソンによって付けられました。[10]

TetraVexはGNOMEゲームコレクションのオープンソースゲームとしても入手可能です。[11]

TetraVexの配置の可能な数は数えられます。ボードには、必ず一致する縦横のペアと、任意に選択できる端の数字があります。したがって、 10個の数字、つまりボードの可能な組み合わせの選択肢があります。 n × n {\displaystyle n\times {}n} n （ n − 1 ） {\displaystyle n(n-1)} 4 n {\displaystyle 4n} 2 n （ n − 1 ） + 4 n ＝ 2 n （ n + 1 ） {\displaystyle 2n(n-1)+4n=2n(n+1)} 10 2 n （ n + 1 ） {\displaystyle 10^{2n(n+1)}}

TetraVexパズルに解があるかどうかを判断することは、一般的にNP完全である。[12]その計算手法には、ダグラス・ラチフォードアルゴリズムが用いられる。[13]

六角形

シングルクロスサーペンタイル

サーペンタイルは、Psyche-Paths、Kaliko、 Tantrixといった様々な抽象戦略ゲームで使用される六角形のタイルです。各サーペンタイルの辺はペアになっており、六角形内で同じ辺の色が奇数回出現しないようタイルの配置が制限されています。

三次元

数学的には、エッジマッチングパズルは2次元です。3次元エッジマッチングパズルは、ユークリッド空間において平坦ではないパズルであり、正多面体の表面のような3次元領域をタイル張りするパズルです。前述のように、多角形のピースには区別されたエッジがあり、隣接するピースのエッジが一致する必要があります。

3Dエッジマッチングパズルは、1892年にELサーストンが取得した特許が失効したため、現在、米国特許による直接的な保護を受けていません。[2]現在市販されているパズルの例としては、ドデック・デュオ、エニグマ、メンタル・ミザリー、[14]カドン・エンタープライズの3次元エッジマッチングパズルなどがあります。[15]

エッジマッチングの組み込み

カルカソンヌというボードゲームでは、正方形のタイルを配置できる場所を制限するためにエッジマッチングを採用しています。オリジナルのゲームでは、フィールド、道路、都市の3種類のエッジが存在します。

参照

参考文献

  1. ^ Erik D. Demaine、Martin L. Demaine、「ジグソーパズル、エッジマッチング、ポリオミノパッキング：接続と複雑性」（PDF） 。 2007年8月12日閲覧。
  2. ^ ab 「Robのパズルページ：エッジマッチング」。2007年10月22日時点のオリジナルよりアーカイブ。2007年8月12日閲覧。
  3. ^ ガードナー、マーティン (2009).球詰め、ルイス・キャロルとリバーシ. ケンブリッジ大学出版局.
  4. ^ マクマホン、パーシー・アレクサンダー (1921). 「新しい数学的娯楽」. ゲルシュタイン - トロント大学. ケンブリッジ大学出版局.
  5. ^ Steckles, Katie. Blackboard Bold: MacMahon Squares. 2021年3月10日閲覧。
  6. ^ Guy. 31の立方根. Wang Tiles. 2021年4月12日閲覧。
  7. ^ ウェイド・フィルポット（クレジット表記）. Kadon Enterprises. Multimatch. 2021年4月12日閲覧。
  8. ^ Whittum, Christopher (2013).オープンソースで教育を活性化する. 32ページ.
  9. ^ マルセル、ガニェ (2006)。Ubuntu Linux への移行。
  10. ^ 「Visual Basicの誕生」Forestmoon.com . 2010年5月11日閲覧。
  11. ^ 「ライセンス - README」. gnome-games . gnome.org. 2011年. 2012年10月2日閲覧。
  12. ^ 竹永康彦; ウォルシュ・トビー (2006年9月15日). 「TetraVexはNP完全である」 .情報処理レター. 99 (5). 情報処理レター, 第99巻, 第5号, 171–174頁: 171–174 . doi :10.1016/j.ipl.2006.04.010. S2CID  7228681.
  13. ^ リンストロム、スコット・B、シムズ、ブレイリー（2020年）『ダグラス・ラッチフォードの60年』ケンブリッジ大学出版局。
  14. ^ 「Robのパズルページ：パターンパズル」 。 2009年6月22日閲覧。
  15. ^ 「Kadon Enterprises、Edgematchingについての詳細」 。 2009年6月22日閲覧。
  • エーリッヒのマッチングパズルコレクション
  • ロブ・ステグマンによるロブのパズルページ
  • エッジマッチングスクエア
スタブアイコン

この組み合わせ論関連の記事はスタブです。記事を拡張することでWikipediaに貢献できます。

「https://en.wikipedia.org/w/index.php?title=Edge-matching_puzzle&oldid=1299980512#TetraVex」から取得