การแก้ไขปัญหาจํานวนคําใบ้ที่น้อยที่สุดของซูโดกุขนาด 9 x 9 ที่ทําให้มีผลเฉลยแบบเดียวโดยหลักการของแม็คไกวร์และทฤษฎีกราฟ
- ชื่อนักเรียนผู้จัดทำโครงงานวิทยาศาสตร์
โสภณวิชญ์ ปิติวรยุทธ, ณัช กอตระกูลสิน, ปุรัณ ประเสริฐไทย
- อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์
มนสิการ จันทร์สร้าง
- โรงเรียนที่กำกับดูแลโครงงานวิทยาศาสตร์
- ปีที่จัดทำโครงงานวิทยาศาสตร์
บทคัดย่อโครงงานวิทยาศาสตร์
Sudoku เป็นหนึ่งในเกมปริศนาที่ได้รับความนิยมทั่วโลกและได้มีการจัดการแข่งขันมากมาย ลักษณะของ Sudoku ที่นิยมจะเป็นตารางขนาด 9 x 9 และแบ่งเป็นตารางย่อยขนาด 3 x 3 โดยเราต้องเติมตัวเลข 1-9 ลงในแต่ละช่องให้ตัวเลขในแต่ละแถว แต่ละหลักและแต่ละตารางย่อยไม่ซ้ำกัน
โดยปกติแล้ว ตารางจะถูกให้มาพร้อมกับตัวเลขจำนวนหนึ่งเพื่อใช้เป็นหลักในการเติมจำนวนช่องต่อ ๆ ไปจนครบตาราง ตัวเลขเริ่มต้นที่มาพร้อมกับตารางนั้น ถูกเรียกว่า clue หรือคำใบ้ ซึ่ง Sudoku หลาย ๆ ครั้งมีผลเฉลยหลายรูปแบบ ซึ่งเป็นผลมาจากตำแหน่งและจำนวนของ clue โดยปัญหาเกี่ยวกับ Sudoku หนึ่งที่น่าสนใจคือ ปัญหาการหาจำนวนคำใบ้ที่น้อยที่สุดที่ทำให้ Sudoku มีผลเฉลยรูปแบบเดียว โดยสำหรับตารางขนาด 4 x 4 และ 9 x 9 คำตอบคือ 4 และ 17 ตามลำดับ
โดยปัญหาจำนวนคำใบ้ที่น้อยสุดที่ทำให้ Sudoku มีผลเฉลยรูปแบบเดียวในตารางขนาด n x n นั้นมีหลายวิธีที่เป็นไปได้ ซึ่งวิธีการของ Gary McGuire ก็เป็นหนึ่งในวิธีเหล่านั้นซึ่งทางผู้ศึกษาเห็นว่าปัญหาทางซูโดกุนั้นสามารถนำหลักทฤษฎีดังกล่าวไปสู่การแก้ไขได้ ดังนั้นทางผู้ศึกษาจึงสนใจที่จะศึกษาการประยุกต์หลักวิธีของ Gary McGuire มาใช้ร่วมกับทฤษฎีกราฟซึ่งอาจก่อให้เกิดวิธีหาคำตอบอีกรูปแบบหนึ่ง ซึ่งมีประสิทธิภาพมากขึ้น