คำอธิบายปัญหา: วางราชินีแปดตัวไว้บนกระดานหมากรุก ห้ามมีราชินีสองตัวโจมตีกันเอง (นั่นคือ ไม่มีราชินีสองตัวอยู่ในแถว คอลัมน์ หรือแนวทแยงเดียวกัน) ดังที่แสดงในภาพ
ในบทความนี้ มีการใช้วิธีแก้ปัญหาที่แตกต่างกันเล็กน้อยสำหรับปัญหาทั้งสอง แต่ทั้งคู่ใช้อาร์เรย์หนึ่งมิติ ใน 6.20 จำเป็นต้องค้นหาเลย์เอาต์ที่มีประสิทธิภาพ ฉันสร้างอาร์เรย์หนึ่งบิตที่มีแปดองค์ประกอบโดยการสุ่มค่าของอาร์เรย์ และเปรียบเทียบค่ากับตัวห้อย ในที่สุดฉันก็ได้เลย์เอาต์ที่มีประสิทธิภาพ 6.22 จำเป็นต้องมี ค้นหาทั้งหมด เค้าโครงที่มีประสิทธิภาพ ในที่นี้ฉันใช้เลขฐานแปด สำรวจตัวเลขทั้งหมดตั้งแต่ 001234567-076543210 แปลงเป็นสตริงฐานแปด เปรียบเทียบแต่ละบิตด้วยตัวห้อย และส่งเอาต์พุตโครงร่างที่ตรงตามเงื่อนไข หลักการและวิธีการนำไปใช้จะมีรายละเอียดด้านล่าง
ส่วนที่ 1 วิธีตัดสินว่าเป็นเค้าโครงที่ถูกต้องหรือไม่
เราถือว่ากระดานหมากรุกเป็นเมทริกซ์ขนาด 8*8 มีค่าตั้งแต่ 0-7 เมื่อสังเกตภาพทางด้านซ้าย คุณจะพบว่าเลย์เอาท์สามารถแสดงได้ด้วยชุดตัวเลขคู่ (จากบนลงล่าง) ได้แก่ (0, 0), (1, 6), (2, 3), (3 , 5), (4, 7), (5, 1), (6, 4), (7, 2) แสดงโดยอาร์เรย์ นั่นคือ int []list = {0, 6, 3, 5, 7, 1, 4, 2};
เห็นได้ชัดว่านี่เป็นเลย์เอาต์ที่ถูกต้อง ต่อไป เราต้องพิจารณาคำถาม: ในรูปแบบที่มีประสิทธิภาพ มีความสัมพันธ์ใดๆ ระหว่างตัวห้อยและค่าที่สอดคล้องกันในอาร์เรย์ นั่นคือ i และ list[i] หรือไม่?
ที่นี่เราตั้งค่า list[i] = k; list[j] = q; (i > j) ซึ่งตรงตามเงื่อนไขสองประการต่อไปนี้ (จะเข้าใจง่ายกว่าเมื่อวาดบนกระดาษ):
1. เค != คิว;
2. i - j == k - q หรือ i - j == q -k (ได้มาจากคำถาม)
เพื่อให้แน่ใจว่า k != q รายการอาร์เรย์จะถูกประกาศและเริ่มต้นที่นี่ โดยที่ list[i] = i จากนั้นสุ่มสับเปลี่ยนอาร์เรย์ แล้วตรวจสอบว่าตรงตามเงื่อนไขที่ 2 หรือไม่
คัดลอกรหัสรหัสดังต่อไปนี้:
// สร้างและเริ่มต้นอาร์เรย์
int [] รายการ = int ใหม่ [arrSize];
สำหรับ (int i = 0; i < arrSize; i++)
รายการ [i] = ฉัน;
// สุ่มสับเปลี่ยนอาเรย์
โมฆะสาธารณะแบบคงที่ RandomizeArray (รายการ int []) {
int arrSize = list.length;
int ranIndex;
สำหรับ(int i = 0; i < arrSize; i++){
ranIndex = (int)(Math.random() * arrSize);
ถ้า (ranIndex ! = i) {
int temp = รายการ [i];
รายการ [i] = รายการ [ranIndex];
รายการ [ranIndex] = อุณหภูมิ;
-
-
-
เนื้อโค้ดของ 6.20 มีดังต่อไปนี้
คัดลอกรหัสรหัสดังต่อไปนี้:
// 6.20 เกม: Eight Queens
โมฆะสาธารณะ solveEightQueens(){
int arrSize = 8;
int [] รายการ = int ใหม่ [arrSize];
สำหรับ (int i = 0; i < arrSize; i++)
รายการ [i] = ฉัน;
นับจำนวน = 0;
บูลีน notValid = จริง;
ในขณะที่ (ไม่ถูกต้อง) {
นับ++;
notValid = เท็จ;
RandomizeArray(รายการ);
สำหรับ(int i = 0; i < arrSize; i++){
สำหรับ(int j = i + 1; j < arrSize; j++){
if(j - i == Math.abs(list[j] - list[i])){/ // ตรวจสอบว่าตรงตามเงื่อนไขหรือไม่
notValid = จริง;
หยุดพัก;
-
-
ถ้า (ไม่ถูกต้อง) พัง;
} // สิ้นสุดด้านนอกของ for loop
} // สิ้นสุดในขณะที่
// พิมพ์ผลลัพธ์
ฉัน;
System.out.println("O(∩_∩)Ohaha~, ฉันได้ลอง " + count + " ครั้งแล้วและในที่สุดก็สำเร็จ");
สำหรับ(i = 0; i < arrSize - 1; i++){
System.out.print("(" + i + ", " + รายการ [i] + "), ");
-
System.out.println("(" + i + ", " + รายการ [i] + ")");
-
ส่วนที่ 2 ค้นหาเค้าโครงที่ถูกต้องทั้งหมด
เนื่องจากเวอร์ชัน 6.22 ต้องการการค้นหาโครงร่างแปดควีนที่ถูกต้องทั้งหมด วิธีการสุ่มสับเปลี่ยนอาร์เรย์จึงไม่สามารถใช้ได้อีกต่อไป ดังนั้นเราจึงต้องหาวิธีการที่สามารถสำรวจอาร์เรย์ที่เป็นไปได้ทั้งหมด วิธีหนึ่งที่ตรงที่สุดก็คือการใช้ for loop 8 เลเยอร์ แต่โค้ดมีจำนวนมากเกินไป และ head จะเป็นสีจางได้ง่าย ดังนั้นจึงไม่ได้ใช้วิธีนี้
เมื่อสังเกตค่าของอาร์เรย์ในส่วนที่ 1 อย่างระมัดระวัง คุณจะพบว่าค่าทั้งหมดอยู่ระหว่าง 0-7 ดังนั้นการสำรวจโดยใช้เลข int ฐานแปดจึงมั่นใจได้ว่าจะรวมการเรียงสับเปลี่ยนทุกครั้งด้วย เนื่องจากตัวเลขแปดหลักแตกต่างกัน จึงมีการเรียงสับเปลี่ยนที่เป็นไปได้ 8 = 40320 และจำนวนเลขฐานแปดทั้งหมดคือ 8^8 = 16777216 ดังนั้นอัตราส่วนที่เป็นไปได้จึงคิดเป็น 40320/16777216 = 1/416 ผลลัพธ์ที่ได้คือ 40320 การเรียงสับเปลี่ยน นอกจากนี้ยังมีการตรวจสอบเพื่อกรองเค้าโครงที่ถูกต้องขั้นสุดท้าย วิธีนี้ยังคงไม่มีประสิทธิภาพเล็กน้อย แต่ฉันยังไม่พบวิธีที่มีประสิทธิภาพมากกว่านี้
คัดลอกรหัสรหัสดังต่อไปนี้:
// 6.22 เกม: วิธีแก้ปัญหาต่าง ๆ สำหรับปัญหาแปดควีน (เพิ่มค่า int จากนั้นแปลงเป็นสตริงฐานแปดแล้วตรวจสอบ)
โมฆะคงที่สาธารณะ solveEightQueensMethod(){
int start = 001234567; // Octal
int end = 076543210; // ฐานแปด
int count = 0; // คำนวณจำนวนเลย์เอาต์ที่ถูกต้อง
สำหรับ(int i = start; i < end; i++){
บูลีน isValid = isValid(i);
ถ้า (ถูกต้อง) {
ถ้า(++นับ% 7 == 0)
System.out.println(จำนวนเต็มtoOctalString(i) + ":" + isValid);
อื่น System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
-
-
System.out.println("count = " + count); // ส่งออกจำนวนเค้าโครงที่ถูกต้อง
-
// ตรวจสอบว่าตัวเลขเป็นรูปแบบที่ถูกต้องหรือไม่
isValid บูลีนคงที่สาธารณะ (หมายเลข int) {
สตริง numOct = Integer.toOctalString (หมายเลข);
int arrSize = numOct.length();
if(arrSize==7) { // หากตัวเลขตัวแรกเป็น 0 แสดงว่าสตริงที่สร้างขึ้นจะมีอักขระเพียงเจ็ดตัวเท่านั้น
numOct = '0' + numOct;
arrSize++;
-
สำหรับ(int i = 1; i < arrSize; i ++){
สำหรับ(int j = i - 1; j >= 0; j--){
if(numOct.charAt(i) == numOct.charAt(j)) คืนค่าเท็จ; // คอลัมน์เดียวกัน
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) คืนค่าเท็จ // เส้นทแยงมุมเดียวกัน
-
-
กลับเป็นจริง;
-
ส่วนที่ 3 ส่วนขยาย: ปัญหาในการสร้างชุดค่าผสม
มีคำถามดังกล่าวในการทดสอบข้อเขียนเมื่อปีที่แล้ว เมื่อได้รับลำดับ ให้ส่งออกชุดค่าผสมทั้งหมด ตัวอย่างเช่น,
เอาต์พุตของ "123": 1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321
ผลลัพธ์ของ "abcd": a, b, c, d, ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc, abc, acb, abd, adb, acd, adc, ..., เอบีซีดี, ...
ในเวอร์ชัน 6.22 วิธีการที่ใช้ในการค้นหาเค้าโครงแบบแปดราชินีทั้งหมดคือการเพิ่มหมายเลขประเภท int แล้วตรวจสอบทีละรายการ ปัญหาข้างต้นสามารถแก้ไขได้ในลักษณะเดียวกัน อย่างไรก็ตาม ประสิทธิภาพค่อนข้างต่ำ หากมีวิธีที่มีประสิทธิภาพมากกว่านี้ โปรดขอคำแนะนำจากผู้เชี่ยวชาญ