การเรียงสับเปลี่ยนและแนวคิด N-Queens
วางสมาชิกและย้อนกลับเมื่อเกิดความขัดแย้ง
การเรียงสับเปลี่ยนและแนวคิด N-Queens เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
จากเซตย่อยสู่การเรียงลำดับ
permutation คือการจัดสมาชิกทั้งหมดให้อยู่ในลำดับใดลำดับหนึ่ง การสร้างสิ่งเหล่านี้คือทักษะการย้อนกลับถัดจากการสร้างเซตย่อย 🔀
มี permutation กี่แบบ
มีn แฟกทอเรียล permutation ของสิ่งของ n ชิ้น เพราะช่องแรกมีทางเลือก n แบบ ช่องถัดไปมี n ลบหนึ่งแบบ และลดลงไปเรื่อย ๆ จำนวนจึงเพิ่มขึ้นอย่างรวดเร็ว
วางสมาชิกทีละตัว
การเรียกซ้ำจะเติมตำแหน่งจากซ้ายไปขวา ในแต่ละขั้น ให้เลือกสมาชิกที่ยังไม่ได้ใช้มาวาง แล้วเรียกซ้ำกับส่วนที่เหลือ
ติดตามว่าสมาชิกใดถูกใช้แล้ว
อาร์เรย์ติดตามการใช้แล้วแบบบูลีนจะระบุว่าสมาชิกใดถูกวางไปแล้ว เพื่อให้สมาชิกแต่ละตัวปรากฏเพียงครั้งเดียวใน permutation ทุกแบบ
permutation ในโค้ด
การย้อนกลับนี้วางค่าที่ยังไม่ได้ใช้ เรียกซ้ำ แล้วคืนค่านั้นให้ว่างสำหรับกิ่งถัดไป
def perm(cur):
if len(cur) == n:
out.append(cur[:]); return
for x in a:
if x not in cur:
perm(cur + [x])ใช้ itertools.permutations เมื่ออนุญาต
ในการแข่งขันที่ต้องการความรวดเร็ว itertools.permutations ของไพทอนจะสร้างการเรียงลำดับทุกแบบให้โดยไม่ต้องเขียนการเรียกซ้ำเอง
from itertools import permutations
for p in permutations(a):
print(p)ปัญหา N-ควีนส์
ปัญหา N-ควีนส์ขอให้วางควีน n ตัวบนกระดานขนาด n คูณ n โดยไม่ให้ควีนตัวใดโจมตีกัน นี่คือโจทย์การย้อนกลับแบบคลาสสิก 👑
ควีนหนึ่งตัวต่อแถว
เนื่องจากควีนสองตัวไม่สามารถอยู่แถวเดียวกันได้ จึงวางควีนหนึ่งตัวต่อแถวและเลือกเฉพาะคอลัมน์เท่านั้น วิธีนี้ลดพื้นที่ค้นหาได้อย่างมาก
ตรวจสอบความขัดแย้งสามแบบ
ก่อนวาง ให้ปฏิเสธคอลัมน์หรือเส้นทแยงมุมที่ถูกใช้ไปแล้ว ติดตามคอลัมน์ที่ใช้แล้วและเส้นทแยงมุมทั้งสองทิศทางในเซต
if c in cols or r-c in d1 or r+c in d2:
continueย้อนกลับเมื่อถึงทางตัน
หากไม่มีคอลัมน์ใดใช้ได้ในแถวหนึ่ง กิ่งนั้นจะล้มเหลว ให้ย้อนกลับ นำควีนตัวสุดท้ายออก แล้วลองทางเลือกถัดไป
รูปแบบร่วม
permutation และปัญหา N-ควีนส์มีรูปแบบเดียวกัน ได้แก่ เลือก เรียกซ้ำ ยกเลิก เมื่อมองเห็นรูปแบบนี้แล้ว โจทย์การวางส่วนใหญ่ก็ใช้แม่แบบเดียวกันได้
ตรวจสอบความเข้าใจ
เหตุใดปัญหา N-ควีนส์จึงวางควีนเพียงหนึ่งตัวต่อแถว
สรุปทบทวน: เลือก เรียกซ้ำ ยกเลิก
ได้สร้าง permutations ด้วยการวางสิ่งของที่ยังไม่ได้ใช้ และเรียนรู้ว่าปัญหา N-ควีนส์ใช้รูปแบบเลือก-เรียกซ้ำ-ยกเลิกแบบเดียวกัน พร้อมตรวจสอบความขัดแย้ง 🎯
คำถามที่พบบ่อย
บทเรียน “การเรียงสับเปลี่ยนและแนวคิด N-Queens” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การเรียงสับเปลี่ยนและแนวคิด N-Queens” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การเรียงสับเปลี่ยนและแนวคิด N-Queens”
วางสมาชิกและย้อนกลับเมื่อเกิดความขัดแย้ง คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “การเรียงสับเปลี่ยนและแนวคิด N-Queens” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- คิดแบบเวียนเกิด: ฐานและการเรียกซ้ำ
- สร้างเซตย่อยทั้งหมด
- การเรียงสับเปลี่ยนและแนวคิด N-Queens
- ตัดกิ่งเพื่อให้อยู่รอดในขีดจำกัดเวลา