Clever Geek Handbook

女王問題でそこに発見されたものを把握します

数ヶ月前、チェス盤に女王を置くという古典的な問題を分析した興味深い記事が登場しました（詳細と歴史を参照）。 この問題は非常によく知られており、すべてが顕微鏡下ですでに検査されているため、本当に新しいものが登場したのは驚くべきことでした。







画像

さらに6つ入れられますか？ そして、すべてのソリューションを見つけますか？

（記事の写真）







さらに、残念なことに、これらの変換のチェーンからいくつかの完全に理解できない話がありました。









ロシア語で5つのランダムに開かれたリンクによって、状況がさらに明確になったことに注目してください。







私は考えていました-誰かがこの奇妙な連鎖を破り、出来事の本質を通常の言語で述べるべきです。







議論されるもの：









このタスクは、1848年にチェスの作曲家マックスベゼルによって発明されました。タスクの本質は、互いに攻撃しないように、8つのクイーンをチェス盤に置くことです。 それ以来、ガウスなどの多くの数学者がタスクに取り組んでおり、アルゴリズムやダイクストラなどのプログラマーは、解決策を見つけて数えるための多くのアプローチを考え出しています。







問題では、クイーン8人ではなく、それぞれNとボード、通常のチェスではなくNxNについて説明します。









3種類のクイーンズ問題



最も人気のある女王の処方には3つあります。









Nクイーンズ



タスクは非常に簡単に定式化されます。







指定 ：空のNxNボード、たとえば8x8









（原則として、単にNを示すだけで十分であることは明らかですが、より明確に）







見つける ：クイーンの最大可能数の配置











すなわち 入り口での数字はボードのサイズ、出口でのクイーンの位置（1つのソリューション）です。



決定の数を数える



タスクも非常に簡単です。







指定：空のボードサイズN

見つける： Hボード上のNクイーンの可能な配置の数







たとえば、ボードのサイズはN = 1で、可能な配置の数はH = 1です。

N = 8 => H = 92。









Nクイーンズの補足



ここで、文言はもう少し陰湿です。







与えられた：ボードのサイズNとMの位置は既に確立された女王

検索：残りのN-Mクイーンの位置







視覚的には、すべてがCPDVのようなものです。









（元の記事からも写真）









タスクのバリエーション



一般的に、問題にはさらに多くのバリエーションがあります。たとえば、白と黒の女王の配置を参照してください。

http://www.csplib.org/Problems/prob110

ただし、ここではメインのクラシックバージョンのみを検討します。







このバリエーションでは、ソリューションは大きく異なります（白は白に勝るものではなく、黒は黒です：混乱の場合-こちらのコメントを参照 ）。









（ここではクイーンの最大数、そして十字架の代わりに白を、黒点の代わりに置くことができます-同時に両方ではありません; 記事から取られました）









モデルとタスクの複雑さ



実際に議論する時が来ました。これをどのように決定し、どのくらい迅速にそれを行うことができますか？









古典的な問題の線形探索



最も興味深い点は、専門家でさえ混乱する場合があり、Nクイーンを解決するには組み合わせ検索が必要であり、問​​題の複雑さはPよりも高いと考えることです。PとNPについては、Habréで書いたことがあります。 SATとこれらすべてのP-NP（パート1）および2番目の P-NPが必要 です 。 ただし、問題はオプションを経由せずに解決されます！ つまり、どのサイズのボードでも、クイーンを次々に配置できます。









配置アルゴリズムは多数あります。たとえば、 この記事やWikiをご覧ください。







したがって、N = 1およびN> 3の場合、常に解決策があり（Algoを参照）、N = 2またはN = 3の場合、

常にそうではありません（ボードから簡単に続きます）。 これは、Nクイーン（解があるかどうかを言う必要がある）の可解性の問題が一定の時間で簡単に解決されることを意味します（まあ、わかりました、構造的に線形時間-配置/チェック）。







私たちが読んだものを再確認する時が来ました。典型的な見出し「Nクイーンの仕事はNP完全な仕事として認識されました」を読みます。









実際の決定の数を数える方法



ここからが楽しみの始まりです。クイーンズアレンジの問題の解決策の数には、「sequence A000170 」という独自の名前が付いています。 良い知らせはここで終わります。 問題の複雑さ：NPおよびP＃よりも高いため、実際には、最適な解決策は、シーケンスデータを辞書にダウンロードし、必要な数を返すことです。 N = 27の場合、並列クラスターでは何週間あるか既に考慮されていました。







解決策 ：ラベルとnを書き、（n）を返します

ナ（n）

1：1

2-0

3-0

4：2

5：10

6：4

午前7時40分

8：92

9：352

10：724

...

21：314666222712

22：2691008701644

23：24233937684440

24：227514171973736

25：2207893435808352

26 22317699616364044

27：234907967154122528







ただし、何らかの厄介な問題があり、解決策を計算する必要がある場合（およびその数は不明であり、誰も以前に数えていません）、プロトタイプの最適なバージョンを以下で説明します。









Nおよびアンサーセットプログラミングの補足



ここからが楽しみです。記事の新しい結果は何ですか？ Nクイーンを補完する問題はNP完全です！ （興味深いことに、ラテン方格補数のNP完全性は 1984年に知られていました。）







これは実際にはどういう意味ですか？ この問題を解決する最も簡単な方法（または突然、バリエーションが必要な場合）は、SATを使用することです。 ただし、次の例えが好きです。







SATはコンビナトリアルNPタスクのアセンブラーであり、Answer Set Programming（ASP）はC ++です（ASPには謎めいたロシアの魂もあります：未熟な人にとっては混乱し、予測できないこともあります;ところで、 現代のASPの基礎となる理論が発明されました1988年にミハイルゲルフォンドとウラジミールリフシッツにより、それぞれテキサス大学とスタンフォード大学に勤務しました）。







簡単に言うと、ASPは、Prolog構文を使用したプログラミングの制約（英語文学の制約）のための宣言型言語です。 つまり、ソリューションが満たさなければならない制約を記録し、システムはすべてをSATオプションに還元し、ソリューションを見つけます。







ソリューションの詳細はここではそれほど重要ではありません。また、回答セットプログラミングは別の投稿に値するものです（これは長い間、私のドラフトにありふれていました）。したがって、概念的なポイントを分析します。 







% domain row(1..n). column(1..n). % alldifferent 1 { queen(X,Y) : column(Y) } 1 :- row(X). 1 { queen(X,Y) : row(X) } 1 :- column(Y). % remove conflicting answers :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2. :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2. :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.


行1 { queen(X,Y) : column(Y) } 1 :- row(X).



-選択ルールと呼ばれ、有効な検索スペースを決定します。







最後の3行は整合性制約と呼ばれ、ソリューションが満たす必要のある制約を決定します。同じ行にクイーンは存在できず、同じ列にクイーンは存在できません（対称性のために省略されます）。同じ対角線の。







実験用のシステムとして、 Clingoをお勧めします 。

そして、初心者にとっては、 チュートリアルを見て、 www.hakank.orgのブログを読む価値があります。







もちろん、最初にASPで記述した場合、最初のモデルは非常に効率的かつ高速に動作しませんが、ほとんどの場合、ブルートフォースリターンよりも高速になります。 ただし、システムの基本原則を理解していれば、ASPは「NP完全タスクの正規表現」になる可能性があります。







ASPモデルで簡単な数値実験を行いましょう。 私はモデルに5人の陰湿な女王を追加し、1から150までのNの解決策の検索を開始しました。これが起こったことです（通常の自宅のラップトップで実行）。











合計で、ASPモデルは、N <= 150の補完問題の解決策を約1分で見つけることができます（通常の場合）。 これは、このシステムが複雑な組み合わせ問題のプロトタイピングモデルに優れていることを示しています。









結論





More articles:


All Articles