لغز
مشكلة الملكة. ضع N Queens على لوحة الشطرنج في NXN ، حيث لا يوجد ملكتان في نفس الصف ، في نفس العمود ، أو في نفس قطري حتى لا يتمكنوا من مهاجمة بعضهما البعض.
الاستراتيجية
طريقة التراجع.
حل جافا سكريبت
خذ سؤال الملكة الثماني كمثال:
نسخة الكود كما يلي:
/**
* تم إنشاؤه بواسطة Chao في 12/28/14.
*/
وظيفة getNqueens (الطلب) {
if (order <4) {
console.log ('N Queens مشكلة تنطبق للحصول على طلب أكبر من 3') ؛
يعود؛
}
var nqueens = [] ؛
var backtracking = false ؛
Rowloop:
لـ (var row = 0 ؛ row <order ؛ row ++) {
if (nqueens [row] === undefined) {
nqueens [row] = [] ؛
}
لـ (var col = 0 ؛ col <order ؛ col ++) {
if (nqueens [row] [col] === 0) {
يكمل؛
} آخر إذا (backtracking && nqueens [row] [col] == 1) {
if (col === order-1) {
Resetrow (nqueens ، order ، row) ؛
الصف = الصف - 2 ؛
متابعة Rowloop.
}
nqueens [row] [col] = 0 ؛
التراجع = خطأ ؛
يكمل؛
}
nqueens [row] [col] = 1 ؛
if (isqueenvalid (nqueens ، row ، col)) {
متابعة Rowloop.
} آخر إذا (col == order-1) {
التراجع = صحيح ؛
Resetrow (nqueens ، order ، row) ؛
الصف = الصف - 2 ؛
متابعة Rowloop.
} آخر {
nqueens [row] [col] = 0 ؛
يكمل؛
} ؛
}
}
إرجاع nqueens.
}
وظيفة RESERTROW (nqueens ، الطلب ، الصف) {
لـ (var col = 0 ؛ col <order ؛ col ++) {
nqueens [row] [col] = غير محدد ؛
}
}
وظيفة isqueenvalid (nqueens ، الصف ، العقيد) {
لـ (var i = 0 ؛ i <col ؛ i ++) {
if (nqueens [row] [i] == 1) {
العودة كاذبة
}
}
لـ (var j = 1 ؛ j <row+1 ؛ j ++) {
إذا (nqueens [row-j] [col] == 1 || (nqueens [row-j] [col-j]! = undefined && nqueens [row-j] [col-j] == 1) || (nqueens [row-j] [col+j]! = undefined && nqueens [row-j] [col+j] == 1)) {
العودة كاذبة
}
}
العودة صحيح.
}
وظيفة printqueens (Queens) {
لـ (var row = 0 ؛ row <queens.length ؛ row ++) {
var rowtext = '' ؛
لـ (var col = 0 ؛ col <queens.length ؛ col ++) {
if (Queens [row] [col] === undefined) {
Queens [row] [col] = 0 ؛
}
Rowtext = Rowtext + Queens [row] [col] + '' ؛
}
console.log (rowtext) ؛
}
}
var Queens = getNqueens (8) ؛
printqueens (Queens) ؛
نتيجة
نسخة الكود كما يلي:
1 0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0