NQueens package

ภาพรวม

ปัญหา N-Queens เป็นความท้าทายแบบคลาสสิกที่พบบ่อยในการสัมภาษณ์การเขียนโปรแกรมและการตั้งค่าทางวิชาการ ความท้าทายคือการวาง n ควีนส์บนกระดานหมากรุก n × n ซึ่งไม่มีควีนส์สองคนคุกคามซึ่งกันและกัน ซึ่งหมายความว่าไม่มีสองควีนส์สามารถแชร์แถวคอลัมน์หรือเส้นทแยงมุมเดียวกันได้

คำสั่งปัญหา

ให้จำนวนเต็ม N ให้คืนโซลูชันที่แตกต่างทั้งหมดไปยังปริศนา N-queens คุณสามารถส่งคืนคำตอบในลำดับใดก็ได้

โซลูชันแต่ละครั้งมีการกำหนดค่าบอร์ดที่แตกต่างกันของตำแหน่ง 'queens' โดยที่ 'Q' หมายถึงราชินีและ ' ระบุพื้นที่ว่าง

ตัวอย่าง

สำหรับ n = 4 วิธีแก้ปัญหาที่เป็นไปได้คือ:

 [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

วิธีการและอัลกอริทึม

อัลกอริทึมการย้อนรอย

วิธีการที่พบบ่อยที่สุดในการแก้ปัญหา N-queens คือการใช้การย้อนรอย อัลกอริทึมการย้อนกลับเพิ่มผู้สมัครในการแก้ปัญหาและยกเลิกผู้สมัครทันทีที่กำหนดว่าผู้สมัครไม่สามารถนำไปสู่การแก้ปัญหาที่ถูกต้อง

ขั้นตอน:

1. Initialize the Board : เริ่มต้นด้วยบอร์ด N × N ที่ว่างเปล่า
2. Place the Queen : พยายามวางราชินีไว้ในแถวแรกและดำเนินการต่อเพื่อวางควีนส์ที่ตามมา
3. Check Validity : สำหรับตำแหน่งราชินีแต่ละตำแหน่งตรวจสอบว่ามันขัดแย้งกับราชินีที่วางไว้แล้วหรือไม่
4. Backtrack if Necessary : หากการวางราชินีจะนำไปสู่การแก้ปัญหาให้ถอดราชินี (Backtrack) ออกแล้วลองตำแหน่งถัดไป
5. Store the Solution : หากพบการกำหนดค่าที่ถูกต้อง (N Queens วาง) ให้เก็บการกำหนดค่าบอร์ด
6. Repeat : ดำเนินการดำเนินการนี้ต่อไปจนกว่าการกำหนดค่าที่เป็นไปได้ทั้งหมดจะได้รับการลอง

ความท้าทาย

การเป็นตัวแทนของคณะกรรมการ

บอร์ดสามารถแสดงโดยใช้รายการ 2D ที่แต่ละเซลล์เป็น 'Q' หรือ '.'

การตรวจสอบความขัดแย้ง

การตรวจสอบความขัดแย้งอย่างมีประสิทธิภาพเป็นสิ่งสำคัญ:

1. Row Check : ตรวจสอบให้แน่ใจว่าไม่มีราชินีอื่นอยู่ในแถวเดียวกัน
2. Column Check : ตรวจสอบให้แน่ใจว่าไม่มีราชินีอื่นอยู่ในคอลัมน์เดียวกัน
3. Diagonal Check : ทำให้แน่ใจว่าไม่มีราชินีอื่นอยู่ในแนวทแยงมุมเดียวกัน

การเพิ่มประสิทธิภาพ

การใช้ชุดเพื่อติดตามคอลัมน์ที่ครอบครองและเส้นทแยงมุมสามารถเร่งกระบวนการตรวจสอบความขัดแย้ง

พร้อมกันกับ threadpoolexecutor

เพื่อเพิ่มประสิทธิภาพการแก้ปัญหาสำหรับ N ที่มีขนาดใหญ่ขึ้นโซลูชันใช้ประโยชน์จากการเกิดขึ้นพร้อมกับ ThreadPoolexecutor:

• แต่ละเธรดเริ่มแก้ปัญหาสำหรับคอลัมน์อื่นในแถวแรก
• วิธีการขนานนี้สามารถลดเวลาในการค้นหาวิธีแก้ปัญหาทั้งหมดได้อย่างมีนัยสำคัญ

ทางออกของเรา

โซลูชันนี้มาจาก ความท้าทายในวันศุกร์ฟรี ของเราซึ่งเราเลือกความท้าทายในการสัมภาษณ์แบบสุ่มในระหว่างการหยุดทำงานเพื่อเขียนโซลูชั่น

การติดตั้ง

 pip install wolfsoftware.NQueens

การใช้งาน

 usage: nqueens [-h] [-v] [-V] [board_size]

See solutions to the NQueens problem.

positional arguments:
  board_size     Size of the board (default is 8 for the Eight Queens puzzle) (default: 8)

flags:
  -h, --help     Show this help message and exit
  -v, --verbose  Enable verbose output - show the actual boards (default: False)
  -V, --version  Show program's version number and exit.

The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

สรุป

ปัญหา N-Queens เป็นความท้าทายที่น่าสนใจและซับซ้อนซึ่งต้องมีความเข้าใจอย่างลึกซึ้งเกี่ยวกับการเรียกซ้ำการย้อนรอยและเทคนิคการเพิ่มประสิทธิภาพ ด้วยการใช้ประโยชน์จากมัลติเธรดการใช้งานนี้มีประสิทธิภาพอย่างมีประสิทธิภาพพบโซลูชันที่เป็นไปได้ทั้งหมดสำหรับขนาดบอร์ดที่กำหนด การทำความเข้าใจและนำปัญหา N-Queens เป็นแบบฝึกหัดที่มีคุณค่าสำหรับการพัฒนาทักษะการแก้ปัญหาและการคิดอัลกอริทึม