และแล้วก็มาถึงตอนต่อไปของซีรี่ส์ (ว่าไปนั่น ฮร่าๆ)   ไม่พล่ามมากละกัน มีให้พล่ามอีกเยอะในเนื้อหา  เริ่มกันโลด

แง่มม  การทำ 8puzzle นี่เนื่องจากหาข้อมูลค่อนข้างยาก คือจริงๆมันก็มีน่ะแหละ  แต่หาไอที่มันอธิบายแบบรู้เรื่องไม่ค่อยจะมีเอาซะเลย   จริงๆคือหาไม่เจอเลยแหละ -0-  ก็เลยจะอธิบายหลักการไว้ซะหน่อยก่อนที่จะเข้าไปส่วนของการ coding ละกันเนอะ  จะได้ไม่งง  

8PUZZLE :  What is?

     ตอนแรกที่ไอโจบอกจารย์ให้ทำ array 2 มิติแล้วให้มัน gen กันจนจบ  ก็มานั่งนึก  อะไรวะ array 2 มิติแล้วให้ gen จนจบแมวน้ำว้อท  จนมันบอกว่าทำไอเกมที่มันเลื่อนๆอะ เคยเล่นกันมะที่มีจะมีช่องอยู่ 9 ช่องแล้วมีช่องว่างอยู่ช่องนึง แล้วเวลาเลื่อนก็เลื่อนได้แค่ครั้งละช่องอะนะ  ถ้ายังนึกรูปไม่ออกก็ดูรูปด้านบนประกอบละกัน

 

8PUZZLE : tree traversal

     เมื่อรู้ว่ามันคืออะไรแล้ว  แล้วมันเกี่ยวแม้วอะไรกับ tree traversal ล่ะ(วะเนี่ย)   แน่นอนว่ามันต้องเกี่ยวไม่งั้นอาจารย์คงไม่สั่ง ฮ่าๆๆ  สรุปกันแบบกำปั้นทุบดินคือเราสามารถใช้ tree traversal ในการหาคำตอบในการเลื่อนไอ้เจ้าเกม 8puzzle นี่ได้ยังไงล่ะคร้าบ

 

8PUZZLE : HOW?

     โอเคมันใช้แก้ปัญหานี้ได้ซินะ  แล้วจะเอา tree traversal เข้ามาเกี่ยวยังไงล่ะ  ก็นั่นน่ะซิ (เฮ้ย)  อ่าเริ่มยังไงดี  จริงๆแล้วการแก้ 8puzzle มันก็ทำได้หลายทางล่ะนะ  ซึ่งจริงๆการแก้ที่ดีที่สุดคือการใช้ A* approach (อ่านว่า เอ สตาร์)  แต่เนื่องจากเราโดนสั่งให้ใช้ tree traversal ในการแก้  การเป็นโปรแกรมเมอร์ที่ดีคือการทำตามคำสั่ง ฮร่าๆ เพราะฉะนั้นเราก็จะใช้ tree traversal กันล่ะเน้อ  อธิบายหลักการคร่าวๆคือเราจะทำการสร้าง tree ที่เกิดจากการสลับที่ของตาราง 8puzzle แล้วหา node ที่เป็น goal state ที่ตั้งไว้  แต่เนื่องจากการจะสร้าง tree ที่เกิดจากการสลับที่ของ 8puzzle จะต้องใช้เนื้อที่ถึง 9! = 362880 node!! แม่เจ้า จะใหญ่ไปถึงไหน  เราเลยต้องมีการพลิกกันเล็กน้อย  ก็คือทำการสร้างไปเช็คไปนั่นเอง  ฮร่าๆๆ  ซึ่งการสร้าง tree นี้จะทำด้วยกันสองแบบก็คือแบบ Depth-first กะแบบ Breadth-first  โดยเหตุผลที่ไม่ทำ inorder และ postorder คือมันให้ผลคล้ายกันกับแบบ Depth-first ล่ะนะ  แต่!! ที่จะทำให้ดูต่อไปนี้จะทำเฉพาะ Depth-first search อย่างเดียว  ส่วน Breadth-first ไปทำต่อกันเอาเอง (จริงๆคือเพิ่งเสร็จแค่อย่างเดียวล่ะนะ ฮ่าๆๆ บวกกับอยากให้ลองเอาไปต่อยอดกันเอง)  ต่อไปมาดูการออกแบบ tree กันต่อ

 

8PUZZLE : Tree Model

     การออกแบบ Tree "ตามหลักการแล้ว" จะ store array 2 มิติไว้ในแต่ละ node แล้วจึงค่อยแตกไปเรื่อยๆ  ตามรูปแบบที่กำหนด (คือ depth-first หรือ breadth-first)  แต่เนื่องจากพอลองใช้ DefaultMutableTreeNode ใส่ array ลงไปแล้วตอนรับค่ากลับมันแปลงกลับไม่ด้ายย T^T  ใครทำได้ก็สอนกันมั่ง  ก็เลยจำใจและจำยอมต้องเก็บค่าเป็น String แล้วค่อยมา split ใส่ array 2 มิติตอนจะคำนวณ node ใหม่ อะใช่ๆดูรูปหน่อยละกัน

     ก็ไปดูรูปใหญ่กันละกันเนอะ อันนี้เป็นรูป Depth-first search  อธิบายหน่อย ก็คือตอนเริ่ม (initial state) เราก็จะมีช่องว่างอยู่ช่องนึงใช่มะ (มันก็มีช่องนึงตลอดแหละ) การจะสร้าง tree เราจะยึดช่องว่างไว้เป็นหลัก ต่อไปเรียกว่าช่อง x ละกัน  โดยช่อง x จะมีทางที่เป็นไปได้ที่จะเดินอยู่ 2-4 ทาง เช่นในรูป initial ก็จะเดินไปล่างหรือไปทางขวาก็ได้  เราก็จะแตกโดยเป็นเช่นนี้ไปเรื่อยๆ  อ้อแต่ว่าช่องที่เราเพิ่งเดินมาก็ไม่ต้องแตกไปละนะ เปลือง memory โดยเปล่าประโยชน์ อาจจะยังงงๆ อยู่นิดนึง จะทำตัวอย่างการแตกให้ดูนิสนึงละกัน

2	8	3
1	6	4
7	x	5

เลื่อน x ไปด้านซ้าย

||
||
\/

2	8	3
1	6	4
x	7	5

||
||
\/

2	8	3
x	6	4
1	7	5

 

     อะจากรูปจะเห็นว่าจาก figure 1 --> figure 2 ช่อง x จะเลื่อนไปทางซ้ายโดยที่จริงๆยังมีอีกสองทางให้เลื่อนคือบนกับทางขวา  แต่เราจะทำ Depth-first ฉะนั้นเราจะลงมาเรื่อยๆก่อนจาก figure 2 --> figure 3 จะเห็นว่าช่อง x เลื่อนไปด้านบน  ซึ่งจริงๆ figure 2 ก็สามารถเลื่อนไปทางขวาได้  แต่เนื่องจากถ้าเราไปทางขวาก็จะกลับไปเป็น figure 1 อีก ดังนั้นเราจึงมีสิทธิ์เดินทางขวาแค่ทางเดียว  จาก figure 3 เราก็จะแตกต่อไปอย่างนี้เรื่อยๆจนสุดปลายของแต่ละแบบ แล้วจึงขึ้นมาทำ node ด้านบนแล้วก็เลื่อนไปเรื่อยๆ (คงนึกออกนะ)  จนเมื่อเจอกับ goal state ซึ่งในที่นี้ก็คือ 

goal state

1	2	3
4	5	6
7	8	x

     ก็จะเสร็จการทำงานแล้วทำการหาเส้นทางมายัง node ที่เป็น goal state แล้วจึงทำตามนั้นล่ะเน้อ  ก็จบละสำหรับหลักการของการทำ 8puzzle ถ้ามีอะไรสงสัยก็ถามละกัน โฮ่ๆ 

 

8PUZZLE : Coding

     ในที่สุดก็มาถึงส่วนที่รอคอย ก็คือส่วนของ Code นั่นเองงงงง  ถึงจะบอกว่าให้เอาอันเก่าไปแก้ก็เถอะ  การ traverse มันไม่เหมือนกันอ้ะ  ก็เลยจำเป็นต้องเขียนใหม่  ก็คือเอาหลักการเดิมน่ะแหละแต่มันต้องเขียนแบบใหม่อะนะ  ก็มาดูกันเลยละกัน

JTREE 

     อย่างที่บอกไปตอนต้นว่าถ้าใส่ array 2 มิติลงไปตอน retrieve ค่าออกมาข้าพเจ้าแปลงกลับมาเป็น array ไม่ได้ -*- เลยต้องใช้การพลิกแพลงเล็กน้อยโดยใส่ String ลงไปใน node นั้นแล้วเวลาจะคำนวณจึงค่อยมาแปลงเป็น array แทนโดยใช้ objectToArray(String) และ arrayToObject(int[][]) 

objectToArray(String) และ arrayToObject(int[][])

     หลักการสองตัวนี้เหมือนกันเด้ะๆ objectToArray จะรับค่า string มาวนลูปแล้วใส่ลงใน array 2 มิติที่เตรียมไว้เพื่อเอาไปคำนวณ  ส่วน arrayToObject() และรับค่า array 2 มิติ มาวนลูปแล้วเอาไปใส่ใน string เพื่อแปลงเป็น Object แล้วก็เอาไปใส่ใน node 

Pick initial State

     ส่วนนี้จริงๆก็คือ actionPerformed นั่นแหละ ฮ่าๆๆ โดยจะมีปุ่มให้ user คลิกอยู่ 9 ปุ่มโดยแต่ละปุ่มเมื่อถูกกดก็จะเพิ่มค่าทีละหนึ่งจนครบ 8 ซึ่งจะเช็คโดย checkFull(int) ก็จะทำการ enable ปุ่ม btPre และ btLevel ซึ่งเป็นปุ่มสำหรับเริ่มการคำนวณนั่นเอง

begin() เริ่มได้!!

     เมื่อเลือก initial state และกดปุ่มเริ่มแล้วก็จะเรียกคำสั่ง begin(void) โดยจะวนรับ label ของปุ่มที่ user เลือกไว้แล้วเอาไปใส่ในตัวแปร initial จากนั้นก็จะนำไปสร้างเป็น root node  และเริ่มการคำนวณเรียก  generateChildNodes(DefaultMutableTreeNode,int,Vector)

generateChildNodes(DefaultMutableTreeNode,int,Vector)

     -  method นี้จะทำการคำนวณเพื่อหาค่าของ node ถัดไปเพื่อนำไปใส่ใน tree นั่นเอง  โดยขั้นแรกจะทำการเช็ค Node ที่รับเข้ามาว่าตรงกับ goalState  แล้วรึยัง ถ้าเป็นแล้วก็จะเซ็ตค่า found เป็น true แล้วหา path จาก root มายัง node นี้เพื่อตัดสินใจในการเดิน ด้วย getPath()

     -   แต่ถ้าเกิดยังไม่ใช่ ก็จะทำการหาค่าของ array 2 มิติโดยรับมาจาก TreeNode แล้วมาแปลงเป็น array โดยใช้ objectToArray(String) อย่างที่บอกไว้ตอนต้น  

     -  จากนั้นก็จะทำการหาตำแหน่งช่องว่างซึ่งกำหนดไว้เป็น 0 โดยใช้ getZeroPosition(int[][])

     -  เมื่อได้ตำแหน่งช่องว่างมาแล้วก็จะคำนวณหาการเดินที่เป็นไปได้โดยเรียก getPossibleMove(int[][],int[],Vector)

     -  เมื่อคำนวณหาช่องการเดินที่เป็นไปได้ก็จะเริ่มเดิน (แหงล่ะ) โดยการวน possibleMove ที่เก็บไว้แล้วทำการสร้าง node ใหม่โดยจะทำการเดินด้วย makeTileSwap(int[][],int,int,int,int)  แล้วทำการแปลงเป็น Object เพื่อเอาไปใส่ใน node ด้วย arrayToObject(int[][]) จากนั้นก็ makeTileSwap() เพื่อให้กลับเป็นเหมือนเดิม เนื่องจาก array ของ integer นั้นเป็นการส่งค่าแบบ pass by ref (ทำเอาเอ๋อไปพักนึงว่าทำไมค่ามันเปลี่ยนไปด้วยฟะ)

     -  เมื่อสร้าง node ใหม่สำเร็จก็จะบันทึกการเดินไว้ใน Vector แล้วจึงทำ recursive ของ method generateChildNode() ไปจนกว่าจะพบ

     -  แต่เนื่องจากการใช้ Depth-first search ถ้าหาลงไปเรื่อยๆอาจทำให้เกิด memory overflow ได้เพราะไม่เจอซักที  ก็เลยจะมีการกำนหด depth ที่ลงไปได้ลึกที่สุด  โดยหากเกินกว่านั้นให้ทิ้ง node นั้นไปแล้วขึ้นมาทำ parent node ใหม่ต่อ

getZeroPosition(int[][])

     ชื่อก็บอกอยู่แล้วว่าเป็นการหาตำแหน่งของช่องที่เป็นช่องว่าง  โดยวนลูปเพื่อหาค่า 0 แล้ว return ตำแหน่งนั้นกลับมานั่นเอง

getPossibleMove(int[][],int[],Vector)

    method นี้จะรับค่า zeroPosition มาแล้วทำการเช็คด้วย switch และ if เพื่อกำหนดการเดินที่เป็นไปได้  แต่จะไม่เดินซ้ำทางที่เคยเดินมาแล้วโดยเมื่อกำหนดการเดินจะทำการเช็ค Vector lastMove ที่ส่งเข้ามาแล้วทำการปรับให้ตำแหน่งที่ส่งเข้ามาเป็น false จากนั้นจึง return ค่า possibleMove[][] กลับไป

makeTileSwap(int[][],int,int,int,int)

    ไม่มีอะไรมากก็เป็น method swap ธรรมดาโดยรับ array ของตารางมาแล้วทำการ swap ตำแหน่งที่กำหนด

Show the result

     เมื่อคำนวณหา path ไปสู่ goal node ได้แล้วก็ถึงเวลาแสดงผล  โดยจะไปแสดงใน JTextArea ที่ได้สร้างเอาไว้  แต่ถ้าหาไม่ได้มันก็ไม่ได้ล่ะนะ ฮ่าๆๆ   บอกตรงๆมันหาไม่ค่อยจะได้เอาซะเลยคำตอบน่ะ  (ข้าพเจ้าเซ็ต DEPTH ไว้ที่ 20)  เพราะจริงๆแล้วจะต้องมีการใช้ A* มาช่วยล่ะนะ  อ้อใช่ อีกอย่างนึงเท่าที่อ่านมาเค้าถือว่าการเดินแบบในรูปด้านบนก็เป็น goal state ด้วยนะ (จริงๆคือส่วนใหญ่จะได้แต่แบบนั้นประจำ - -*) 

BUG&ERROR&UNFINISHED

     เนื่องจากความเร่งรีบ (และความโง่ว) ของข้าพเจ้า โปรแกรมจึงยังมีบัคอยู่บางส่วน (จริงๆก็หลายล่ะ) เท่าที่รู้ก็มี

     -  ถ้า initial state = goal state จะเดินอ้อมโลกรอบนึงแล้วถึงจะกลับมาที่เดิมได้ *fixed

     -  บางครั้งตอนจบเกมมันดันไม่เป็น goal state ซะงั้น *fixed

     -  stack overflow ในบางครั้ง *fixed

     -  ยังไม่มี Breadth-first search

     -  ยังไม่แสดงการเดินในแต่ละส่วน

 

 

โอเคก็จบลงไปแล้วสำหรับตอนนี้  คิดว่าคงจะพอเข้าใจหลักการล่ะนะ  ส่วน src ก็โหลดได้จาก ตรงนี้ เช่นเคย

ปล. อีกนิดนึง ถ้าใส่เลขแล้วมันหาไม่เจอซักทีก็ใช้อันนี้ละกันเน้อ [2 8 3] [1 6 4] [7 0 5] คือ algorithm นี้มันไม่ค่อยดีอะนะ (โทษซะเลย ฮ่าๆๆ) จริงจริ๊ง  มันต้องใช้อันอื่นช่วยด้วย  แต่จารย์ให้ทำแค่นี้ก็แค่นี้เด่ะ เอิํกๆ