15-Puzzle

สิ่งที่ต้องการ

หวังว่านักเรียนคงเคยเล่นเกม 15 puzzle กันมาก่อน  เป็นแผ่นพลาสติกรูปสี่เหลี่ยมจัตุรัส ภายในประกอบด้วยแผ่นพลาสติกย่อยเล็กๆ (สี่เหลี่ยมจัตุรัสเหมือนกัน) จำนวน 15 แผ่น (แต่ละแผ่นมีตัวเลขกำกับตั้งแต่ 1 ถึง 15) วางเรียงกันเป็นตาราง 4x4 โดยมีช่องว่างหนึ่งอยู่ภายใน สามารถเลื่อนแผ่นต่าง ๆ ไปมาได้ในแนวนอนแนวตั้ง

จุดประสงค์ของเกมก็คือ ให้เลื่อนแผ่นสี่เหลี่ยมภายในไปมา เพื่อให้ได้แผ่นสี่เหลี่ยมเหล่านี้ เรียงเป็นระเบียบไล่ไปเรื่อย ๆ 1 ถึง 15 (จากซ้ายไปขวา จากบนลงล่าง) ดังตัวอย่างที่แสดงข้างล่างนี้ เริ่มจากรูปทางซ้าย ให้หาวิธีเลื่อนจนได้ดังรูปขวา

                  

ประเด็นปัญหาที่เราจะมาสนใจกันในปฏิบัตินี้ก็คือ จากแผ่นเริ่มต้นที่ให้มา (ซึ่งมีรูปแบบที่เป็นไปได้ทั้งสิ้น 15 ! = 1,307,674,368,000 แบบ) มันไม่แน่เสมอไปว่าจะมีวิธีเลื่อนกลับให้เป็นระเบียบตามที่ต้องการได้ ตัวอย่างเช่น ถ้าให้จุดเริ่มต้นเป็นดังรูปข้างล่างนี้ จะไม่มีทางเลื่อนกลับไปเป็นสิ่งที่ต้องการได้ (ให้สังเกตว่า มันต่างกับจุดหมายที่ต้องการ เพียงแค่สลับ 14 กับ 15 เท่านั้น) 

จงเขียน  public static boolean solvable15Puzzle( int [][] b ) ในคลาส FifteenPuzzle ซึ่งรับตาราง b เป็น array สองมิติ (ขนาด 4x4) โดยที่ b[i][j] เก็บหมายเลขของแผ่นสี่เหลี่ยมที่อยู่บนแถวแนวนอนที่ i และแถวแนวตั้งที่ j  (ช่องว่างจะแทนด้วยหมายเลข 0) ถ้า b เป็นตารางที่ไม่มีทางหาวิธีเลื่อนกลับได้ ให้คืน false แต่ถ้ามีหนทางเลื่อนกลับได้ให้คืน true

วิธีตรวจสอบ

เราสามารถตรวจสอบว่าจะมีวิธีเลื่อนแผ่นสี่เหลี่ยมต่าง ๆ กลับไปสู่สิ่งที่ต้องการได้หรือไม่ โดยไม่ต้องลองเลื่อนดูจริง ๆ  ดังนี้

• ขอย้ำอีกครั้งว่า แผ่นสี่เหลี่ยมเล็ก แต่ละแผ่นมีหมายเลขกำกับ คือ 1 ถึง 15
• นำแผ่นสี่เหลี่ยมที่เรียงเป็นตาราง มาวางเรียงกันเป็นแนวยาว ไล่จากซ้ายไปขวาบนลงล่าง ตัวอย่างเช่น

เรียงเป็นแนวได้ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 13, 14, 11

ข้อสังเกต เราจะไม่นำข่องว่าง มาวางเรียงในแถว

• พิจารณาตัวเลขต่างๆ เป็นคู่ ๆ (ตัวเลขมี 15 ตัว จึงมีทั้งหมด (15x14)/2 คู่) แล้วนับว่า มีตัวเลขในรายการอยู่กี่คู่ที่ตัวทางซ้ายมากกว่าตัวทางขวา (เรียกว่าเป็นการกลับลำดับ) เช่นจากตัวอย่างข้างบนนี้ คู่ที่กลับลำดับคือ (12, 11), (15, 13), (15, 14), (15, 11), (13, 11) และ (14, 11) ซึ่งมีอยู่ 6 คู่ 

  กำหนดให้ L คือจำนวนการกลับลำดับที่นับได้ในขั้นตอนนี้

• คราวนี้พิจารณาว่าช่องว่างอยู่ในแถวแนวนอนที่เท่าใด (แถวบนสุดคือแถวที่ 1 ไล่ลงมา) เช่น ตารางตัวอย่างข้างบนนี้มีช่องว่างอยู่แถวที่ 4

  กำหนดให้ B คือหมายเลขแถวที่ช่องว่างอยู่

• ถ้า L+B เป็นจำนวนคู่ แสดงว่าเราจะสามารถเลื่อนแผ่นสี่เหลี่ยมต่างๆ ไปสู่เป้าหมายได้  แต่ถ้า L+B เป็นจำนวนคี่ หมายความว่า ไม่มีทางจะเลื่อนได้สำเร็จ

จะขอไม่พิสูจน์ให้เห็นจริงว่าวิธีตรวจสอบข้างบนนี้ใช้ได้ผลจริงได้อย่างไร

การตรวจให้คะแนน

• กด F6 ระบบจะตรวจให้อัตโนมัติ โดยทดสอบกรณีสุ่ม ๆ 10 กรณี

คะแนนเต็ม 10 คะแนน

เวลาปฏิบัติการ : 60 นาที

แหล่งที่มา : http://www.cut-the-knot.com/pythagoras/fifteen.html

ปฏิบัติการนี้ใช้ควบคู่กับซอฟต์แวร์ปฏิบัติการจาวา JLab 
(http://www.cp.eng.chula.ac.th/~somchai/JLab)