この記事は、列挙子の組み合わせを解く経験のある読者と、難しいプログラミングタスクが好きな読者を対象としています。
それは150年以上にわたって続いている戦いです。 数学者は長い間チェスの駒で戦争を始めており、おそらく女王はこの戦いで最も頑固な人物です。 過去50年間で、コンピューターは数学者の助けになりましたが、それでも十分ではありません。
この最も強力な図に関連付けられている多数のタスクがあります。 たとえば、クイーンズの優位性の問題：ボードのすべてのフィールドを制御するために必要なクイーンズの最小数は何ですか？ 一般的な場合、これは約8 x 8ボード（答えは5）ではなく、サイズnx nのボードです。 さらなる一般化は、女王が立方体のボード上に置かれる（そして26方向のいずれかにビートする）3次元空間への移行に関連する場合があります。 しかし、我々は女王の可能な取り決めのリストに関連する問題のクラスを検討しています。
女王をチェス盤に置く問題は、おそらく最もよく知られている難しい問題の1つです。 可能性のある変形の1つでは、次のように聞こえます。nxnのサイズのチェス盤にn個のクイーンを配置して、互いに勝負しないようにする方法はいくつありますか？ このタスクは、学校でコンピューターサイエンスのレッスン（n = 8の場合）と雇用で提供されます。 ただし、パラメータnの値が十分に大きい場合、この「運動」はすでに深刻な世界的な問題です。
最初は、通常のパズルとしてタスクが定式化されました。標準の8 x 8ボードに8人のクイーンを配置して、お互いに勝てず、すべてのそのような配置を提示する必要があります（ところで、92個あります）。 彼女はガウスを含む多くの有名な数学者に従事していました。 任意のボードサイズへの問題の一般化は1850年に提案され、それを解決するためのアルゴリズムの積極的な検索は1960年代、つまりコンピューター技術の急速な発展とともに始まりました。 この問題の例を使用して、リターンサーチ、分割統治法、制約プログラミングなどの古典的なアルゴリズムのアプローチの仕事が示されました。メソッド。
実際、なぜこのようなタスクが必要なのでしょうか？ ボード上で不幸な女王を追いかけ、可能な限り大きなnの値に対して誰がより速くそれを行うかを競うことのポイントは何ですか？ 実際、科学にはいわゆる「共通の問題」というクラスがあり、そのすべてが直接適用されるわけではありませんが、それらを解決するために多額のお金を払うか、科学理論全体を開発するか、すでに知られているものに追加することなく、少なくとも一歩前進しようとすることは不可能です科学のセクション。 そのため、n = 26の問題を解決するために、科学者はグループ理論でいくつかの特別な方法を開発し、その上で数人が博士論文を擁護しました。 いわゆるQ（26）の解決策は、2009年7月11日にビデオカードで計算されました。これについては、著者のページで詳しく説明されています 。
シーケンスQ（n）は、整数A000170 （eng）の整数シーケンスの百科事典に登録されています。
この問題を解決する試みは、既存のマシンの計算能力にさらにかかっています。 原則として、Roadrunner（複数ペタフロップスのパフォーマンスを備えた）のようなコンピューターでは前に進むことができますが、遅かれ早かれ、スーパーコンピューターが処理できない値nが存在し、誰もまだ明示的な公式を導き出すことができません。 配置の数が次数n！/ C nの量であるような定数Cが存在するという強い仮説を考慮します。 この定数は2.54にほぼ等しいと考えられていますが、n = 26の答えがわかったので、定数は洗練され、2.48に等しいと見なされます。 いずれにせよ、この方向に大きなブレークスルーは期待できません。
このため、より単純な問題を解決するための試みが興味深いです。ボードnxnにkクイーンを配置します。ここで、kはnに依存しない固定数です。 たとえば、k = 1の場合、配置の数は明らかにn 2です。 k = 2の場合、答えはn（n-1）（n-2）（3n-1）/ 6です。 約1か月半前に、k = 5の明示的な公式を導き出すことができました（k = 3およびk = 4の場合、公式はすでに知られていました）が、この公式を簡略化（美しくしたかった）している間、チェコ共和国の同志もそれを導き出し、公開しました単純化されていない形式。 応答ステップは、k = 6の明示的な式のみになりました。 これは、私のサイトの1つでの競争の一環として導き出そうとしている公式です。 詳細な説明と現在の結果はこちらです。 現時点では、競争は競争のようなものです。誰がnの最大の価値に対する答えを見つけるでしょう。 練習によって、n = 15に到達する人はほとんどいないことがわかるため、体力をテストするのに最適な方法です。 残念ながら、もちろん。 [ 補足05/10/2010。 現時点では、競争が完了し、式が受信されます ]。
クイーンの数が固定され、ボードのサイズが可変の場合、生成関数の分母の絶対値は1に等しい（おそらく複雑な）根を持つことが証明されています。 この状況では、連続するn = 1,2,3の答えを知って、生成関数を推測できます。たとえば、5つのクイーンの問題の場合、n = 38（分母は37）の答えを数える必要がありました。 6人の女王の場合、明らかに、学位は80をわずかに下回ります（私の経験的考察から）。
他のバージョンの問題もあります。たとえば、ボードが正方形ではなく、長方形またはトーラスの形状である場合（つまり、ボードの境界を越えてクイーンの出口が反対側から現れるのと同等）です。 また、各クイーンが他の1つのクイーンと正確に勝つオプションもあります。 おなじみの物理学者は、そのような問題には実際の物理的応用があると主張しているが、私には知られていない。
産業（または基礎研究にあまり関係のない別の分野）で働く多くの人々は、そのような運動を時間の無駄と考え続けています。 彼らは、美しく直感的なインターフェースを作成する方が便利であり、これが効率的に機能するかどうかは二次的な問題だと彼らは言います。 この場合、これは完全に正しいわけではありません。 このような問題を解決することで、科学コミュニティはお互いのスキル、科学学校のレベルを示したり、成功の他の指標を示したりすることができます。 そして、これの意味は、社会に本当に役立つ同様のタイプのタスクが発生すると、通常、この分野の科学者の最も先進的なチームを解決するために与えられるということです。 一方、このタスクまたはそのタスク自体に実用的な価値がない場合でも、そのソリューションにより、数学とプログラミングの新しい手法を開発できます。
このタスクの多様性と重要性を理解するには、上記の整数シーケンスの百科事典に移動して、検索で「Queen」と入力します。 女王が出会う250を超えるタスクが提供されます。 さらに、これらのタスクのいくつかは、チェスとは関係のない科学的な（完全ではない）問題と驚くほど重複しています。
ソースのリスト
数学者対 女王様
All Articles