เกี่ยวกับการแก้ปัญหา JavaScript สำหรับปัญหาแปดควีนส์ฉันมักจะรู้สึกว่าฉันต้องเรียนรู้อัลกอริทึม มันจะน่าอายที่จะรู้ว่าฉันใช้มันวันหนึ่งหรือไม่
พื้นหลัง
คำถามที่แปดของควีนส์เป็นคำถามที่อิงกับหมากรุก: จะวางควีนส์แปดตัวบนกระดานหมากรุก 8 × 8 เพื่อไม่ให้ราชินีสามารถกินควีนส์อื่นได้โดยตรง? เพื่อให้บรรลุสิ่งนี้ราชินีไม่สามารถอยู่ในแนวนอนแนวตั้งแนวตั้งหรือเส้นทแยงมุมเดียวกัน
ปัญหาทั้งแปดของควีนส์สามารถสรุปได้โดยทั่วไปกับปัญหาทั่วไปของ N Queen: ในเวลานี้ขนาดของกระดานหมากรุกจะกลายเป็น N × N และจำนวนราชินีก็กลายเป็น n ถ้าถ้า n = 1 หรือ n ≥ 4 มีวิธีแก้ปัญหา
อัลกอริทึมการแจงนับตาบอด
ผ่านลูป n-fold โซลูชันที่ระบุที่ตรงกับข้อ จำกัด (มีรหัสลูปแปดเท่าหลายรหัสลูปสี่เท่าจะดำเนินการที่นี่) ค้นหาตำแหน่งที่เป็นไปได้ทั้งหมดของสี่ราชินีจากนั้นตัดสินในบอร์ดทั้งหมดว่าสี่ราชินีเหล่านี้จะกินกันและกันโดยตรง แนวคิดของโปรแกรมค่อนข้างง่าย
ฟังก์ชั่น check1 (arr, n) {สำหรับ (var i = 0; i <n; i ++) {สำหรับ (var j = i+1; j <n; j ++) {ถ้า ((arr [i] == arr [j]) || math.abs (arr [i] - arr [j]) == j - i) }}} return true;} function queen1 () {var arr = []; สำหรับ (arr [0] = 1; arr [0] <= 4; arr [0] ++) {สำหรับ (arr [1] = 1; arr [1] <= 4; arr [1] ++) {สำหรับ (arr [2] = 1; arr [2] <= 4; arr [2] ++) {สำหรับ (arr [3] = 1; ดำเนินการต่อ; } else {console.log (arr); - - - -เกี่ยวกับผลลัพธ์ในกระดานหมากรุก 4*4 สี่ควีนส์ไม่สามารถอยู่ในแถวได้ arr [0] ถึง arr [3] สอดคล้องกับสี่ควีนส์ตามลำดับ ค่าที่สอดคล้องกับตัวห้อยของอาร์เรย์และตัวห้อยเป็นตำแหน่งของราชินีในบอร์ด
วิธีการย้อนรอย
"ถ้าคุณไปไม่ได้ก็หันหลังกลับ" ตรวจสอบว่ามันตรงกับที่โหนดที่เหมาะสมหรือไม่ หากไม่ตรงกันคุณจะไม่สำรวจสาขานี้อีกต่อไป
ฟังก์ชั่น check2 (arr, n) {สำหรับ (var i = 0; i <= n - 1; i ++) {ถ้า ((math.abs (arr [i] - arr [n]) == n - i) || (arr [i] == arr [n])) {return false; }} return true;} function queen2 () {var arr = []; สำหรับ (arr [0] = 1; arr [0] <= 4; arr [0] ++) {สำหรับ (arr [1] = 1; arr [1] <= 4; arr [1] ++) {ถ้า (! check2 (arr, 1)) ดำเนินการต่อ; // ระบุความขัดแย้งระหว่างสองควีนส์สำหรับ (arr [2] = 1; arr [2] <= 4; arr [2] ++) {ถ้า (! check2 (arr, 2)) ดำเนินการต่อ; // ระบุความขัดแย้งระหว่างสามควีนส์สำหรับ (arr [3] = 1; arr [3] <= 4; arr [3] ++) {ถ้า (! check2 (arr, 3)) {ดำเนินการต่อ; } else {console.log (arr); - - - -การย้อนรอยแบบไม่กลับคืนมา
กรอบอัลกอริทึม:
ในขณะที่ (k> 0 『มีวิธีที่จะไป』 และ 『ไม่ถึงเป้าหมาย』) {// k> 0 『มีวิธีที่จะไปถ้า (k> n) {// ค้นหาโหนดใบไม้ // ค้นหาทางออก}} {// a [k] ค่าแรกที่เป็นไปได้ในขณะที่ ( พื้นที่ค้นหา ") {// ทำเครื่องหมายทรัพยากรที่ครอบครอง // k = k + 1; } else {// ทำความสะอาดพื้นที่รัฐที่ถูกครอบครอง // k = k - 1; -รหัสเฉพาะมีดังนี้ ชั้นนอกสุดในขณะที่มีสองส่วน หนึ่งคือการสำรวจค่านิยมที่เป็นไปได้ของราชินีในปัจจุบันและอีกอย่างคือการตัดสินใจว่าจะป้อนเลเยอร์ถัดไปหรือย้อนกลับเลเยอร์ก่อนหน้า
ฟังก์ชั่น backdate (n) {var arr = []; var k = 1; // ราชินี nth 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) {ถ้า (k == n) {// nth ราชินีคอนโซล log (arr); } else {k = k + 1; // ราชินีต่อไป arr [k-1] = 0; }} else {k = k - 1; // Backtrack, Last Queen}}} backdate (4); // [2, 4, 1, 3] // [3, 1, 4, 2]วิธีย้อนกลับแบบเรียกซ้ำ
การโทรแบบเรียกซ้ำลดจำนวนรหัสและเพิ่มความสามารถในการอ่านของโปรแกรมได้อย่างมาก
var arr = [], n = 4; function backtrack (k) {ถ้า (k> n) {console.log (arr); } else {สำหรับ (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 คืออะไร? ให้รายการข้อมูลซึ่งสามารถส่งคืนวิธีการตอบสนองสถานการณ์ความสำเร็จของข้อ จำกัด หากไม่ประสบความสำเร็จมันจะล้มเหลว แน่นอนว่ามันสามารถคืนสถานการณ์ความสำเร็จทั้งหมด ผู้เขียนได้เขียนคะแนนมากมายด้านบนเพื่อแนะนำอัลกอริทึม AMB นี้ที่นี่ เหมาะสำหรับการจัดการสถานการณ์ย้อนกลับอย่างง่าย มันน่าสนใจมาก มาดูกันว่ามันทำงานอย่างไร
ก่อนอื่นให้จัดการกับปัญหาเล็ก ๆ น้อย ๆ ค้นหาสตริงที่อยู่ติดกัน: รับอาร์เรย์สตริงหลายชุดและแต่ละอาร์เรย์จะออกสตริง อักขระสุดท้ายของสตริงก่อนหน้านี้เหมือนกับอักขระตัวแรกของสตริงถัดไป หากเป็นไปตามเงื่อนไขแล้วสตริงที่ดึงมาใหม่จะถูกส่งออก
ambrun (ฟังก์ชั่น (amb, fail) {// ฟังก์ชั่นวิธีการ จำกัด การเชื่อมโยง (S1, S2) {return s1.slice (-1) == s2.slice (0, 1);} // รายการข้อมูล inject var w1 = amb ("", ",", "]; "Tread", "Grows"]);มันดูง่ายสุด ๆ หรือไม่! อย่างไรก็ตามสถานที่ตั้งของการใช้คือคุณไม่สนใจเกี่ยวกับประสิทธิภาพมันเสียเวลาจริงๆ!
ด้านล่างคือการใช้งาน JavaScript หากคุณสนใจคุณสามารถศึกษาวิธีการสกัดย้อนหลัง
ฟังก์ชั่น ambrun (func) {ตัวเลือก var = []; ดัชนี var; ฟังก์ชั่น Amb (ค่า) {ถ้า (value.length == 0) {fail (); } if (index == choices.length) {choices.push ({i: 0, count: values.length}); } var choice = ตัวเลือก [index ++]; ค่าส่งคืน [choice.i]; } ฟังก์ชั่นล้มเหลว () {โยนล้มเหลว; } ในขณะที่ (จริง) {ลอง {index = 0; ส่งคืน func (amb, ล้มเหลว); } catch (e) {ถ้า (e! = ล้มเหลว) {โยน e; } ตัวเลือก var; ในขณะที่ ((ตัวเลือก = choices.pop ()) && ++ choice.i == ตัวเลือก. count) {} ถ้า (ตัวเลือก == undefined) {return undefined; } choices.push (ตัวเลือก); -และรหัสเฉพาะของปัญหาแปดควีนส์ที่ใช้โดยใช้ Amb
ambrun (ฟังก์ชั่น (amb, fail) {var n = 4; var arr = []; var turn = []; สำหรับ (var n = 0; n <n; n ++) {turn [turn.length] = n +1;} ในขณะที่ (n--) {arr [arr.length] = amb (turn);}; var a = arr [i], b = arr [j];การแก้ปัญหา JavaScript สำหรับปัญหาแปดควีนส์
นี่คือวิธีแก้ปัญหา JavaScript สำหรับปัญหาแปดควีนส์ โปรแกรมทั้งหมดไม่ได้ใช้สำหรับลูปและดำเนินการผ่านการเรียกซ้ำ มันใช้ประโยชน์จากแผนที่ลดการกรอง concat วิธีการชิ้นของวัตถุอาร์เรย์
'ใช้อย่างเข้มงวด'; var queens = function (boardersize) {// ใช้การเรียกซ้ำเพื่อสร้างช่วงเวลาอาร์เรย์ var ตั้งแต่เริ่มต้นจนจบ = ฟังก์ชั่น (เริ่มต้น, สิ้นสุด) {ถ้า (เริ่มต้น> สิ้นสุด) {return []; } return Interval (เริ่มต้นสิ้นสุด - 1) .concat (สิ้นสุด); - // ตรวจสอบว่าชุดค่าผสมนั้นถูกต้อง var isvalid = ฟังก์ชั่น (queencol) {// ตรวจสอบว่ามีความขัดแย้งระหว่างสองตำแหน่ง var issafe = ฟังก์ชั่น (pointa, pointb) {var slope = (pointa.row - pointb.row) / (pointa.col - pointb.col); if ((0 === ความลาดชัน) || (1 === ความลาดชัน) || (-1 === ความลาดชัน)) {return false; } return true; - var len = queencol.length; var pointtocompare = {row: queencol [len - 1], col: len}; // ชิ้นแรกแยกอาร์เรย์ยกเว้นคอลัมน์สุดท้ายจากนั้นทดสอบว่ามีความขัดแย้งระหว่างคะแนนในแต่ละคอลัมน์และจุดที่จะทดสอบและในที่สุดก็รวมผลการทดสอบ return queencol .slice (0, len - 1) .map (ฟังก์ชั่น (แถว, ดัชนี) {return issafe ({row: row, col: index + 1}, pointtocompare);}). reduce (ฟังก์ชั่น (a, b) {return a && b;}); - // สร้างชุดค่าผสมที่สอดคล้องกับกฎ var var queencols = ฟังก์ชั่น (ขนาด) {ถ้า (1 === ขนาด) {ช่วงเวลาคืน (1, Boardersize) .map (ฟังก์ชั่น (i) {return [i];}); } // ก่อนขยายชุดของคอลัมน์ก่อนหน้าทั้งหมดทั้งหมดที่สอดคล้องกับกฎจากนั้นใช้ลดการลดขนาดของมิติและในที่สุดก็ใช้ isvalid เพื่อกรองชุดค่าผสมที่สอดคล้องกับกฎคืน queencols (ขนาด - 1) .map (ฟังก์ชั่น (queencol) {return interval (a, b) {return a.concat (b);}) .filter (isvalid); - // jueens function entry return queencols (boardersize);}; 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: ขยายปัญหาของราชินี
เมื่อผู้เล่นหมากรุกแม็กซ์เบซเซิลถามปริศนาของควีนส์แปดตัวในปี 2391 เขาอาจไม่เคยคิดว่ามากกว่า 100 ปีต่อมาปัญหานี้กลายเป็นหนึ่งในหลักสูตรภาคบังคับที่สำคัญที่สุดในการเรียนรู้การเขียนโปรแกรม ปัญหาทั้งแปดของควีนส์ฟังดูง่ายมาก: วางราชินีแปดตัวบนกระดานหมากรุกเพื่อให้ทั้งแปดควีนส์ไม่โจมตีซึ่งกันและกัน (กระดานหมากรุกเป็นอาร์เรย์ 8 × 8 ตารางและราชินีสามารถทำหลายขั้นตอนในแปดทิศทางในแนวนอนและแนวตั้ง) แม้ว่าจะมีวิธีแก้ปัญหานี้ 92 วิธี แต่ก็ไม่ใช่เรื่องง่ายที่จะหาวิธีแก้ปัญหาหนึ่งด้วยมือเปล่า รูปต่อไปนี้เป็นหนึ่งในวิธีแก้ปัญหา:
มีปัญหาหลายอย่างของแปดควีนส์ แต่ไม่ว่ามันจะยากแค่ไหนมันจะไม่หล่อกว่าตัวแปรต่อไปนี้: โปรดออกแบบแผนการวางราชินีในทุกแถวและทุกคอลัมน์ของกระดานหมากรุกที่ไม่มีที่สิ้นสุด โดยเฉพาะสมมติว่ามุมซ้ายล่างของบอร์ดนี้อยู่ที่จุดกำเนิดโดยมีแถวที่ไม่มีที่สิ้นสุดจากล่างขึ้นบนและคอลัมน์ที่ไม่มีที่สิ้นสุดจากซ้ายไปขวาคุณต้องค้นหาการจัดเรียงของจำนวนเต็มบวกทั้งหมด A1, A2, A3, ... ดังนั้นเมื่อคุณวางราชินีแรกในแถวแรกในคอลัมน์ A1 ที่สองในคอลัมน์ A2
นี่คือการก่อสร้างที่เรียบง่ายและฉลาดมาก ก่อนอื่นเราให้คำตอบสำหรับปัญหาทั้งห้าควีนส์ และที่สำคัญมากหนึ่งในควีนส์ครอบครองกริดที่มุมล่างซ้าย
ต่อไปเราจะขยายการแก้ปัญหาของราชินีทั้งห้าไปยังราชินี 25 ราชินีและขึ้นอยู่กับเค้าโครงของทั้งห้าควีนส์:
เป็นผลให้ทั้งห้าควีนส์ในกลุ่มเดียวกันเห็นได้ชัดว่าจะไม่โจมตีซึ่งกันและกันและควีนส์ในกลุ่มต่าง ๆ จะไม่โจมตีซึ่งกันและกันอย่างเห็นได้ชัด นี่คือโซลูชันสมเด็จพระราชินี 25 ที่ตรงตามข้อกำหนด โปรดทราบว่าหลังจากการขยายตัวส่วนที่เติมก่อนหน้านี้ไม่เปลี่ยนแปลง
ฉันควรทำอย่างไรต่อไป? ถูกต้องแล้วเราคัดลอกการปลดล็อคของราชินี 25 ชิ้นออกเป็นห้าชิ้นและจัดมันอีกครั้งตามรูปแบบของทั้งห้าควีนส์จึงขยายไปถึง 125 ควีนส์!
ด้วยการขยายออกไปอย่างต่อเนื่องโดยขึ้นอยู่กับส่วนที่เต็มไปด้วยสิ่งนี้คุณสามารถสร้างทางออกให้กับปัญหาราชินีที่ไม่มีที่สิ้นสุด