10億人の女王の問題解決策、または「n-Queens分布問題の解決策リストのパターンの研究」

まとめ

n-Queens分布の問題に対するすべてのソリューションの順次リストで確立された法律について説明します。 以下が確立されています。

• nの値が大きくなると、すべてのソリューションの一般リストに含まれる完全なソリューションの割合が減少します。
  
• 完全なソリューションは、リスト内で互いに近くにある完全なソリューションが見つかる可能性が最も高いように、すべてのソリューションの順次リストで配布されます。
  
• すべてのソリューションの一般的なリストには、完全なソリューションの順序に対称性があります。 リストの先頭からi番目の位置で解が完全な場合、n-i + 1の位置にあるリストの末尾からの対称解も完全です（解の対称性の規則）。
  
• すべてのソリューションのリストに対称的に配置された短いおよび完全なソリューションのペアは相補的です-対応するラインの位置インデックスの合計は一定であり、n + 1（ソリューションの相補性の規則）に等しくなります。 これは、すべての完全なソリューションのリストの前半のみが「一意」であり、リストの後半からの完全なソリューションは相補性ルールに基づいて取得できることを示唆しています。 このルールの結果は、nの任意の値に対して、完全なソリューションの数が常に偶数になるという事実です。
  
• ソリューション行列の行のセルのアクティビティは、この行列の中央を通る水平軸に対して対称です。 つまり、i番目の行のセルのアクティビティは、行n-i + 1のセルのアクティビティと常に一致します。 アクティビティとは、完全なソリューションのリストの対応する行でセルインデックスが発生する頻度を意味します。 同様に、ソリューションマトリックスの列のセルのアクティビティは、マトリックスを2つの等しい部分に分割する垂直軸に関して対称です。
  
• nに関係なく、すべてのソリューションの順次検索では、最初の完全なソリューションは特定の短いソリューションのシーケンスの後にのみ表示されます。 短い決定の初期シーケンスのサイズは、nとともに増加します。 nの偶数値の最初の完全な解が現れるまでの短い解のリストの長さは、最も近い奇数の値よりも大幅に長くなります。
  
• 困難が前進し始め、最初の短い決定が形成される決定マトリックスの行は、黄金比規則に従ってマトリックスを分割します。 nの値が小さい場合、このような結論は近似値になりますが、nの値が増加すると、そのような結論の精度は標準ルールのレベルまで漸近的に増加します。
  

この出版物は、論文「Modeling of Artificial Intelligence、2018、5（1）」に掲載された記事[1]の主な結果を示しています。 Habréには、nクイーンの問題に関連する作品がありました： [2] 、 [3] 、
nxnサイズのチェス盤でnクイーンを配布する問題には長い歴史があります。 もともとは、1848年にM. Bezzel [4]によって通常のチェス盤の知的作業として策定されました。 時間が経つにつれて、問題の声明はF. Nauck [5]によって拡張され、チェス盤のサイズは任意の値を取ることができました。

はじめに

問題のステートメントは非常に簡単です：サイズnxnのチェス盤にn個の女王を配布する必要があります。これにより、各行、各列、および女王がいるセルを通過する左右の対角線上に女王が1人しかいません。 このタスクは、誰かに理解したり説明したりするのは簡単ですが、解決するのは困難です。 実際には、解決策を得るために各行にクイーンを配置できるルールはありません。 解決策は、特定の行のクイーンの配置のさまざまなバリエーションを列挙することによってのみ取得できます。 ただし、この解決方法の複雑さは、nの増加とともにクイーンの配置のすべてのバリアントの数が指数関数的に増加するという事実にあります。 さらに、特定の行の自由な位置にクイーンを配置するために一歩前進すると、残りの行の自由な位置のリストが変更されます。また、検索ブランチを形成するために1つのステップに戻るとき、以前に実行されたアクションのトレースをクリアする必要があります。

n-Queens問題を解決するさまざまな側面に関連する出版物が多数あります。 それらは、研究のいくつかの分野に帰することができます：チェス盤（n）のサイズの特定の値のすべての完全なソリューションの検索、nのさまざまな値の1つのソリューションを見つけるための迅速なアルゴリズムの開発、kクイーンの任意の構成のための完全なソリューションの完全な問題のソリューション、質問アルゴリズム計算の計算の複雑さ、および問題の元の定式化のさまざまな修正。 これらの分野に精通するために、B。Jordan、S. Brett [6]およびIP Gent、C. Jefferson、P. Nightingale [7]による興味深い出版物をお勧めします。 特に注目すべきは、Unitersiteit Leidenのグループによって作成され、n-queens問題に関連する342の出版物へのリンクを含むWalter Costersがサポートするインターネット出版物[8]です （2018年12月現在）。

n-Queens問題は150年以上にわたって活発であり、この間に膨大な数の出版物が登場しましたが、この問題を解決した結果のパターンを見つけることに関連する仕事は見つかりませんでした。 すべてのソリューションの検索に関連するプロジェクトのほとんどは、見つかったソリューションを保存せず、「内部」にあるものを確認しなかった可能性があります。問題の声明には、他の主要な目標があり、尊敬される同僚がそれらを達成しました。 しかし、リモートでは、状況は人が朝食のために卵を沸騰させるが、それらを食べるのではなく、それらを捨て、ゆで卵の数だけを彼の記憶に残すときと似ているように思えた。 データがランダムでない場合、その規則性を見つけることができない場合でも、データに一定の規則性があるはずだと常に確信しています。 この確信が、このタスクでパターンを検索する理由でした。

Habrコミュニティのメンバーに有益な情報を提供したいという要望に加えて、Habrのほとんどが優秀なプログラマーに、コンピューターシミュレーション（計算シミュレーション）などの開発の方向性にもっと注意を払ってほしいと思います。 研究方法として、このような「アルゴリズム数学」は、人工知能、ソフトウェアサイエンス、データサイエンスなど、多くの分野の「最先端」で使用されています。そして、実用化のための非常に複雑で重要なタスクはアルゴリズム数学に基づいて解決されると確信していますそうでなければ。

定義

以下、チェス盤のサイズを記号nで示します。 n個すべてのクイーンが常にチェスボードに配置されている場合、ソリューションは完全と呼ばれます。 他のすべてのソリューションは、正しく配置されたクイーンの数がn未満の場合-ショートソリューションと呼びます。 解の長さとは、正しく配置されたクイーンの数（k）を意味します。 nの特定の値に対するすべての解の数は、mで示されます。 サイズnx nの「チェス盤」の類似物として、サイズnx nの「決定マトリックス」を検討します。

開始する

研究を行うために、nの任意の値のすべての解を検索するアルゴリズムが開発されました。 標準の再帰やネストされたループの通常のシステムは使用しませんでした。 nの値が大きい場合、このようなアプローチは非常に問題になります。 アルゴリズムは相互作用する一連のイベントに基づいて構築されており、それぞれのイベントでは特定のアクションシステムが相互接続されて実行されています。 これにより、問題の解決策の分岐内の次のノードを選択するときに状態空間を変更するメカニズムを実装することができます（前方追跡）、または1つ以上のステップを戻すときに（以前のアクションのトレースをクリアします）（後方追跡）。 アルゴリズムのメモリサイズまたはプロセッサ速度に特別な要件はありません。

このアルゴリズムに基づいて、解行列n =（7、...、16）のさまざまな値に対するすべての逐次解（短いものと完全なものの両方）が見つかりました。 完全なソリューションのリストのサイズは、名前付きシーケンス整数シーケンスのオンライン百科事典 （シーケンスA000170 [9]）であり、多くの出版物で示されているため、私たちが検討したnの値のすべてのソリューションのリスト（ショート+フル）のサイズをリストすることは興味深いようです： 7 （194）、 8 （736）、 9 （2 936）、 10 （12 774）、 11 （61 076）、 12 （314 730）、 13 （1 716 652）、 14 （10 030 692）、 15 （ 62 518 772）、 16 （415 515 376）。

さらに、見つかった解決策を使用して、いくつかの問題の文言、それらを解決する方法、および結果の説明を示します。

1.ソリューションが検索される状態空間

サイズnの決定の行列の特定の行のクイーンの位置に関するさまざまなオプションの列挙は、状態空間の形成につながります。 行列の1つまたは別のセルでのクイーンの配置に禁止がない場合、状態空間のサイズはn ^nになります。 各行と各列の複数のクイーンの位置を禁止するルールのみを考慮すると、サイズがnに等しい状態空間のサブセットを取得します！ 状態空間のこのサブセットは、ルークによるnの分布の問題に対応します。 これに加えて、クイーンが位置するセルを通過する左右の対角線上の複数のクイーンの位置を禁止するルールも考慮に入れると、サイズがnより小さい検索スペースが得られます。 -この部分空間のみがすべて可能な解決策であるという事実に基づく、生産的な検索空間。 生産的な検索スペースで完了したブランチは、特定の数のクイーンが正しく配置されたソリューションです。 基本的に、これらは短い解決策であり、完全な解決策はわずかな残りの部分のみです。

図1は、3つの指標の自然対数のグラフを示しています。a）階乗値（n！）決定行列のサイズ。 b）すべての決定の数（短いものと完全なものの両方）; c）ソリューションマトリックスのサイズの値（n）に応じた完全なソリューションの数。 予想どおり、すべての曲線はnの増加とともに指数関数的な成長を示します。 すべてのソリューションの数と完全なソリューションの数の成長率は異なりますが、n値のサンプルサイズが小さいため、グラフ上ではそれほど顕著ではありません。 たとえば、n = 13の場合、これらのインジケーターの対数の差は3.148で、n = 16の場合、この差は0.190増加して3.338です。 明らかに、nの値をさらに大きくすると、この不一致はさらに大きくなります。

図1状態空間のサイズの対数の値nへの依存性

2.すべての決定の一般リストに含まれる完全な決定の割合はどのように変わりますか？

明らかに、完全なソリューションの数の成長率がすべてのソリューションの数の成長率に遅れている場合、すべてのソリューションの一般リストで完全なソリューションを見つける確率は、nの増加とともに減少します。 図2は、nの値に関するすべてのソリューションの一般的なリストにおける完全なソリューションの割合のグラフを示しています。 ソリューションマトリックスのサイズが大きくなると、一般リスト内のすべての完全なソリューションのシェアが減少することがわかります。 初期値n =（7、...、14）では、この値は値0.2062から0.0364に5.66倍減少し、その後、この値の漸進的漸近的減少が続きます。 ここで、2つのステートメントの間で正式な矛盾が生じます。一方で、完全な解の数はnの増加とともに指数関数的に増加し、他方では、すべての解の連続リストにおける完全な解の確率は絶えず減少しています。 この見かけ上のパラドックスは非常に簡単に説明されています。生産的なスペースのサイズとすべてのソリューションのリストの関連サイズは、完全なソリューションの数よりもnの増加とともに速く成長します。 これは、干し草の山で針を見つけようとするのに似ています-「nが増加する」干し草の量は、そこで失われる針の数よりも速く成長します。 したがって、n = 27の場合、完全な解の数が約2.346 * 10 ¹⁷である場合、すべての解の数の対応する値は、おそらく3〜4桁の大きさであると仮定できます。

図2 nの増加に伴うすべてのソリューションの一般リストでの完全なソリューションの割合の減少

3.すべてのソリューションのリストにあるさまざまな長さのソリューションの頻度はどのくらいですか？

前述したように、生産的な検索スペースで完成したすべてのブランチは、異なる数のクイーンが正しく配置されたソリューションです。
すべてのソリューションの一般的なリストにさまざまな長さのソリューションがある頻度で、私たちは興味を持っています。

値n =（7、...、12）の表1は、異なる長さの解の相対周波数の対応する値を示しています。 このデータの対応する視覚的表現を図3に示します。

表の分析により、次の結論を導き出すことができます。

a）サイズnの各行列に対して、最大頻度（太字で強調表示）を持つ解の特定の長さがあります。

表1.サイズn =（7、...、12）のマトリックスの異なる長さ（k）の解の相対頻度（％）

n \ k	4	5	6	7	8	9	10	11	12
7	10.31	31.23	27.84	20.62
8	2.45	20.38	34.78	29.89	12.50
9	0.34	5.79	21.73	35.83	34.32	11.99
10	0.05	1.35	8.41	25.62	32.94	25.96	5.67
11		0.15	2.12	11.80	26.71	34.47	20.36	4.39
12		0.01	0.29	3.28	13.56	29.88	31.29	17.18	4.51

b）nが増加すると、長さが異なる解の数が増加します。 したがって、すべての決定の相対的な頻度は減少します。

図3解行列のサイズに応じたさまざまな長さの解の頻度、n = 7、...、16

c）サイズnの各行列に対して、解の長さの特定の最小サイズがあり、それ以下では短い解は発生しません。 nを大きくすると、このしきい値の値が大きくなります。 たとえば、n = 8の場合、しきい値はそれぞれ4、n = 16の場合、しきい値は7です。

4.すべてのソリューションの連続したリストにおける完全なソリューションの相対的な配置は何ですか？

「n個の女王の分布に関する」問題の声明には、すべての解決策の一般的なリストにおける完全な決定のシーケンスについての仮定を行う理由を与える理由はありません。 一般リストの完全なソリューションが均等に、ランダムに配布されるのか、それとも何らかの特異性があるのか​​どうかに興味がありました。 調べるために、すべてのソリューションの連続リスト内の最も近い完全なソリューション間の距離について分析が行われました。 図4からわかるように、n = 12の場合、対応する周波数の変化のグラフが表示されます。

図4すべての完全な解の連続リスト内の最も近い完全な解の間の距離に対する頻度（n = 12）

最大の頻度で、すべてのソリューションの共通の順次リストですぐに互いに続く完全なソリューションがあります。 これらは、最後の行の自由位置の関係により、2つ以上の連続した完全なソリューションを形成できる場合の、検索ブランチの形成の場合です。 さらに、最大周波数は、間にある完全なソリューションです：1つの短いソリューション、2つの短いソリューションなど。

5.すべてのソリューションの一般リストに完全なソリューションの配置にパターンはありますか？

この質問に答えるために、値n =（7、...、16）のすべてのソリューションの連続リストを分析しました。 結果を明確に示すために、図5では、値n = 8について、736個すべてのソリューションのリスト内の各ソリューションの長さが順番に示されているグラフが表示されています。 ここでは、92個のソリューションのみが完了しており、それらは赤で強調表示され、残りの644個のソリューションは短く、青で強調表示されています。 完全なソリューションは、すべてのソリューションのリストで均等に配布されていないことがわかります。 完全なソリューションがより一般的である領域があり、完全なソリューションがまれであるか、まったくない場所があります。

図5 8 x 8マトリックス（赤-完全なソリューション、青-短いソリューション）の場合、すべてのソリューションの順次リスト内の各ソリューションの長さ。 すべてのソリューションの総数は736です

ただし、ここでは何か他のことが重要です。 青赤バーコードに似た図を注意深く見ると、1つの非常に重要な機能に気付くでしょう。すべての赤線は、ソリューションのリストの中央を通る条件付きの垂直線に関して対称です。 実際、チェックが示すように、一般リストの先頭からi番目のステップで完全なソリューションがある場合、それに応じて、ステップm-i + 1で完全なソリューションが確実に見つかります。 たとえば、n = 8の場合、すべてのソリューションの順次検索で最初の完全なソリューションがステップ43に表示される場合、それに応じて、リストの最後の完全なソリューションがステップ736–43 + 1 = 694で見つかります。 10x10行列の17番目の解がステップ368のリストに表示される場合、それと対称な完全な解がステップ12774-17 + 1 = 12407のすべての解のリストに表示されます。 このルールは、任意のサイズの決定マトリックスに当てはまります。 したがって、ルールを定式化できます。 nの任意の値について、すべてのソリューションのシーケンシャルリストで、リストの先頭からi番目の位置でソリューションが完了している場合、位置m-i + 1にあるリストの末尾からの対称ソリューションも完了します（ソリューションの対称性の規則）。 ここで、上記のmは、すべての解の数を意味します。 この規則の結果は、nの値に対して、完全な解の数が常に偶数になるという事実です。 （これまでに見つかった完全なソリューションのリストのサイズはすべて偶数です）。

任意の2つの対称解のインデックスを比較すると、基本的に重要な特徴を見つけることができます。対称解のペアは相補的です。 対称解のクイーンのインデックスの対応する値の合計はn + 1になります。 たとえば、すべてのソリューションのリストのn = 10の17番目のソリューションは、リストの先頭から368番目のステップにあり、このステップのクイーン位置インデックスは（1、5、7、10、4、2、9、3、6、 8）。

対応する対称解はステップ12407にあり、クイーン位置インデックス（10、6、4、1、7、9、2、8、5、3）を持っています。 各ペアのインデックスの対応する値を追加すると、（11、11、...、11）が得られます。 この規則は、完全な対称解と短い対称解の両方のnの値に対して有効です。 これにより、2番目のルールを定式化できます。 任意のサイズnのソリューションマトリックスの場合、すべてのソリューションの連続リストに対称的に配置されたソリューションのペア（短いものと完全なものの両方）は相補的です-対応する行の位置インデックスの合計は一定であり、n + 1（ソリューションの相補性の規則）に等しくなります。 Q（i）とQ1（i）が相補解のインデックスの配列である場合、ルール

<b>`Q ( i ) + Q1 ( i ) = n + 1, i = (1, n) `</b> 

この規則は、 i番目のステップで完全な解が得られた場合、ステップm-i +1の対称完全解が既知になることを意味します。 したがって、すべての完全なソリューションを検索する場合、すべての完全なソリューションの前半のみを検索するだけで十分です。 完全なソリューションのリストの後半は、補完のルールに基づいて、すでに取得されているソリューションから決定できます。 完全な解のリストの半分が達成される基準は、前の完全な解Q（i-1）と後続のQ（i）の間の相補性ルールの実現です。 すなわち、2つの連続した解の対応するインデックスの各ペアの合計がn + 1に等しいことが必要です。 すべての完全なソリューションのリストからの完全なソリューションは一意であるため、リストを半分に分割する境界の両側にある連続した完全なソリューションのみが補完的となります。

これらの2つのルールにより、将来、nの次の値のすべての完全なソリューションを検索するときに、計算量が削減され、計算時間が半分になります。

6.最初の完全なソリューションを見つけるための一連のステップの視覚化

ソリューション検索のブランチを形成するときに、ステップを前進させる（フォワードトラッキング）およびリターンする（バックトラッキング）プロセスはどのように行われますか？ この質問に答えるために、10 x 10の行列について、最初の完全な解が現れるまでの行間の最初の194遷移のシーケンスを決定しました。 対応するグラフを図6に示します。青い線は前進を示し、赤い線は戻りを示します。 これらの194のステップの間に、35の短いソリューションが作成されました。 図は、ほとんどの遷移（84.5％）が行（5、6、7、8）の間で発生することを示しています。 これは、「目標」に向かう途中の一種の「ボトルネック」です。 図からわかるように、4行目に切り替えるのは7件、3行目に切り替えるのは1件のみです。 9行目に切り替える13のケースもあります。 10行目のこれらの検索ブランチには空の位置がなかったため、10行目に3回移動しようとしても失敗しました。 この例は、shortのすべてのブランチを示しています

図6最初の194の検索ステップ（n = 10）のバックトラッキング（赤）およびフォワードトラッキング（青）イベントの視覚化

ソリューション、最初の完全なソリューションまで。 そのような問題を解決するためのアルゴリズムは、短い解決につながるすべてのブランチ（または一部）を排除するメカニズムが含まれている場合に効果的です。

7.最初の完全なソリューションは、いくつの短い決定を経て現れますか？

完全なソリューションがすべてのソリューションのリストの異なる部分で異なって表示されることを考えると、すべてのソリューションを順番に検索する場合、最初の完全なソリューションが表示される短いソリューションの数を見つけることが重要と思われます。 この目的のために、値n =（7、...、35）について、最初の完全な解が現れるまで、すべての短い解が連続的に計算されました。 ステップ番号の自然対数であるnへの依存関係のグラフを示す図7からわかるように、最初の完全な解が現れたとき、nの偶数の値に対して、最初の完全な解はnの最も近い奇数の値よりはるかに遅く現れます。 たとえば、n = 21の奇数値の場合、最初の完全なソリューションはステップ3138に表示され、n = 22の次の偶数値の場合、最初の完全なソリューションはステップ628169に表示されます。 したがって、次の奇数n = 23の場合、最初の完全な解がステップ9155に表示されます。

図7 nのさまざまな値に対する最初の完全な解までの短い解の数

偶数n = 22の反復ステップ数は、最も近い奇数値のそれぞれ200.2倍と68.6倍です。 これは、n = 34の​​時間をカウントする場合に特に顕著です。 ここで、最初の完全なソリューションは826 337 184番目のステップに表示され、最も近い奇数（33、35）には、それぞれ50 704 900番目および84 888 759番目のステップに表示されます。 また、nの増加に伴い、最初の完全なソリューションが出現する前の短いソリューションの数の単調な増加の違反についても言及する必要があります。 nの偶数値の場合、これはn = 19で発生し、奇数値の場合、n = 24およびn = 26で発生します。

8.すべての完全なソリューションのリストの各行のセル周波数は同じですか？

チェス盤の類似物として機能するnxnサイズの決定マトリックスは、すべてのイベントが発生するシーンのようなものです。 このシーンで形成される完全なソリューションは、異なる行のセルのインデックスで構成されます。 そのような各セルは、ソリューション検索ブランチのノードです。 興味のある質問は次のとおりです。すべての完全なソリューションのリストをコンパイルするときに、各セルの負荷は各セルで同じですか？ 明らかに、周波数値が高いほど、完全なソリューションのリストを形成するこのセルのアクティビティが高くなります。 これを確立するために、すべての完全なソリューションのリストに基づいて、各行について、さまざまなインデックスの相対頻度を決定します。 まず、サイズn = 8の解行列について分析します。 完全なソリューションの配列の各行を順番に調べて、さまざまなインデックス値の頻度を決定します。 表2は、8つの行のそれぞれの異なるセルの絶対活動頻度の対応する値を示しています。 8

表2.すべての完全なソリューションのリストの分析に基づいた、8x8決定マトリックスの8行のそれぞれにおけるセルアクティビティの絶対頻度

行\列	1	2	3	4	5	6	7	8
1	4	8	16	18	18	16	8	4
2	8	16	14	8	8	14	16	8
3	16	14	4	12	12	4	14	16
4	18	8	12	8	8	12	8	18
5	18	8	12	8	8	12	8	18
6	16	14	4	12	12	4	14	16
7	8	16	14	8	8	14	16	8
8	4	8	16	18	18	16	8	4

4つのグラフのグループが表示されます。各グラフは、1行内の相対頻度の変化を特徴付けます。 得られたすべてのデータの分析から引き出すことができる基本的に重要な結論の1つは次のとおりです。

• 任意のサイズnの決定行列の場合、 i番目の行のセルのアクティビティは、セルn-i + 1のアクティビティと一致します。 最初の行のセルのアクティビティは常に最後の行のセルのアクティビティと常に一致し、2番目の行のセルのアクティビティは最後から2番目の行のセルのアクティビティと一致します。
  
  nが奇数の場合、解行列の中央の行のみに対称ペアがありません;他のすべてのセルでは、上記のルールが有効です
• これを「ソリューションマトリックスの異なる行のセルのアクティビティの水平対称性のプロパティ」と呼びます。 この理由から、行（1、8）、（2.7）、（3.6）、および（4.5）のセルアクティビティの対応するグラフは完全に同一であるため、サイズn = 8の決定行列に対して4つのグラフのみを提示しました。

また、周波数値は、マトリックスを2つの等しい部分に分割する（nの偶数値の場合）、または中央値列を通過する（nの奇数値の場合）垂直軸に関して対称であることに注意してください。 これを「解行列の異なる行のセルの活動の垂直対称性」と呼びます。

さらに、表2の分析からわかるように、解行列の周波数は、左右の主対角線に関して対称です。

図8完全なソリューションのリストを作成するときの対応する行のセルアクティビティ、n = 8

問題の記述に制限的なルールが存在し、非決定性の関連プロパティが異なる行のノード間の一種の調和した関係を「形成」すると思います。 これらのルールに適合する検索のブランチ-完全なソリューションの形成につながります。 検索の残りのブランチは、あるステップでこれらのルールに違反し、その結果、短い決定の形で「旅を完了」します。 ここで、決定マトリックスのセルは投影影響グループ内でローカルな関係のみを持ち、それらの間の調整されたアクションに関する規定されたルールはないことに注意する必要があります。 セルの集合的な活動は、制限ルールの影響の結果にすぎません。 したがって、かなり興味深い質問が残っています。非決定性要因などの制限的なルールが決定マトリックスのセルにどのように影響し、最終的に「調和のとれた」セル活動マトリックスの形成につながりますか？水平軸と垂直軸、および左に関して対称です右の対角線。 これはこの問題だけの特徴的な特性ですか、それとも他の非決定的な問題にも当てはまりますか？

9.どの行番号から前方追跡-後方追跡アルゴリズムがオンになりますか？

クイーンの場所の決定マトリックスで連続行選択アルゴリズムの操作に従うと、「StopRow」と呼ばれる特定の行から開始して、進行のプロセスが「中断」していることがわかります。 検索ブランチでは、これは無料の可用性に問題がある最初の行です

図 9-1 StopRowインデックスとnの比率の決定マトリックスのサイズへの依存性（パート1）

女王の位置の位置。 この行から、以前に実行されたアクションのトレースをクリアして戻るために、バックトラッキングアルゴリズムがオンになります。 これは、最初の短いソリューションが表示される行です。

図9-2決定行列のサイズに対するStopRowインデックスとnの比率の依存性（パート2）

困難が前進し始める「StopRow」行のインデックスは、決定マトリックスのサイズnに依存します。 StopIndで示されるこのインデックスと解行列nのサイズの比率を考慮すると、初期値n =（7、...、99）の計算結果が示されている図9-1からわかるように、この比率は多かれ少なかれ変動します側と減少する傾向があります。 n =（100、...、300）が増加すると、この比率は0.619-0.642の間で変動し（図9-2）、さらにnが増加すると、次の結果が得られます（nの値は順番に示され、括弧内の値はStopIndおよびStopInd / n比： 1000 （619、0.6190）、 2000 （1239、0.6195）、 3000 （1856、0.6187）、 4000 （2473、0.6182）、 5000 （3091、0.6182）。驚くべきことに、 停止すると主張することができます-lineは、黄金比ルールに従って決定行列を分割します。つまり、 StopInd / n比は、 nの増加とともにゼロになる傾向がある（n-StopInd）/ StopIndとは異なります。たとえば、n = 5000の場合、関係の差 3091/5000および1909/3091は0.006であり、これら2つの関係の平均の0.1％未満です。

2つの図に示されているグラフ 9-（1,2）は、ランダムではない形式の変動性を持ち、これは「音楽的譜表」の録音に似ています。 不規則な周期性で、ジャンプを繰り返し、段階的に下降するのを見ることができます。 明らかに、この種の曲線の振る舞いには何らかの理由があり、おそらくこれは研究にとって興味深いでしょう。 このため、より詳細な視覚化を目的として、グラフは2つの図で表示されました。

「n-queensの分布に関する」問題の解決結果に基づいて定式化できる質問の一部のみを検討しました。 得られた結果が、非決定的なプロセスの形成と状態空間の変化のメカニズムを理解のためにより透明にすることを願っています。 おそらくこれは、新しいタスクを策定し、前進するための支点として役立つでしょう。

おわりに

• 出版物を見て結論に達した場合、当然のことながら疑問が生じます：「記事タイトルの10億の女王問題解決策とはどういう意味ですか？」 Habr向けの出版物の準備中に、たとえば、ダイヤモンドを採掘する鉱山を持っている人は、少なくとも1つのダイヤモンドを友人や親toに寄付すべきだと考えました。そうでなければ不公平になるでしょう。 したがって、参加者、主催者、訪問者など、habrコミュニティのすべてのメンバーに贈り物を贈りたいと思います。 名前が示すように、これは10億のサイズのチェス盤で10億の女王を配布する問題の解決策です。
  
  もちろん、これは多面的なダイヤモンドではありませんが、知的芸術の真の愛好家にとっては、「そこにある種のダイヤモンド」よりも価値があります。 さらに、ダイヤモンドは世界中でさまざまであり、この解決策はこれまでのところ1つのコピーにしかありません。 そして、私たちのByte-God（*）は、私がこれを心からやっていると考えています。
  結果として得られるソリューションは、10億個の1次元配列であり、MatLab .mat形式で提示され、次の場所から入手できます。
  -この配列の最初の要素は、1行目のクイーンの位置、2番目の要素-2行目の位置などを特徴づけます。 これは、nBillionの可能なソリューションの1つに過ぎません。 また、nBillionの値は非常に大きいため、無限大の近縁と見なすことができます。
  
• この解決策は、仮想の知的価値のカテゴリーに起因すると考えられます。 「これは何かがあるものだ」と言えます。 彼らは本当に「触れる」ことはできないので、それは感覚のレベルでのみ意識で知覚されます。 実際、そこには驚くべき秩序と明示的および暗黙的な調和があります。 これは、コミュニティのすべてのメンバーに宛てられた純粋に象徴的な贈り物です（文字通りおよび比fig的に）。 「 あなたは他のみんなとは違う 」と思う。
  
  （誰かが「ギフトを家に持ち帰る」ことを願っています。ファイルが十分に大きい-3.7 Gb。これはクリーンで検証済みのデータです。Googleドライブは警告を表示します。
  
• この決定を下す前に、私はそのような贈り物の個々に集合的な性質について考えました。 オリジナルを提示し、残りをコピーで提示することは可能ですか？ しかし、解決策は簡単でした。 この場合、「オリジナル」と「コピー」という通常の「毎日」の概念は意味を失います。 コピーするのではなく、別のオリジナルを作成します。 そして、「オリジナル」はすべて同じであり、等しく同等です。
  
• 親relativeの会社では、そのような「知的製品」をプレゼントとして受け取ったのはおそらくあなただけだと思います。 義理の母にそのような贈り物について話すのは楽しいでしょう：「50,000 km×50,000 kmのチェス盤を持った母親を想像してください。10億の女王が近くにいるのを見ないように分布しています...」 彼はそのような奇妙な贈り物を与えられているので、おそらくこの後、義理の息子がより高く評価されるでしょう。
  

habrコミュニティのすべてのメンバーの健康、成功、幸福を祈っています。 新年が私たち全員に幸運をもたらすように。

（*）-オブジェクトの名前を参照しているため、その説明も提供する必要があります。
バイト神とは、0と1からなる多次元の実体を意味し、あらゆる意味で合理的であり、あらゆる方向に無限です。 このスペース内のゼロと1のシーケンスは、特定の知識を表します。

参照資料

[4] Max Bezzel、「8クイーンズ問題の提案」、Berliner Schachzeitung、Volume
3（1848）、363ページ。（著者名\ Schachfreund "で提出。）

[5]フランツ・ナウク、ブリーフウェッヒセルン、アレン・ファー・アレ」、Illustrirte Zeitung、Volume
377 Number 15（1850）、182ページ。

[6]ベルジョーダン。 スティーブンスブレット（2009）。 「nクイーンの既知の結果と研究領域の調査。」 離散数学。 309（1）：1–31

[7]ゲント、イアンP。; ジェファーソン、クリストファー。 ナイチンゲール、ピーター（2017年8月）。 「nクイーンの完了の複雑さ」。 Journal of Artificial Intelligence Research。 AAAI Press。 59：815–848

[8] W. Kosters and all、n-Queens-342のリファレンス（2018年11月20日）

[9] NJAスローン、整数シーケンスのオンライン百科事典は、電子的に公開されています。 2016年