คณิตศาสตร์ของเกมเลื่อนแผ่นภาพ ทำไมบางกระดานแก้ไม่ได้
ปริศนาเลื่อนแผ่นภาพเป็นหนึ่งในของเล่นคลาสสิกที่สุดในโลก มันโด่งดังขึ้นในช่วงปลายศตวรรษที่ 19 ในชื่อ “ปริศนา 15” (15 Puzzle) ซึ่งมีแผ่นตัวเลข 15 แผ่นในกรอบ 4x4 และช่องว่างหนึ่งช่อง ตอนนั้นมีการท้าทายว่าใครเรียงได้เมื่อตัวเลข 14 กับ 15 สลับที่กันอยู่จะได้รางวัล คนจำนวนมากพยายามกันอย่างบ้าคลั่ง แต่ไม่มีใครทำได้ เพราะ มันเป็นไปไม่ได้ทางคณิตศาสตร์
ความลับอยู่ที่ “การกลับลำดับ”
ลองเขียนเลขบนแผ่นทั้งหมดเรียงต่อกันจากซ้ายไปขวา บนลงล่าง (ไม่นับช่องว่าง) แล้วนับว่ามีกี่คู่ที่ “เลขมากมาก่อนเลขน้อย” จำนวนคู่ที่กลับลำดับนี้เรียกว่า inversion
- ในกระดานที่เรียงสมบูรณ์ จำนวน inversion เท่ากับ 0
- ถ้าสลับแค่ 14 กับ 15 จะมี inversion 1 คู่
การเลื่อนแต่ละครั้งเปลี่ยนอะไร
- เลื่อนแนวนอน (ซ้าย-ขวา) ลำดับของตัวเลขไม่เปลี่ยนเลย จำนวน inversion จึงเท่าเดิม
- เลื่อนแนวตั้ง (ขึ้น-ลง) แผ่นหนึ่งกระโดดข้ามแผ่นอื่นไปหลายตำแหน่ง ทำให้จำนวน inversion เปลี่ยน
สำหรับกระดานที่ความกว้างเป็นเลขคี่ (เช่น 3x3) การเลื่อนแนวตั้งจะข้ามแผ่นไป 2 แผ่นเสมอ จำนวน inversion จึงเปลี่ยนทีละเลขคู่ ผลคือ ความเป็นคู่คี่ของ inversion ไม่เคยเปลี่ยน กระดาน 3x3 ที่มี inversion เป็นเลขคี่จึงไม่มีทางกลับไปเป็น 0 ได้
สำหรับกระดานกว้างเป็นเลขคู่ (เช่น 4x4) ต้องนับแถวของช่องว่างร่วมด้วย แต่หลักการเดียวกัน: ผลรวมบางอย่างไม่เปลี่ยนความเป็นคู่คี่ไม่ว่าจะเลื่อนอย่างไร ปริศนา 14-15 ในตำนานจึงแก้ไม่ได้ตลอดกาล
ครึ่งหนึ่งของทุกการจัดเรียงแก้ไม่ได้
ผลที่น่าทึ่งคือ ถ้าคุณแกะแผ่นออกมาแล้วใส่กลับแบบสุ่ม จะมีโอกาสครึ่งต่อครึ่งที่กระดานนั้นแก้ไม่ได้เลย
วีโดปารับประกันอย่างไร
ด่านเลื่อนแผ่นภาพในวีโดปาไม่ได้วางแผ่นแบบสุ่ม แต่เริ่มจากภาพที่สมบูรณ์ แล้ว เลื่อนจริงตามกติกาทีละครั้ง เพื่อสับภาพ เหมือนคนเอามือเลื่อน วิธีนี้รับประกันว่ากระดานทุกกระดานกลับไปเป็นภาพสมบูรณ์ได้เสมอ นอกจากนี้ Solver ของเรายังตรวจความเป็นคู่คี่ซ้ำอีกรอบ และคำนวณจำนวนครั้งน้อยที่สุดที่ต้องเลื่อน เพื่อให้ความยากเหมาะกับแต่ละชั้นของคฤหาสน์
ใช้ความรู้นี้ในเกมอย่างไร
คุณไม่ต้องนับ inversion ระหว่างเล่น แต่การรู้ว่า “ทุกกระดานแก้ได้แน่นอน” ช่วยให้มั่นใจที่จะใช้กลยุทธ์แบบมีระบบ คือเรียงแถวบนก่อน แล้วคอลัมน์ซ้าย จนเหลือกระดานเล็กลงเรื่อยๆ อ่านขั้นตอนละเอียดได้ในคู่มือเลื่อนแผ่นภาพ