ปริศนา
ปัญหาของราชินี วาง n ควีนส์บนกระดานหมากรุกใน NXN ซึ่งไม่มีควีนส์สองตัวอยู่ในแถวเดียวกันในคอลัมน์เดียวกันหรือในแนวทแยงเดียวกันเพื่อที่พวกเขาจะไม่สามารถโจมตีซึ่งกันและกันได้
กลยุทธ์
วิธีการย้อนรอย
โซลูชัน JavaScript
นำคำถาม 8 ข้อของราชินีเป็นตัวอย่าง:
การคัดลอกรหัสมีดังนี้:
-
* สร้างโดย Chao เมื่อวันที่ 12/28/14
-
ฟังก์ชั่น getnqueens (คำสั่งซื้อ) {
ถ้า (สั่งซื้อ <4) {
console.log ('n Queens ปัญหาใช้สำหรับการสั่งซื้อที่ใหญ่กว่า 3');
กลับ;
-
var nqueens = [];
var backtracking = false;
Rowloop:
สำหรับ (var row = 0; row <order; row ++) {
if (nqueens [row] === ไม่ได้กำหนด) {
nqueens [row] = [];
-
สำหรับ (var col = 0; col <order; col ++) {
ถ้า (nqueens [row] [col] === 0) {
ดำเนินการต่อ;
} อื่นถ้า (backtracking && nqueens [row] [col] == 1) {
if (col === order-1) {
Resetrow (nqueens, order, row);
แถว = แถว - 2;
ดำเนินการต่อ Rowloop;
-
nqueens [แถว] [col] = 0;
backtracking = false;
ดำเนินการต่อ;
-
nqueens [แถว] [col] = 1;
if (isqueenvalid (nqueens, row, col)) {
ดำเนินการต่อ Rowloop;
} อื่นถ้า (col == order-1) {
backtracking = true;
Resetrow (nqueens, order, row);
แถว = แถว - 2;
ดำเนินการต่อ Rowloop;
} อื่น {
nqueens [แถว] [col] = 0;
ดำเนินการต่อ;
-
-
-
กลับ NQUEENS;
-
ฟังก์ชั่น Resetrow (nqueens, order, row) {
สำหรับ (var col = 0; col <order; col ++) {
nqueens [row] [col] = undefined;
-
-
ฟังก์ชั่น isqueenvalid (nqueens, row, col) {
สำหรับ (var i = 0; i <col; i ++) {
ถ้า (nqueens [row] [i] == 1) {
กลับเท็จ;
-
-
สำหรับ (var j = 1; j <แถว+1; j ++) {
if (nqueens [row-j] [col] == 1 || (nqueens [row-j] [col-j]! = undefined && nqueens [row-j] [col-j] == 1) || (nqueens [row-j] [col+j]!
กลับเท็จ;
-
-
กลับมาจริง;
-
ฟังก์ชั่น printqueens (ควีนส์) {
สำหรับ (var row = 0; row <queens.length; row ++) {
var rowtext = '';
สำหรับ (var col = 0; col <queens.length; col ++) {
if (Queens [row] [col] === undefined) {
ควีนส์ [แถว] [col] = 0;
-
rowtext = rowtext + ควีนส์ [row] [col] + '';
-
console.log (rowtext);
-
-
var queens = getnqueens (8);
printqueens (ควีนส์);
ผลลัพธ์
การคัดลอกรหัสมีดังนี้:
1 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0