歴史あるチェスのパズル問題が現代数学における未解決問題の解明につながる可能性

1000年を超える歴史を持つボードゲーム「チェス」には単なるゲームの勝敗ではなく、そのルールに即したさまざまなパズルの課題「チェス・プロブレム」が存在しています。エイト・クイーンはチェスの駒のうち、8個のクイーンだけを使うパズルなのですが、その規模を大きく拡大して行くと、現代数学における未解決問題であり、1億円の賞金がかかる「P対NP問題」の解明につながるものと考えられています。

2017 | “Simple” chess puzzle holds key to $1m prize | University of St Andrews
https://www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php

Can You Solve the Million-Dollar, Unsolvable Chess Problem? - Atlas Obscura
http://www.atlasobscura.com/articles/queens-puzzle-chess-problem-solution-software

「エイト・クイーン」は1848年にチェスプレイヤーのマックス・ベッツェルによって提案されたパズル。8×8マスのチェス盤の上に、縦横と斜め方向にどこまででも進めるという駒・クイーンを8個並べるというものなのですが、その際には「どの駒も他の駒に取られるような位置においてはいけない」というルールが設定されています。このルールに従った場合にいくつの正解が存在するのか、長らくの間にわたって謎とされていたのですが、考案から100年以上が経過した1874年にGuntherが行列式を用いて解く方法を提案し、イギリスのグレイシャー(Glaisher)によって全解(基本解)が12個であることを確認しています。

この問題は、チェス盤の一辺のマスの数とクイーンの数を同一にしたn-クイーン問題とも呼ばれており、nの数が増えるに連れて飛躍的にその解数が増大することが知られています。記事作成時点で全ての解が判明しているのは、2009年にドレスデン工科大学で計算された「26-クイーン」で、その基本解は2789兆7124億6651万289個、転回形などのバリエーション解を含めると、その数は2京2317兆6996億1636万4044個にもなることがわかっています。

セント・アンドルーズ大学のコンピューターサイエンティストであるIan Gent博士らによる研究チームは、この「n-クイーン問題」から派生する「n-クイーン穴埋め問題」(n-Queens Completion)パズルの複雑性に関する(PDF)論文を作成しています。n-クイーン穴埋め問題は、チェス盤の上にあらかじめいくつかのクイーンの駒を並べておいた状態で、残りのクイーンを全て埋めるというパズル問題です。

基本的にこの問題を解決するためにはバックトラック法と呼ばれる、いわば「総当たり法」が用いられますが、全ての選択肢を試すためには膨大な時間が必要とされ、しかもマスとクイーンの数が多くなるとその時間は指数関数的に一気に増加します。Gent氏によると、この「n-クイーン穴埋め問題」を素早く解決できるコンピューターやアルゴリズムの開発が進むことで、我々が日々抱えている問題を解決する技術の進化が期待できるとのこと。先述のように、現代の科学でも解決できているn-クイーン問題は26×26マスの「26-クイーン」にとどまっており、穴埋め問題であってもそこから先へと進むためには、現在はまだ存在していない新しい技術を開発することが必須となってきます。

この問題は、2000年にアメリカのクレイ数学研究所が100万ドル(約1億1000万円)の賞金とともに設定したミレニアム懸賞問題の一つに数えられる「P対NP問題」の証明につながるものとされています。これは、「答えを見つけるのは難しいかもしれないが、答えがあっているかどうかは素早くチェックできる問題」のことをNP問題、「簡単に素早く解ける問題」のことをP問題とした時に、「素早く解けるP問題はすべて答えを素早く確認できるNP問題である」ことは証明されているが、その逆、つまり「答えを素早く確認できるNP問題はすべて、素早く解けるか？」という問題を証明するというもの。 これを解くためには膨大な量の計算を素早く行うことが必要になり、現代のコンピューター技術でも解決までには数万年の時間が必要になると考えられています。