فيما يتعلق بحل جافا سكريبت لمشكلة كوينز الثمانية ، أشعر دائمًا أنني بحاجة إلى تعلم الخوارزمية. سيكون من المحرج معرفة ما إذا كنت أستخدمه يومًا ما.
خلفية
سؤال الملكات الثمانية هو سؤال يعتمد على الشطرنج: كيف يمكن وضع ثمانية ملكات على لوحة الشطرنج 8 × 8 بحيث لا يمكن لأي ملكة أن تأكل الملكات الأخرى مباشرة؟ لتحقيق ذلك ، لا يمكن أن تكون الملكة في نفس الخط الأفقي أو الرأسي أو القطري
يمكن تعميم مشكلة Queens الثمانية على المشكلة الأكثر عمومية لوضع ملكة n: في هذا الوقت يصبح حجم لوحة الشطرنج n × n ، ويصبح عدد الملكات أيضًا n. إذا وفقط إذا n = 1 أو n ≥ 4 ، فهناك حل للمشكلة
خوارزمية التعداد الأعمى
من خلال حلقات N-Fold ، يتم تعداد الحلول التي تلبي القيود (هناك العديد من رموز الحلقة ذات ثمانية أضعاف ، يتم تنفيذ حلقات أربع أضعاف هنا) ، والعثور على جميع المواقف الممكنة للملكات الأربع ، ثم الحكم في اللوحة بأكملها ما إذا كانت هذه الملكات الأربعة ستأكل بعضها البعض مباشرة. فكرة البرنامج بسيطة نسبيا.
وظيفة 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 [i] - arr [j]) == j - i) {return false ؛ }}} return true ؛} function Queen1 () {var arr = [] ؛ لـ (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] يكمل؛ } آخر {console.log (arr) ؛ }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}فيما يتعلق بالنتيجة ، في لوحة الشطرنج 4*4 ، لا يمكن أن تكون الملكات الأربعة على التوالي. ARR [0] إلى ARR [3] تتوافق مع الملكات الأربعة على التوالي. القيمة المقابلة لمرتبة الصفيف والمنصية هي موضع الملكة في اللوحة.
طريقة التراجع
"إذا لم تتمكن من الذهاب ، فما عليك سوى الدوران." تحديد ما إذا كان يطابقها في العقدة المناسبة. إذا لم يتطابق ، فلن تستكشف هذا الفرع.
الدالة 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 ؛} وظيفة Queen2 () {var arr = [] ؛ لـ (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)) متابعة ؛ // اذكر الصراع بين ثلاث ملكات لـ (arr [3] = 1 ؛ arr [3] <= 4 ؛ arr [3] ++) {if (! check2 (arr ، 3)) {متابعة ؛ } آخر {console.log (arr) ؛ }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}التراجع غير المتوحش
إطار الخوارزمية:
بينما (k> 0 『هناك طريقة للذهاب』 و 『لم تصل إلى الهدف』) {// k> 0 『هناك طريقة للذهاب إذا (k> n) الفضاء ") {// وضع علامة على المورد المشغل // k = k + 1 ؛ } آخر {// تنظيف مساحة الحالة المحتلة // k = k - 1 ؛ }}}الرمز المحدد كما يلي. الطبقة الخارجية بينما تحتوي على جزأين. أحدهما هو اجتياز القيم المحتملة للملكة الحالية ، والآخر هو قرار ما إذا كان سيتم إدخال الطبقة التالية أو التراجع عن الطبقة السابقة.
وظيفة backdate (n) {var arr = [] ؛ var k = 1 ؛ // Queen arr [0] = 1 ؛ بينما (k> 0) {arr [k-1] = arr [k-1] + 1 ؛ بينما ((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) ؛ } آخر {k = k + 1 ؛ // الملكة التالية arr [k-1] = 0 ؛ }} آخر {k = k - 1 ؛ // backtrack ، Queen}}} backdate (4) ؛ // [2 ، 4 ، 1 ، 3] // [3 ، 1 ، 4 ، 2]طريقة التراجع العودية
مكالمات العودية تقلل بشكل كبير من كمية الكود وزيادة قابلية قراءة البرنامج.
var arr = [] ، n = 4 ؛ function backtrack (k) {if (k> n) {console.log (arr) ؛ } آخر {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) {// stridle method function linked (s1 ، s2) {return s1.slice (-1) == s2 "reced" ، "تنمو") ؛تبدو بسيطة للغاية أم لا! ومع ذلك ، فإن فرضية الاستخدام هي أنك لا تهتم بالأداء ، إنها حقًا مضيعة للوقت!
فيما يلي تطبيق JavaScript. إذا كنت مهتمًا ، فيمكنك دراسة كيفية استخراج التراجع.
وظيفة Ambrun (func) {var choices = [] ؛ مؤشر فار ؛ دالة AMB (القيم) {if (values.length == 0) {fail () ؛ } if (index == choices.length) {choices.push ({i: 0 ، count: dorder.length}) ؛ } var choice = Choices [index ++] ؛ قيم الإرجاع [choice.i] ؛ } fails fail () {throw fail ؛ } بينما (صحيح) {try {index = 0 ؛ إرجاع Func (AMB ، FAIL) ؛ } catch (e) {if (e! = fail) {throw e ؛ } var choice ؛ بينما ((choice = choices.pop ()) && ++ choice.i == choice.count) {} if (choice == undefined) {return undefined ؛ } choices.push (choice) ؛ }}}والرمز المحدد لمشكلة كوينز الثمانية التي تم تنفيذها باستخدام AMB
ambrun (function (amb ، fail) {var n = 4 ؛ var arr = [] ؛ var turn = [] ؛ for (var n = 0 ؛ n <n ؛ n ++) {turn [turn.length] = n +1 ؛} بينما (n--) {arr.length] = amb (turn) ؛} for (var i = 0 ؛ var a = arr [i] ، b = arr [j] ؛حل جافا سكريبت لمشكلة كوينز الثمانية
هذا هو حل JavaScript لمشكلة Queens الثمانية. لا يستخدم البرنامج بأكمله للحلقات ، ويتم تنفيذه من خلال العودية. يستخدم بالكامل الخريطة ، وتقليل ، وتصفية ، ومسلسل ، وشريحة طرق كائن الصفيف.
"استخدام صارم" ؛ var queens = function (proderersize) {// استخدم العواقب لإنشاء فاصل زمني صفيف من البداية إلى النهاية = function (start ، end) {if (start> end) {return [] ؛ } الفاصل الزمني للعودة (ابدأ ، نهاية - 1) .Concat (نهاية) ؛ } ؛ // تحقق مما إذا كان المركب صالح var isValid = function (queencol) {// تحقق مما إذا كان هناك تعارض بين موضعين var issafe = function (pointa ، pointb) {var slope = (pointa.row - pointb.row) / (pointa.col - pointb.col) ؛ if ((0 === Slope) || (1 === Slope) || (-1 === Slope)) {return false ؛ } إعادة صواب ؛ } ؛ var len = queencol.length ؛ var pointtocompare = {row: queenencol [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 vertal (1 ، boardersize) .map (function (i) {return [i] ؛}) ؛ } // أولاً قم بتوسيع مجموعة جميع الأعمدة السابقة التي تتوافق مع القواعد ، ثم استخدم تقليل الحد من الأبعاد ، وأخيراً استخدم isValid لتصفية المجموعات التي تتوافق مع القواعد الإرجاع Queencols (الحجم - 1) .map (وظيفة (Queenencol) ب) {return A.Concat (B) ؛ } ؛ . 7 ، 5]]ملاحظة: تمديد مشكلة الملكة
عندما سأل لاعب الشطرنج ماكس بيزيل عن لغز كوينز الثمانية في عام 1848 ، ربما كان يعتقد أبدًا أنه بعد أكثر من 100 عام ، أصبحت هذه المشكلة واحدة من أهم الدورات الإلزامية في تعلم البرمجة. تبدو مشكلة كوينز الثمانية بسيطة للغاية: ضع الملكات الثمانية على لوحة الشطرنج حتى لا تهاجم الملكات الثمانية بعضها البعض (لوحة الشطرنج عبارة عن صفيف مربع 8 × 8 ، ويمكن للملكة اتخاذ أي خطوات متعددة في أي من الاتجاهات الثمانية أفقيًا ورأسيًا). على الرغم من وجود 92 حلًا لهذه المشكلة ، إلا أنه ليس من السهل العثور على حل واحد بأيدي عارية. الشكل التالي هو أحد الحلول:
هناك العديد من المتغيرات لمشكلة كوينز الثمانية ، ولكن بغض النظر عن مدى صعوبة ذلك ، فلن تكون أكثر وسيمًا من المتغير التالي: يرجى تصميم خطة لوضع ملكة في كل صف وكل عمود من لوح الشطرنج اللانهائي ، بحيث لا تهاجم جميع الملكات بعضها البعض. على وجه التحديد ، لنفترض أن الزاوية اليسرى السفلى من هذه اللوحة هي في الأصل ، مع وجود صفوف لا حصر لها من أسفل إلى أعلى وأعمدة لا حصر لها من اليسار إلى اليمين ، تحتاج إلى معرفة ترتيب جميع الأعداد الصحيحة الإيجابية A1 ، A2 ، A3 ، ... لذلك عندما تضع الملكة الأولى في الصف الأول في العمود A1 ، الملكة الثانية في العلامة A2 ، وما إلى ذلك ، لن يتمثل أي من قوائم الانتظار.
هنا بناء بسيط جدا وذكي. أولاً ، نقدم إجابة لمشكلة كوينز الخمسة. والأهم من ذلك ، أن إحدى الملكات تحتل الشبكة في الزاوية اليسرى السفلية.
بعد ذلك ، نقوم بتوسيع حل الملكات الخمسة إلى 25 ملكات ، واستنادا إلى تخطيط الملكات الخمسة نفسها:
نتيجة لذلك ، من الواضح أن الملكات الخمسة في نفس المجموعة لن تهاجم بعضها البعض ، ومن الواضح أن الملكات في مجموعات مختلفة لن تهاجم بعضها البعض. هذا هو حل 25 ملكة يفي بالمتطلبات. لاحظ أنه بعد التوسع ، لم يتغير القسم المملوء سابقًا.
ماذا يجب أن أفعل بعد ذلك؟ هذا صحيح ، قمنا بنسخ الـ 25 ملكة في خمس قطع ، وقمنا بترتيبها مرة أخرى وفقًا لتخطيط الملكات الخمسة ، وبالتالي التوسع إلى 125 ملكًا!
من خلال التوسع باستمرار إلى الخارج بناءً على الأجزاء المملوءة مثل هذا ، يمكنك إنشاء حل لمشكلة الملكة اللانهائية.