Nクイーンは今のコンピュータでは絶対解けない。ギズモード・ジャパンこのページではJavaScriptを使用しています。JavaScriptをONにしてください。NEWCATEGORYTAGFEATUREfacebookTwitterYoutubeRSSタグ一覧へTOPSCIENCENクイーンは今のコンピュータでは絶対解けない。解けたら1億円もらえるよNクイーンは今のコンピュータでは絶対解けない。英セント・アンドリューズ大教授が「コンピュータには絶対無理」と発表しました。反証できた方は100万ドル(約1億900万円)もらえます。上下左右斜めの8方向に遮るものがない限り進めるチェスの駒クイーン。これを他のクイーンに取られないように並べる配置を考えるのが「Nクイーン」の命題です。縦横のマス目はクイーンと同数という条件です。最初に登場したのは1850年代で、これまでに8マスの「エイト・クイーン」は計4,426,165,368通りのパターンから92通りの解が人力で見つかっています。Wikimedia解は92通り。8マスが解けたら9マス、10マスと駒を進めたくなるのが人類です。ところがこれが結構難しくて、現実的な時間枠の中で解を求めるプログラムについては、世界中の数学者とコンピュータ科学者の頭を悩ませ続けてきました。米マサチューセッツのクレイ数学研究所が世紀の変わり目に人類7つの最難問「ミレニアム懸賞問題」にリストアップして公募中なのですが、まだ解けていません。Gent教授が、実行可能な時間内でコンピュータで解を導き出すことは事実上不可能であると結論付ける論文を発表してしまいました。不可能なのかというと、今のコンピュータプログラムは1個1個の候補をしらみつぶしに当たって検証していく「総当り」攻撃のアプローチなので、処理にものすごく負荷がかかってしまうからです。27x27マス+27体まで増えただけで候補はなんと234,000,000,000,000通り!これでは1,000x1,000マスにクイーン1,000体投入した辺りでコンピュータにガタがきてエンドレスな計算処理地獄にはまり、文字通り何千年という単位で計算してなきゃならないので、計算してる間に人類終わっちまうなどの状況も考えられる。いうことらしいのです。Thought」(750万年かけて万物の解、42を導き出す)みたいな話ですよね...。Gent教授自身は友達にFacebookで「解ける?」と聞かれたのがきっかけで研究をはじめました。「これをすばやく解けるコンピュータプログラムが出現すれば、日々の暮らしに関わる最重要課題の多くが解決する。オンラインのあらゆる決済を保護している暗号化技術なんかも解けてしまう」とプレスリリースで書いています。確かに数学、コンピュータ、AIの研究への影響も大きいけど、金銭的インセンティブも膨大そうですよね。解いただけでミリオネアだし、市場デビューなんかした暁には一生左うちわです。Nightingale博士も当分出現はないと予想しています。あまりにも解の候補が多すぎるし、バックトラッキング(それ以上進めても解がないと分かると、一手だけ戻って解を探す方法)という手法にも限界があるため、現存する最速のコンピュータでも数年かかるそうなのです。「理論はともかくとして現実には、すばやく解けるプログラムには誰も近づけていないんですね。研究では、絶対解けないことの証明を目指しました」と、Nightingale博士は言っています。ムリと言われると闘志が湧きますよね。Problem(P≠NP予想、P対NP問題)」といいます。Jamesさんのブログ記事(英語)、Wikipediaの「エイトクイーン」の解説などご参考に。10:0025,288小学生か。12:3022,391ファーウェイが3月に新スマホ「P40シリーズ」を発表か。Razr」、早くもスクリーンが剥がれた報告。11:3011,113ソニーの新完全ワイヤレスがノイキャンの代わりに得たもの。11:0043,609DNAの90%が前代未聞。16:00486,358ついに!EUが充電規格統一を可決。22:00256,907ソニーの新完全ワイヤレスがノイキャンの代わりに得たもの。12:30シャオミがスマート・マスクの特許を米国で取得。12:00シャワーホースにも浴槽のカーブにもフィット。12:30シャオミがスマート・マスクの特許を米国で取得。12:00シャワーホースにも浴槽のカーブにもフィット。11の開発者向けプレビューが配布スタート。