8-Puzzle Solver Part-03

8-Puzzle ပြဿနာတွေနဲ့ပတ်သက်ပြီး အလွန်အရေးကြီးတဲ့အချက်တစ်ချက်ရှိတယ်။

အခု ရေးထားတဲ့ အေအိုင် ပရိုဂရမ် နှစ်ပုဒ်လုံးကို ကိုယ့်စိတ်ကြိုက် 'input configuration' ပေးပြီး အလုပ် လုပ်ခိုင်းရင်ကော၊ မှန်ကန်တဲ့ အဖြေ/ရလာဒ် အမြဲတစေ ပေးနိုင်ပါသလား?

 ဆိုရင်.... ၎င်းဟာ အလွန်အရေးကြီးပြီး လက်တွေ့ကျတဲ့ မေးခွန်းဖြစ်တယ်။

အဖြေကို အတိုချုပ်ဖြေရရင် - "မှန်ကန်သော အဖြေကို ပေးနိုင်ပါတယ်။ သို့သော် သတိပြုရမည့် အချက်တစ်ခု ရှိတယ်။" အဘယ်ကြောင့်ဆိုသော် 8-Puzzle ပြဿနာတိုင်းတွင် အဖြေမရှိနိုင်ပါဘူး။ (Not all states are solvable)

AIMA စာအုပ်ထဲမှာ ဖော်ပြထားသော "Parity Property" (စုံ၊ မ သဘောတရား) အရ၊ 8-puzzle ရဲ့ ဖြစ်နိုင်ခြေရှိသော အခြေအနေအားလုံးရဲ့ ထက်ဝက် (၅၀%) ကိုသာ ဖြေရှင်း၍ ရနိုင်ပြီး၊ ကျန်ထက်ဝက်မှာ မည်သို့မျှ ဖြေရှင်း၍ မရနိုင်သော (Unsolvable) အခြေအနေများ ဖြစ်နေတတ်သောကြောင့် ဖြစ်ပါတယ်။

ထို့ကြောင့် မိမိစိတ်ကြိုက် Input ပေးလိုက်သည့်အခါ၊ ထို Input သည် "Unsolvable" ဖြစ်နေပါက၊ ယခင်ရေးပေးခဲ့သော ပရိုဂရမ်ဟာ အဖြေရှာမတွေ့မချင်း Run နေပြီး နောက်ဆုံးတွင် None (No solution) ဟု ပြန်ပြောပါလိမ့်မည်။

Solvability Check (ဖြေရှင်းနိုင်စွမ်း ရှိမရှိ စစ်ဆေးခြင်း)

ပရိုဂရမ်ကို အချိန်ကုန်ခံပြီး မ Run ခင်၊ ဒီပုစ္ဆာက တွက်လို့ရလား၊ မရဘူးလား ဆိုတာကို Inversion Count (ပြောင်းပြန်ဖြစ်မှု အရေအတွက်) တွက်ပြီး စစ်ဆေးနိုင်သည့် Function ကို ထပ်ဖြည့်သင့်ပါတယ်။

စစ်ဆေးပုံ သဘောတရား

1. ဇယားကွက်ထဲရှိ ဂဏန်းများကို တစ်တန်းတည်း (1D List) ချရေးပါ။ (ကွက်လပ် 0 ကို ဖယ်ထုတ်ထားပါ)။
2. ရှေ့ကဂဏန်းသည် နောက်ကဂဏန်းထက် ကြီးနေလျှင် Inversion (၁) ခု ဟု သတ်မှတ်သည်။
3. စုစုပေါင်း Inversion အရေအတွက်သည် "စုံကိန်း" (Even Number) ဖြစ်မှသာ ပုစ္ဆာကို ဖြေရှင်း၍ ရပါမည်။ "မကိန်း" (Odd Number) ဖြစ်နေလျှင် ဖြေရှင်း၍ မရနိုင်ပါ။

---

ပြင်ဆင်ထားသော Python Code (Solvability Check ပါဝင်သည်)

ယခင်ရေးပေးခဲ့သော 2D Array ကုဒ်တွင် ဤစစ်ဆေးချက်ကို ပေါင်းထည့်ပြီး အောက်ပါအတိုင်း အသုံးပြုနိုင်ပါတယ်။

Python

import heapq

# ... (PuzzleState2D Class နှင့် အခြား Function များသည် ယခင်အတိုင်းဖြစ်သည်) ...
# ... (အပေါ်မှ PuzzleState2D Class ကုဒ်များကို ပြန်ထည့်ပါ / သို့မဟုတ် ယခင်ဖိုင်ကို import လုပ်ပါ) ...

def check_solvability(grid):
    """
    ပေးထားသော ပုစ္ဆာသည် ဖြေရှင်း၍ ရ၊ မရ (Solvable or Not) စစ်ဆေးခြင်း
    """
    # 1. 2D Grid ကို 1D List အဖြစ်ပြောင်းမည် (0 ကို ဖယ်ထုတ်ပါ)
    flat_list = []
    for row in grid:
        for num in row:
            if num != 0:
                flat_list.append(num)
    
    # 2. Inversion Count တွက်မည်
    inversions = 0
    for i in range(len(flat_list)):
        for j in range(i + 1, len(flat_list)):
            # ရှေ့ကောင်က နောက်ကောင်ထက် ကြီးနေရင် Inversion ဖြစ်သည်
            if flat_list[i] > flat_list[j]:
                inversions += 1
                
    print(f"Total Inversions: {inversions}")
    
    # 3. စုံကိန်း (Even) ဖြစ်မှ Solvable ဖြစ်သည်
    if inversions % 2 == 0:
        return True
    else:
        return False

# --- User Input စိတ်ကြိုက်ပေး၍ စမ်းသပ်ခြင်း ---

if __name__ == "__main__":
    
    # ဥပမာ (၁) - ဖြေရှင်း၍ ရသော ပုစ္ဆာ (Solvable)
    # Figure 3.3 မှ Start State
    input_1 = [
        [7, 2, 4],
        [5, 0, 6],
        [8, 3, 1]
    ]

    # ဥပမာ (၂) - ဖြေရှင်း၍ မရနိုင်သော ပုစ္ဆာ (Unsolvable)
    # Goal State မှ 1 နှင့် 2 ကို နေရာချင်းလဲထားခြင်း (Parity ပြောင်းသွားသည်)
    input_2 = [
        [2, 1, 3], 
        [4, 5, 6],
        [7, 8, 0]
    ]

    # စမ်းသပ်လိုသော Input ကို ဤနေရာတွင် ရွေးချယ်ပါ
    current_input = input_1 

    print("Checking solvability...")
    
    if check_solvability(current_input):
        print(">> Status: Solvable! Starting A* Search...\n")
        
        # A* Algorithm ကို ခေါ်ယူခြင်း (ယခင်ရေးခဲ့သော function)
        # solve_8_puzzle_2d function ရှိပြီးသားဟု ယူဆပါသည်
        solution = solve_8_puzzle_2d(current_input)
        
        if solution:
            print_2d_solution(solution)
        else:
            print("Something went wrong with the search.")
            
    else:
        print(">> Status: Unsolvable! (Inversion count is Odd)") 

        print("AIMA စာအုပ်ပါ Parity Property အရ ဤပုစ္ဆာသည် အဖြေမရှိနိုင်ပါ။")       

လက်တွေ့ စမ်းသပ်ကြည့်ရန်

1. Input 1 (Solvable): [7, 2, 4, 5, 0, 6, 8, 3, 1] (0 ကို ဖယ်တွက်လျှင်) -> 7, 2, 4, 5, 6, 8, 3, 1
• Inversion တွက်ကြည့်လျှင် (ဥပမာ: 7 သည် 2,4,5,6,3,1 ထက်ကြီးသည် = 6 inversions, etc.) စုစုပေါင်း 26 (စုံကိန်း) ရသဖြင့် ပရိုဂရမ်က အလုပ်လုပ်ပါလိမ့်မည်။
2. Input 2 (Unsolvable): [2, 1, 3, 4, 5, 6, 7, 8, 0] (0 ကို ဖယ်တွက်လျှင်) -> 2, 1, 3, 4, 5, 6, 7, 8
• Inversion: 2 သည် 1 ထက်ကြီးသည် (1 inversion)။ ကျန်တာ အစဉ်လိုက်ဖြစ်နေသည်။
• စုစုပေါင်း 1 (မကိန်း) ဖြစ်နေသည်။
• ဤ Input ကို ပေးလိုက်လျှင် ပရိုဂရမ်က "Unsolvable!" ဟု ချက်ချင်း ပြောပြပါလိမ့်မည်။

နိဂုံးချုပ်

Solvability Check ခံထားလိုက်ရင်တော့၊ မည်သည့် Input ကိုမဆို ပေးနိုင်ပါတယ်။ ဖြေရှင်း၍ ရလျှင် အဖြေထုတ်ပေးမည်ဖြစ်ပြီး၊ မရလျှင် ကြိုတင် သတိပေးမှာ ဖြစ်ပါတယ်။

***********************

How to make an Inversion Count

Inversion Count (ပြောင်းပြန်ဖြစ်မှု အရေအတွက်) ဆိုသည်မှာ 8-Puzzle ကဲ့သို့သော ဂိမ်းများတွင် ပုစ္ဆာတစ်ခုသည် ဖြေရှင်း၍ ရနိုင်လား (Solvable)၊ မရနိုင်ဘူးလား (Unsolvable) ဆိုတာကို ကြိုတင်တွက်ချက်သည့် သင်္ချာနည်းလမ်း ဖြစ်ပါသည်။

ယေဘုယျ စည်းမျဉ်းမှာ -

• Inversion Count သည် စုံကိန်း (Even) ဖြစ်လျှင် -> ဖြေရှင်း၍ ရနိုင်သည်။

• Inversion Count သည် မကိန်း (Odd) ဖြစ်လျှင် -> ဖြေရှင်း၍ မရနိုင်ပါ။

(မှတ်ချက် - ဤစည်းမျဉ်းသည် ပန်းတိုင် (Goal State) ကို 1, 2, 3, 4, 5, 6, 7, 8, 0 ဟု သတ်မှတ်ထားသော ပုံစံအတွက် ဖြစ်ပါသည်)

အောက်ပါ ဥပမာ (၄) ခု ဖြင့် အသေးစိတ် ရှင်းပြပေးပါမည်။

---

Inversion တွက်နည်း အဆင့်ဆင့်

1. ဇယားကွက်ကို ဘယ်မှညာ၊ အပေါ်မှအောက် တစ်တန်းတည်း (1D List) ချရေးပါ။

2. ကွက်လပ် 0 ကို လုံးဝ ဖယ်ထုတ်လိုက်ပါ။

3. ဂဏန်းတစ်ခုချင်းစီအတွက်၊ "ကိုယ့်နောက်မှာ ကိုယ့်ထက်ငယ်တဲ့ ဂဏန်း ဘယ်နှလုံးရှိလဲ" လိုက်ရေပါ။

4. ထိုအရေအတွက်အားလုံးကို ပေါင်းလိုက်ပါ။

---

ဥပမာ (၁) - ဖြေရှင်း၍ ရသော ပုစ္ဆာ (Solvable)

Start State:

Plaintext

 1  8  2
 0  4  3
 7  6  5

အဆင့် ၁: တစ်တန်းတည်းရေးပါ (0 ကိုဖယ်ပါ) -> [1, 8, 2, 4, 3, 7, 6, 5]

အဆင့် ၂: Inversion လိုက်ရေတွက်ခြင်း

• 1: နောက်မှာ ၁ ထက်ငယ်တာ မရှိပါ (0)

• 8: နောက်မှာ ၈ ထက်ငယ်တာ (2, 4, 3, 7, 6, 5) စုစုပေါင်း ၆ လုံးရှိသည်။

• 2: နောက်မှာ ၂ ထက်ငယ်တာ မရှိပါ (0)

• 4: နောက်မှာ ၄ ထက်ငယ်တာ (3) ၁ လုံးရှိသည်။

• 3: နောက်မှာ ၃ ထက်ငယ်တာ မရှိပါ (0)

• 7: နောက်မှာ ၇ ထက်ငယ်တာ (6, 5) ၂ လုံးရှိသည်။

• 6: နောက်မှာ ၆ ထက်ငယ်တာ (5) ၁ လုံးရှိသည်။

• 5: နောက်ဆုံးမို့ မရှိပါ (0)

Total Inversions: $6 + 1 + 2 + 1 = 10$

ရလဒ်: 10 သည် စုံကိန်း (Even) ဖြစ်သောကြောင့် ဤပုစ္ဆာသည် Solvable (ဖြေရှင်း၍ရသည်)။

---

ဥပမာ (၂) - ဖြေရှင်း၍ မရသော ပုစ္ဆာ (Unsolvable)

ဒါက အလွန်နာမည်ကြီးတဲ့ ပုစ္ဆာဖြစ်ပါတယ်။ ပန်းတိုင်ရောက်ခါနီးမှ နောက်ဆုံးဂဏန်း ၂ လုံး (7 နဲ့ 8) နေရာမှားနေတဲ့ ပုံစံပါ။

Start State:

Plaintext

 1  2  3
 4  5  6
 8  7  0

အဆင့် ၁: တစ်တန်းတည်းရေးပါ -> [1, 2, 3, 4, 5, 6, 8, 7]

အဆင့် ၂: Inversion လိုက်ရေတွက်ခြင်း

• 1, 2, 3, 4, 5, 6 အထိ အားလုံး အစဉ်လိုက်ဖြစ်နေလို့ Inversion မရှိပါ။ (0)

• 8: နောက်မှာ ၈ ထက်ငယ်တာ (7) ၁ လုံးရှိသည်။

• 7: နောက်ဆုံးမို့ မရှိပါ။

Total Inversions: $1$

ရလဒ်: 1 သည် မကိန်း (Odd) ဖြစ်သောကြောင့် ဤပုစ္ဆာကို ကမ္ဘာပျက်တဲ့အထိ ရွှေ့လျားကစားလည်း ပန်းတိုင် (1,2,3...7,8,0) ကို ဘယ်တော့မှ ရောက်မည်မဟုတ်ပါ။ (Unsolvable)

---

ဥပမာ (၃) - ရှုပ်ထွေးသော ပုစ္ဆာ (Solvable)

စာအုပ်ထဲက Figure 3.3 ပုစ္ဆာကို ယူသုံးကြည့်ပါမယ်။

Start State:

Plaintext

 7  2  4
 5  0  6
 8  3  1

အဆင့် ၁: တစ်တန်းတည်းရေးပါ (0 ဖယ်) -> [7, 2, 4, 5, 6, 8, 3, 1]

အဆင့် ၂: Inversion လိုက်ရေတွက်ခြင်း

• 7: (2, 4, 5, 6, 3, 1) -> ၆ လုံး (၇ ထက်ငယ်သည်)

• 2: (1) -> ၁ လုံး (၂ ထက်ငယ်သည်)

• 4: (3, 1) -> ၂ လုံး

• 5: (3, 1) -> ၂ လုံး

• 6: (3, 1) -> ၂ လုံး

• 8: (3, 1) -> ၂ လုံး

• 3: (1) -> ၁ လုံး

• 1: (0)

Total Inversions: $6 + 1 + 2 + 2 + 2 + 2 + 1 = 16$

ရလဒ်: 16 သည် စုံကိန်း (Even) ဖြစ်သည်။ ထို့ကြောင့် Solvable ဖြစ်သည်။

---

ဥပမာ (၄) - လှည့်စားထားသော ပုစ္ဆာ (Unsolvable)

အထက်ပါ ဥပမာ (၃) ကိုမှ ဂဏန်း 1 နဲ့ 3 နေရာချင်း လဲလိုက်ပါမယ်။

Start State:

Plaintext

 7  2  4
 5  0  6
 8  1  3

(အောက်ဆုံးတန်းက 3 နဲ့ 1 ကို နေရာချိန်းလိုက်ပါတယ်)

အဆင့် ၁: [7, 2, 4, 5, 6, 8, 1, 3]

အဆင့် ၂: Inversion လိုက်ရေတွက်ခြင်း

• 7: (2, 4, 5, 6, 1, 3) -> ၆ လုံး

• 2: (1) -> ၁ လုံး

• 4: (1, 3) -> ၂ လုံး

• 5: (1, 3) -> ၂ လုံး

• 6: (1, 3) -> ၂ လုံး

• 8: (1, 3) -> ၂ လုံး

• 1: နောက်မှာ ၃ ရှိတယ် (၁ ထက်မငယ်ဘူး) -> ၀

• 3: (0)

Total Inversions: $6 + 1 + 2 + 2 + 2 + 2 + 0 = 15$

ရလဒ်: 15 သည် မကိန်း (Odd) ဖြစ်သည်။ ထို့ကြောင့် ဂဏန်းနှစ်လုံး (၁ နဲ့ ၃) ပဲ နေရာလဲလိုက်ပေမယ့် ပုစ္ဆာတစ်ခုလုံးက ဖြေရှင်း၍မရသော (Unsolvable) ဖြစ်သွားပါသည်။

---

အနှစ်ချုပ်

ဒီ Inversion Count နည်းလမ်းဟာ AI ပရိုဂရမ်အတွက် အရမ်းအရေးပါပါတယ်။ ဘာကြောင့်လဲဆိုတော့ -

1. ကွန်ပျူတာကို အဖြေမရှိတဲ့ ပုစ္ဆာတစ်ခု ပေးပြီး အလကား အချိန်ကုန်ခံခိုင်းတာမျိုး မဖြစ်စေဖို့ပါ။

2. if inversions % 2 == 0: ဆိုတဲ့ ကုဒ်တစ်ကြောင်းတည်းနဲ့ ပုစ္ဆာက ရှင်းလို့ရမရ ချက်ချင်းသိနိုင်လို့ ဖြစ်ပါတယ်။