2110101 : Lab7 - Array (15-Puzzle)

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

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

                  

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

จงเขียนเมท็อด  public static boolean isBoardLegal( int [][] b ) ในคลาส Lab7.java ซึ่งรับตาราง 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 คู่) แล้วนับว่า มีตัวเลขในรายการอยู่กี่คู่ที่ตัวทางซ้ายมากกว่าตัวทางขวา (เรียกว่าเป็นการกลับลำดับ) เช่นจากตัวอย่างข้างบนนี้ คู่ที่กลับลำดับคือ (12, 11), (15, 13), (15, 14), (15, 11), (13, 11) และ (14, 11) ซึ่งมีอยู่ 6 คู่ 

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

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

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

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

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

http://www.cut-the-knot.com/pythagoras/fifteen.html

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

• เขียนโปรแกรม  10 คะแนน  (ระบบตรวจให้อัตโนมัติ โดยทดสอบกรณีสุ่มๆ 10 กรณีๆ ละ 1 คะแนน)

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

ปฏิบัติการนี้ใช้ควบคู่กับซอฟต์แวร์ปฏิบัติการจาวา JLab 
© 2002 สมชาย ประสิทธิ์จูตระกูล