ปัญหาการเติมช่องว่างสี่เหลี่ยมขนาดต่าง ๆ ด้วยบล็อกเตตริสต่างชนิดเมื่ออยู่ติดกัน

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

ธนภัทร คลังนาค

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

กีรติ ศรีอมร, อมรศรี อมรวัชรพงศ์

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

โรงเรียนมหิดลวิทยานุสรณ์

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

พ.ศ. 2564

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

โครงงานนี้มีจุดเริ่มต้นความสนใจมาจาก Four Color Theorem โดยผู้จัดทำโครงงานได้สังเกตเห็นว่าเกมเตตริส มีลักษณะคล้ายกับ Four Color Theorem หากแต่มีการเปลี่ยนจาก 4 สี เป็นบล็อก 7 รูปแบบ และบล็อกแต่ละตัวมีขนาดที่ชัดเจน และยังสามารถกำหนดตัวแปรเพิ่มอีกหนึ่งตัวแปรได้ คือขนาดของตารางสี่เหลี่ยมผืนผ้าที่กำหนดความกว้างและความยาว

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

ผลลัพธ์ที่ได้นั้น พบว่า กรณีที่เติมเต็มไม่ได้ คือกรณีที่ผลคูณของ m และ n หารด้วย 4 ไม่ลงตัว กรณีที่ไม่มีวิธีเติมเต็มแบบไม่มีบล็อกชนิดเดียวกันติดกัน คือ (1,8), (2,4), (2,8), (2,10) และส่วนกลับของคู่อันดับข้างต้นทั้งหมด กรณีที่ไม่มีบล็อกมูลฐาน คือ (4,4) กรณีที่ไม่มีบล็อกมูลฐานอนันต์ คือ (1,4), (4,1), และ (2,2) และในกรณีที่เหลือทั้งหมด พบวิธีที่สามารถสร้างบล็อกมูลฐานอนันต์ได้อย่างน้อยหนึ่งวิธี จึงได้ข้อคาดการณ์ว่า ในกรณีที่ m และ n มีค่ามาก ๆ มีแนวโน้มว่าจะสามารถเติมเต็มตารางนั้น ๆ ได้โดยที่เป็นลักษณะของบล็อกมูลฐานอนันต์ นั่นคือ ไม่มีบล็อกชนิดเดียวกันติดกัน ไม่สามารถแบ่งออกเป็นบล็อกย่อยได้ และเมื่อต่อทับกันขึ้นไปเรื่อย ๆ ยังไม่มีบล็อกชนิดเดียวกันติดกัน

โครงงานนี้สามารถพัฒนาได้เพิ่มเติมในอนาคต โดยการลดทอนบล็อกพื้นฐานออกไป และทำซ้ำในลักษณะเดียวกัน เพื่อหากรณีที่ดีที่สุดที่เป็นไปได้จากคู่อันดับ (m,n) แต่ละคู่

ผู้จัดทำโครงงานมีความมุ่งหวังในการนำงานวิจัยนี้ไปเป็นความรู้พื้นฐานสำหรับงานวิจัยที่ต้องการนำไปพัฒนาต่อในอนาคต หรืออาจนำไปประยุกต์ใช้ได้ในชีวิตจริง เช่น การจัดเรียงส่งของให้เกิดประสิทธิภาพมากที่สุด เป็นต้น