FC2ブログ

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

2017年09月05日 17時17分 メモ

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

https://gigazine.net/news/20170905-million-dollar-chess-problem/


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問題はすべて、素早く解けるか?」という問題を証明するというもの。 これを解くためには膨大な量の計算を素早く行うことが必要になり、現代のコンピューター技術でも解決までには数万年の時間が必要になると考えられています。

スポンサーサイト



数学のエキスパートが3ヶ月かけて作成した「世界一難しい数独」

2010年08月22日 21時05分 メモ

数学のエキスパートが3ヶ月かけて作成した「世界一難しい数独」

https://gigazine.net/news/20100822_hardest_sudoku/


数独というのは一般的に、初めから埋められている数字が少ないほど難しく、上級者は一目見ただけで大体その問題の難易度がわかるそうです。しかし、「これは手応えがありそうだ」と感じた数独に、「勘」を使わないと「論理」だけでは解けない部分があったり、解が複数存在すると判明したときには、がっかりするのではないでしょうか。そういった数独は、数独として正しくありません。

フィンランド人の科学者が、解が一つだけ存在し「当てずっぽう」ではなく「論理」のみですべてのマスを埋めることができる「正しい数独」の中で限りなく難しい、「世界一難しい数独」を作り出すことに成功したそうです。


詳細は以下から。9 by 9 Sudoku Solver

こちらがその「世界一難しい数独」。ω-3脂肪酸のサプリメントを販売するEfamol社の依頼で、科学と応用数学の博士号を持つフィンランド人の環境科学者Arto Inkala博士が手がけた数独作成プログラムにより作成されました。


チェスや将棋のように、「ここにこの数字を入れたらあそこがあの数字で埋まり……」と「数手先」まで考えることにより解く数独では、何手先まで考えねばならないかというその数が増えるほど、難易度は高くなります。

作成には3ヶ月かかったというこの数独ですが、「当てずっぽう」ですぐに解けてしまう人もいるかもしれません。「3つか4つのまぐれ当たりにより、15分や30分で解けてしまい、どこがそんなに難しいんだ、と疑問に思う人もいるかもしれません。しかし、このパズルをロジックのみで解くには、普通は数日間はかかるでしょう」とInkala博士は語ってます。

余暇の時間にパズル作りを楽しむというInkala博士。科学と応用数学の博士号を持つInkala博士自身は数学のエキスパートですが、「パズルを解く人は、足し算ができる必要すらありません。論理的思考と注意力、そして粘り強さが数独を解く鍵となります」と語っています。


解答はこちら。なお、この数独に挑戦した編集部員は30分であきらめてしまったので、解答作成には9 by 9 Sudoku Solverを使用しています。

数独の初期ヒント最小個数は「17」、それ未満では解けないと数学者が結論

2012年01月09日 13時14分 メモ

数独の初期ヒント最小個数は「17」、それ未満では解けないと数学者が結論

https://gigazine.net/news/20120109-sudoku-puzzle-starting-digits-is-17/

by Miss_Bathory

日本だけではなく海外でも人気の高い数字パズル「数独(Sudoku)」。初期に配置するヒントの数は20個~30個ぐらいのものが多く、最小では17個のものが確認されていますが、問題として成立するのがいったいどのラインなのかは結論が出ていなかったのですが、アイルランドの数学者が「ヒントが16以下だと解けない」と結論を出しました。

Mathematician claims breakthrough in Sudoku puzzle : Nature News & Comment



Gary McGuire's Minimum Sudoku Page, Sudoku Checker

ユニバーシティ・カレッジ・ダブリンの数学者Gary McGuireさんは、数独においてヒントが16個以下のものは解法を持ちえないということを証明しました。このMcCuireさんの証明は、数学者たちの中で話し合いが持たれた結果、おそらく正しいであろうという結論が出されています。


「数独」とは「数字は独身に限る」の略。この名前はパズル制作会社ニコリが作ったもので、ニコリの登録商標になっており、日本のみならず海外でも「Sudoku」で通じます。また、ナンバープレイス(ナンプレ)とも呼ばれています。

by Wil C. Fry

数独は、最もポピュラーなものだと、9x9に区切られた格子の中に「タテとヨコで同じ数字が複数登場してはならない」「3x3の小格子の中で同じ数字が登場してはならない」というルールに従って、1~9までの数字を入れていくというもの。最初からいくつかの数字がヒントとして初期配置されており、オーソドックスなものではだいたい25個ぐらいの数字が記入されており、おおむね難度が上がると初期配置の数字の数が減ります。

by Jafin89

これまでに登場したパズルの中で、ヒントが最小だったのは17個で、16個以下のものは作れないのではないかと言われていました。これを証明するには16個のヒントが与えられた数独を解くという方法がありますが、コンピューターで計算しても相当な時間が掛かります。そのため、McGuireさんは問題を「hitting-set algorithm」を用いて単純化。2年間で700万CPU時間をかけて挑戦し、答えにたどり着きました。

McGuireさんは、今回の解法が数独だけではなく、遺伝子配列解明技術の分析や、セルラーネットワーク、その他の研究者による分析などに有用に用いられるのではないかと期待しています。

ちなみに、McGuireさん自身は数独よりもクロスワードパズルの方が好きなのだそうです。

プロフィール

檜原転石

Author:檜原転石
FC2ブログへようこそ!

世の中は無名の一人でも変えられる

最新トラックバック

カテゴリ

検索フォーム

ブロとも申請フォーム

QRコード

QR