ปัญหาควีนแปดตัว

จากวิกิพีเดีย สารานุกรมเสรี

ปัญหาควีนแปดตัว (eight queens puzzle) คือปัญหาการวางควีน ลงบนกระดานหมากรุกขนาด 8×8 โดยไม่ให้มีควีนตัวใดกินกันได้ (ควีนทุกตัวเป็นศัตรูกัน) นั่นคือ จะต้องไม่มีควีนตัวใดที่อยู่แถวเดียวกัน หรือหลักเดียวกัน หรือแนวทแยงเดียวกัน. ปัญหาควีน n ตัว คือการวางควีน n ตัว ลงในกระดานหมากรุกขนาด n×n

[แก้] ประวัติศาสตร์

ปัญหานี้ถูกตั้งขึ้นใน ค.ศ. 1848 โดยนักเล่นหมากรุกชื่อ Max Bezzel และหลายปีต่อมา นักคณิตศาสตร์หลายคนรวมทั้ง เกาส์ ได้ศึกษาปัญหานี้. ค.ศ. 1874 S. Gunther ได้เสนอวิธีหาคำตอบโดยใช้ดีเทอร์มิแนนต์

[แก้] จำนวนคำตอบทั้งหมด

ปัญหาควีนแปดตัว มีคำตอบที่แตกต่างกันทั้งหมด 92 คำตอบ. แต่ถ้าเราไม่นับคำตอบที่เกิดจากการหมุน หรือสะท้อนของคำตอบก่อนๆ มันจะมีเพียง 12 คำตอบเท่านั้น. ตารางข้างล่างนี้คือจำนวนคำตอบของปัญหาควีน n ตัว ทั้งแบบนับทั้งหมด และแบบไม่นับซ้ำ

n:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
ไม่นับซ้ำ:	1	0	0	1	2	1	6	12	46	92	341	1,787	9,233	45,752	285,053
นับทั้งหมด:	1	0	0	2	10	4	40	92	352	724	2,680	14,200	73,712	365,596	2,279,184

สังเกตว่า จำนวนคำตอบของควีน 6 ตัว น้อยกว่าคำตอบของควีน 5 ตัว