破損したチェス盤の問題

切り裂かれたチェス盤の問題は、 1946 年にマックス ブラックが提起したタイル張りパズルであり、次のような問題を出します。

標準的な 8×8 のチェス盤(またはチェッカーボード) から対角の 2 つの角が削除され、62 個のマス目が残っているとします。これらのマス目をすべて覆うように、2×​​1 サイズのドミノを31 個配置することは可能ですか?

これは不可能なパズルです。これらの条件を満たすドミノの敷き方は存在しません。不可能であることの証明の 1 つは、角を取り除いたチェス盤には 1 色のマス目が 32 個、もう 1 色のマス目が 30 個ありますが、各ドミノは各色のマス目を同数覆わなければならないという事実を使います。より一般的には、チェス盤から任意の 2 つのマス目を取り除いた場合、取り除いたマス目が異なる色である場合に限り、残りのマス目をドミノで敷くことができます。この問題は、自動推論、創造性、数学の哲学のテストケースとして使用されてきました。

破壊されたチェス盤の問題は、グリッドとポリオミノのドミノタイル張りの一例であり、「ダイマーモデル」としても知られ、統計力学における問題の一般的なクラスに関する研究は、1937年のラルフ・H・ファウラーとジョージ・スタンレー・ラッシュブルックの研究にまで遡ります。 ^{[1]ドミノタイル張りは、舗装設計や}畳の敷き方にも実用化されてきた長い歴史があります。^[2]

切り裂かれたチェス盤の問題自体は、哲学者マックス・ブラックが著書『批判的思考』（1946年）で、その不可能性に対する色分けに基づく解決法を示唆して提唱した。^{[3] [4]}この問題が普及したのは、 ソロモン・W・ゴロム（1954年）、^[5] ジョージ・ガモフとマービン・スターン（1958年）、^[6] クロード・ベルジュ（1958年）、^{[4] [7]}マーティン・ガードナーがサイエンティフィック・アメリカンのコラム「数学ゲーム」（1957年）で論じた後の1950年代である。^[8]

自動推論における切断されたチェス盤問題の使用は、1964年にジョン・マッカーシーが提案したことに由来する。 ^{[9] [10]また、この問題は}認知科学において創造的洞察のテストケースとして研究されてきた。 ^{[11] [12] [13]}ブラックがこの問題を最初に思いついた動機である。^[3]数学の哲学では、数学的証明の性質に関する研究で検討されてきた。^{[14] [15] [16] [17]}

このパズルは完成不可能である。チェス盤に置かれたドミノは、常に 1 つの白いマス目と 1 つの黒いマス目を覆う。したがって、盤上に置かれたドミノの集合は、各色のマス目を同数覆うことになる。しかし、向かい合った 2 つのマス目は同じ色 (両方とも黒または両方とも白) である。これらが取り除かれると、その色のマス目が少なくなり、もう一方の色のマス目が多くなり、各色のマス目の数が不均等になり、盤を覆うことが不可能になる。^[8]同じ考え方から、同じ色のマス目 (反対側の角だけでなく) が 2 つチェス盤から取り除かれると、ドミノのタイル張りは存在しなくなることがわかる。 ^[18]

他にも不可能性を証明する方法がいくつか見つかっている。シュムエル・ウィノグラードの証明は帰納法から始まる。盤面の特定の配置において、ある列に前の列の垂直ドミノで覆われていないマス目が奇数個ある場合、次の列にも奇数の垂直ドミノが伸びる必要がある。最初の列には、前の列のドミノで覆われていないマス目が奇数個 (つまり 7) あることは明らかである。したがって、帰納法によれば、連続する 7 組の列のそれぞれには、奇数の垂直ドミノがあり、合計数は奇数となる。同じ理屈で、水平ドミノの合計数も奇数でなければならない。2 つの奇数の合計として、垂直と水平のドミノの合計数は偶数でなければならない。しかし、切り裂かれたチェス盤を覆うには、31 個のドミノが必要であり、これは奇数である。^{[19] [20]}別の方法は、切り取られたチェス盤の境界の周りの各色の辺を数える。各ドミノには各色の辺が3つあり、ドミノ間の各内部辺は反対色の境界と対になっているため、チェス盤のタイルを敷き詰められる領域では、辺の数は必ず同じになる。しかし、切り取られたチェス盤では、一方の色の辺がもう一方の色よりも多くなっている。^[21]

反対色の2つのマス目を取り除けば、残った盤面は常にドミノで敷き詰めることができる。この結果はゴモリの定理^[22]と呼ばれ、数学者ラルフ・E・ゴモリにちなんで名付けられ、1973年に証明が発表された。 ^{[18] [20]ゴモリの定理は、チェス盤のマス目によって形成される}グリッドグラフのハミルトンサイクルを使用して証明できる。反対色の2つのマス目を取り除くと、このサイクルは偶数個のマス目を持つ2つのパスに分割される。これらのパスは両方とも、従うことで簡単にドミノに分割できる。^[22]ゴモリの定理は、各色のマス目を1つだけ取り除く場合に特有のものである。各色のマス目を同数ずつ取り除くと、ドミノが敷き詰められていない領域が生じる可能性があるが、色分けに基づく不可能性証明は機能しない。^[23]

ポリオミノ上のドミノタイル張り問題、例えば切断されたチェス盤の問題は、群論の問題に変換するか^{[21] [24]}、または二部マッチングのインスタンスとして多項式時間で解くことができます。後者の定式化では、利用可能なチェス盤のマスごとに頂点を持ち、隣接するマスのペアごとに辺を持つ二部グラフが得られます。問題は、各頂点にちょうど 1 回接する辺のシステムを見つけることです。切断されたチェス盤の問題の不可能性の着色ベースの証明と同様に、このグラフにある色の頂点が他の色よりも多くあるという事実は、ホールの結婚定理の必要条件を満たしていないことを意味し、マッチングは存在しません。^{[23] [25] [26]この問題は、}制約充足問題として定式化し、緩和に半正定値計画法を適用することによっても解くことができます。^[27]

1964年、ジョン・マッカーシーは、破壊されたチェス盤を自動証明システムにとって難しい問題として提案し、これを一階述語論理で定式化し、この定式化の不可能性を自動的に判断できるシステムを求めた。^[9]この問題に関するほとんどの考察は、「概念的な意味で」の解決策を提供しているが、これはマッカーシーの問題の論理定式化には当てはまらない。^[28]グラフマッチングに基づく方法など一般的な方法が存在するにもかかわらず、マッカーシーの問題の論理定式化を解決するのは指数関数的に困難であり、[ ^{29] [30] [31]}このことは、より適切な問題表現に自動的に変更できる人工知能の方法^[32]と、異なる表現間の同等性を管理できる知識表現システムの必要性を浮き彫りにしている。 ^[10]短い証明は、追加の変数を使用した解決を使用するか、^[33]または回避可能なタイリングパターンの表現を許可して検索空間を削減できるより強力な証明システムで可能である。^[34]高レベルの証明支援システムは、色付けベースの不可能性証明を直接処理することができます。これには、Isabelle、^[35]、Mizarシステム、[ ^36]、Nqthmが含まれます。^[37]

同様の問題に、普通のチェス盤の角のマス目からスタートしたワジールが、すべてのマス目を一度ずつ訪れて、反対側の角のマス目でゴールできるかどうかという問題があります。ワジールは、垂直または水平（斜めには動かない）に1マスだけ移動できる妖精のチェスの駒です。切断されたチェス盤の問題の古典的な解決法と同様の推論を使用すると、このワジールのツアーは存在しません。たとえば、最初のマス目が白の場合、各移動で黒と白のマス目が交互になるため、完全なツアーの最後のマス目は黒になります。ただし、反対側の角のマス目は白です。^{[38]チェス盤のこの種のツアーは、} Numbrixと呼ばれるタイプのパズルの基礎にもなります。これは、特定のマス目の位置が与えられた手がかりと一致するツアーを求めるものです。^[39]角から角へのツアーが不可能であることは、1つの角に1、反対側の角に64という手がかりがあるNumbrixパズルが不可能であることを表しています。

ド・ブリュインの定理は、特定の直方体をより大きな直方体に詰め込むことが不可能であることに関する定理である。例えば、この定理によれば、6 × 6 × 6 の箱を1 × 2 × 4 の直方体で埋めることは不可能である。証明には、破壊されたチェス盤問題と同様のチェス盤の色付けの議論が用いられる。^[40]

ウィキメディア・コモンズには、 Mutilated chessboard problemに関連するメディアがあります。

• Gomory の定理 (Jay Warendorff 著、Wolfram Demonstrations Project)。