การหาจำนวนและวิธีการวางบิชอปที่มากที่สุดที่วางได้บนกระดานขนาดn×nโดยที่บิชอปแต่ละตัวไม่สามารถกินกันได้

ชื่อนักเรียนผู้จัดทำโครงงานวิทยาศาสตร์

สุพัฒนา การรัตน์, ธนพร บุตรศรีรักษ์

อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์

ศันสนีย์ บุญสนิท

โรงเรียนที่กำกับดูแลโครงงานวิทยาศาสตร์

โรงเรียนวิทยาศาสตร์จุฬาภรณราชวิทยาลัย มุกดาหาร

ปีที่จัดทำโครงงานวิทยาศาสตร์

พ.ศ. 2562

บทคัดย่อโครงงานวิทยาศาสตร์

หมากรุกเป็นเกมกระดานที่จำลองมาจากการสงครามมากมายทุกยุคทุกสมัยในโลก หมากรุกเป็นเกมที่ต้องใช้ปัญญา ความคิด และปฏิภาณไหวพริบในการชิงความได้เปรียบในการแข่งขันเพื่อเอาชนะคู่ต่อสู้คู่ต่อสู้ นอกจากนี้แล้วความสนุกและความตื่นเต้นของเกมการแข่งขันหมากรุกยังอยู่ที่การมีทางเลือกที่เป็นไปได้ซึ่งก่อให้เกิดจำนวนวิธีในการเล่นอย่างมากมาย หลากหลาย ตัวอย่างเช่น หากทั้งสองฝ่ายเริ่มเดินคนละสองตาจะมีวิธีที่เป็นไปได้มากกว่า 7,200 วิธี ถ้าเดินคนละสีตาจะมีวิธีที่เป็นไปได้มากกว่า 288 พันล้านวิธี ถ้าเดินคนละสิบตาจะมีวิธีที่เป็นไปได้มากกว่า 169 พันล้านล้านล้านล้านวิธี เนื่องจากเกมหมากรุกนั้นไม่สามารถเล่นคนเดียวได้จึงทำให้เกิดปัญหาลับสมองและคำถามท้าทายที่เกี่ยวกับหมากรุกมากมาย เช่น ปัญหาม้าเดินทั่วกระดาน (Knight’s tour) ปัญหาการวางเรือ ปัญหาการวางควีน N ตัว (N-queen problem) ซึ่งแต่ละปัญหาก็ได้มีผู้ที่สนใจนำไปศึกษาจนสามารถนำความรู้ไปใช้ให้เกิดประโยชน์ในด้านต่างๆแล้วทั้งสิ้น เช่น ปัญหาการวางควีน N ตัว (N-queen problem) คือการวางควีนบนกระดานหมากรุก ขนาด 8×8 ได้มากที่สุดกี่ตัวโดยให้ควีนแต่ละตัวไม่สามารถกินกันได้เลย และจะมีวิธีวางได้กี่วิธีอย่างไรบ้าง ซึ่งผู้ที่ถามและสนใจปัญหานี้เป็นครั้งแรกคือนาย Max Bezzel นักเล่นหมากรุกชาวเยอรมัน เมื่อประมาณปี พ.ศ. 2391 ซึ่งปัญหาการวางควีนที่เกิดขึ้นมานานกว่า 160 ปีนั้น ได้มีการนำมาใช้ในยุคที่มีการนำมาใช้ในยุคปัจจุบันที่เทคโนโลยีและวิทยาการคอมพิวเตอร์มีความเจริญก้าวหน้า เช่น parallel memory storage screen ใน parallel computing ที่ใช้กันในสถาบันสถาบันเซติ VLSI testing ที่มีความจำเป็นสำหรับขั้นตอนการผลิตชิปคอมพิวเตอร์ และ การควบคุมจราจร เป็นต้น จากที่กล่าวมาข้างต้นจะเห็นได้ว่าปัญหาบนกระดานหมากรุกเป็นปัญหาที่ผู้คนให้ความสนใจ รู้จักกันอย่างกว้างขวางและสามารถนำไปใช้ประโยชน์ได้จริง นอกจากนี้ปัญหาหมากรุกยังเป็นปํญหาที่สามารถปรับเปลี่ยน หรือเพิ่มองค์ประกอบต่างๆ เพื่อสร้างปัญหาใหม่ได้อย่างมากมาย

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