8つのクイーンズの問題に対するJavaScriptソリューションに関して、私は常にアルゴリズムを学ぶ必要があると感じています。いつか使用するかどうかを調べるのは恥ずかしいことです。
背景
8人の女王の質問はチェスに基づいた質問です。女王が他の女王を直接食べることができないように、8×8のチェスボードに8人の女王をどのように置くことができますか？これを達成するために、どちらの女王も同じ水平、垂直、または斜めの線に存在することはできません
8つの女王の問題は、n Queenの配置のより一般的な問題に一般化できます。現時点では、チェスボードのサイズはn×nになり、クイーンの数もnになります。 n = 1またはn≥4の場合にのみ、問題の解決策があります
ブラインド列挙アルゴリズム
N倍ループを介して、制約を満たすソリューションを列挙し（8倍のループコードがたくさんあり、4倍ループがここに実行されます）、4人の女王のすべての可能な位置を見つけ、ボード全体でこれらの4人の女王が直接食べるかどうかを判断します。プログラムのアイデアは比較的簡単です。
関数check1（arr、n）{for（var i = 0; i <n; i ++）{for（var j = i+1; j <n; j ++）{if（（arr [i] == arr [j]）|| math.abs（arr [j]）== j -i）{return false; }}} return true;} function Queen1（）{var arr = []; for（arr [0] = 1; arr [0] <= 4; arr [0] ++）{for（arr [1] = 1; arr [1] <= 4; arr [1] ++）{for（arr [2] = 1; arr [2] <= 4; arr [2] ++）{for（arr [3] = 1; arr [3] <= 4; arr [3] <= 4; arr [3] <= 4; arr [3]; 続く; } else {console.log（arr）; }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}ティー。 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}ティー。 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}ティー。 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}。結果に関しては、4*4チェスボードでは、4人の女王が連続することはできません。 arr [0] to arr [3]はそれぞれ4人の女王に対応しています。配列と添え字の添え字に対応する値は、ボード内のクイーンの位置です。
バックトラッキング方法
「行けない場合は、振り向くだけです。」適切なノードで一致するかどうかを判断します。一致しない場合は、このブランチを探索しなくなります。
function check2（arr、n）{for（var i = 0; i <= n -1; i ++）{if（（math.abs（arr [i] - arr [n]）== n -i）||（arr [i] == arr [n]）{return false; }} return true;} function queen2（）{var arr = []; for（arr [0] = 1; arr [0] <= 4; arr [0] ++）{for（arr [1] = 1; arr [1] <= 4; arr [1] ++）{if（！check2（arr、1））継続; //（arr [2] = 1; arr [2] <= 4; arr [2] ++）{if（！check2（arr、2））継続; // 3人のクイーン間の競合を（arr [3] = 1; arr [3] <= 4; arr [3] ++）{if（！check2（arr、3））{continue; } else {console.log（arr）; }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}ティー。 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}ティー。 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}ティー。 }}}}}}}}}}}}}}}}非回復的なバックトラッキング
アルゴリズムフレームワーク：
（k> 0.は、目標に達する方法があります。検索スペースで "）{// acrupedのリソースをマークします// k = k + 1; } else {//占有状態空間をクリーンアップ// k = k -1; }}}特定のコードは次のとおりです。最外層には2つの部分が含まれています。 1つは現在の女王の可能な値の横断であり、もう1つは次のレイヤーを入力するか、前のレイヤーをバックトラックするかどうかを決定することです。
function backdate（n）{var arr = []; var k = 1; // nth Queen arr [0] = 1; while（k> 0）{arr [k-1] = arr [k-1] + 1; while（（arr [k-1] <= n）&&（！check2（arr、k-1）））{arr [k-1] = arr [k-1] + 1; } //この女王は制約を満たし、次の判断を下します（arr [k-1] <= n）{if（k == n）{// nth Queen Console.log（arr）; } else {k = k + 1; //次のクイーンarr [k-1] = 0; }} else {k = k -1; //バックトラック、最後の女王}}} backdate（4）; // [2、4、1、3] // [3、1、4、2]再帰的バックトラッキング方法
再帰的な呼び出しは、コードの量を大幅に減らし、プログラムの読みやすさを向上させます。
var arr = []、n = 4; function backtrack（k）{if（k> n）{console.log（arr）; } else {for（var i = 1; i <= n; i ++）{arr [k-1] = i; if（check2（arr、k-1））{backtrack（k + 1）; }}}}} backtrack（1）; // [2、4、1、3] // [3、1、4、2]ゴージャスなアンブ
Ambとは何ですか？データリストを提供します。これにより、制約の成功状況を満たす方法を返すことができます。成功することなく、失敗します。もちろん、すべての成功状況を返すことができます。著者は、このAMBアルゴリズムをここで推奨するために、上記の非常に多くのポイントを書いています。簡単なバックトラッキングシナリオの処理に適しています。とても面白いです。それがどのように機能するか見てみましょう。
まず、小さな問題に対処し、隣接する文字列を見つけましょう。文字列配列のセットをいくつか取得すると、各配列が文字列を取り出します。前の文字列の最後の文字は、次の文字列の最初の文字と同じです。条件が満たされている場合、新しく取得された文字列が出力されます。
ambrun（function（amb、fail）{//制約メソッド関数リンク（s1、s2）{return s1.slice（-1）== s2.slice（0、1）;} // inject data list var w1 = amb（["the"、 "that"、 "a"]）; Amb（「warked」、「grows」）;ゆっくりと成長します "}）;とてもシンプルに見えますか？しかし、使用の前提は、あなたがパフォーマンスを気にしないこと、それは本当に時間の無駄だということです！
以下は、JavaScriptの実装です。興味がある場合は、バックトラッキングをどのように抽出するかを調べることができます。
function ambrun（func）{var choices = []; varインデックス; function amb（values）{if（values.length == 0）{fail（）; } if（index == choices.length）{choices.push（{i：0、count：values.length}）; } var choice = choices [index ++]; return値[Choice.i]; } function fail（）{shrow fail; } while（true）{try {index = 0; return func（amb、fail）; } catch（e）{if（e！= fail）{shrow e; } var Choice; while（（choice = choices.pop（））&& ++ choice.i == count.count）{} if（choice == undefined）{return undefined; } choices.push（choice）; }}}AMBを使用して実装された8つのクイーンズ問題の特定のコード
ambrun（function（amb、fail）{var n = 4; var arr = []; varターン= []; var a = arr [i]、b = arr [j];8つの女王問題に対するJavaScriptソリューション
これは、8つの女王問題に対するJavaScriptソリューションです。プログラム全体はループには使用せず、再帰を通じて実装されます。アレイオブジェクトのマップ、削減、フィルター、連結、スライスメソッドを完全に利用します。
'Strict'; var Queens = function（boderersize）{//再帰を使用して、startからend = function（start、end）{if（start> end）{return []; } return interval（start、end -1）.concat（end）; }; //組み合わせが有効かどうかを確認しますvar isvalid = function（queencol）{// 2つの位置の間に競合があるかどうかを確認しますvar issafe = function（pointa、pointb）{var slope =（pointa.row -pointb.row） /（pointa.col -pointb.col）; if（（0 === slope）||（1 === slope）||（-1 === slope））{return false; } trueを返します。 }; var len = queencol.length; var pointtocompare = {row：queencol [len -1]、col：len}; //最初に最後の列を除いて配列をスライスし、次に、各列のポイントとテストするポイントの間に競合があるかどうかをテストし、最後にテスト結果をマージします。 return queencol .slice（0、len -1）.map（function（row、index）{return issafe（{row：row、col：index + 1}、pointtocompare）;}）.reduce（function（a、b）{return a && b;}）; }; //ルールに準拠する組み合わせを再帰的に生成するvar queencols = function（size）{if（1 === size）{return interval（1、bowerersize）.map（function（i）{return [i];}）; } //最初にルールに準拠したすべての以前の列のセットを展開し、次に次元低減を削減し、最後にiSvalidを使用して、ルールを返すルールに準拠する組み合わせをフィルタリングします。 b）{return a.concat（b）; }; // Queens関数エントリリターンクイーンコール（Boderersize）;}; console.log（Queens（8））; //出力結果：// [[1、5、8、6、3、7、2、4]、// [1、6、8、3、7、4、2、5]、// 6、2、7、5]]PS：拡張されたnクイーンの問題
チェスプレーヤーのマックスベッツェルが1848年に8人のクイーンズパズルを尋ねたとき、彼はおそらく100年以上後に、この問題がプログラミング学習において最も重要な強制コースの1つになったとは思っていなかったでしょう。 8人の女王の問題は非常にシンプルに聞こえます。8人の女王をチェスボードに置いて、8人の女王が互いに攻撃しないようにします（チェスボードは8×8の正方形のアレイであり、女王は8方向のいずれかを水平および垂直方向に実行できます）。この問題には92の解決策がありますが、素手で1つの解決策を見つけるのは簡単ではありません。次の図は解決策の1つです。
8人の女王の問題には多くのバリエーションがありますが、それがどんなに難しいとしても、それは次のバリアントよりもハンサムではありません。すべての行と無限のチェスボードのすべての列をすべての列に配置する計画を設計してください。具体的には、このボードの左下隅が原点にあり、左から左から右に無限の列があると仮定すると、すべてのポジティブな整数a1、a2、a3、...列a1の最初の列に最初の女王を配置すると、列a2の2番目の女王などの配置を見つける必要があります。
これは非常にシンプルで賢い構造です。まず、5人の女王の問題に答えます。そして非常に重要なことは、女王の一人が左下隅のグリッドを占有していることです。
次に、5人の女王の解決策を25人の女王に拡張し、5人の女王自体のレイアウトに基づいて拡張します。
その結果、同じグループの5人の女王は明らかに互いに攻撃することはありません。また、異なるグループの女王は互いに攻撃しません。これは、要件を満たす25のクイーンソリューションです。拡張後、以前に記入されたセクションが変更されていないことに注意してください。
次に何をすべきですか？そうです、私たちは25の女王のブロックを5つのピースにコピーし、5人の女王のレイアウトに従って再び配置し、125人の女王に拡大しました！
このような満たされた部分に基づいて常に外側に拡大することにより、無限の女王問題の解を生成できます。