8-Puzzle Solver Part-02

အခု ဒုတိယပိုင်းမှာ 8-Puzzle ပြဿနာကို 1D List (တစ်တန်းတည်း) အစား၊ 2D Array (၃x၃ ဇယားကွက်ပုံစံ) ဖြင့် ပြောင်းလဲရေးသားကြည့်မှာ ဖြစ်ပါတယ်။

သို့သော် Python မှာ List (List of Lists) တွေကို Set (Explored Set) ထဲသို့ ထည့်သွင်း၍ မရသောကြောင့် (Un-hashable ဖြစ်၍)၊ Tuple of Tuples (ပြောင်းလဲ၍မရသော 2D Array) ပုံစံဖြင့် သိမ်းဆည်းသည့် နည်းလမ်းကို သုံးပါမယ်။

Python

import heapq

# ---------------------------------------------------------
# အပိုင်း (၁) - 2D Array State ဖြင့် တည်ဆောက်ထားသော Puzzle Class
# ---------------------------------------------------------

class PuzzleState2D:
    def __init__(self, board, parent=None, move="", cost=0):
        # board သည် ယခုအခါ Tuple of Tuples ဖြစ်သည် (ဥပမာ: ((7,2,4), (5,0,6), ...))
        self.board = board          
        self.parent = parent        
        self.move = move            
        self.cost = cost            
        self.heuristic = self.calculate_manhattan() 
        self.f_score = self.cost + self.heuristic   

    def calculate_manhattan(self):
        """
        Manhattan Distance တွက်ချက်ခြင်း (2D Array ဗားရှင်း)
        """
        distance = 0
        # Row (အတန်း) နှင့် Column (ဒေါင်လိုက်) နှစ်ထပ် Loop ပတ်၍ တွက်မည်
        for r in range(3):
            for c in range(3):
                val = self.board[r][c]
                
                if val != 0: # ကွက်လပ် (0) ကို ထည့်မတွက်ပါ
                    # ပန်းတိုင်တွင် ရှိရမည့်နေရာ (Target Row, Target Col) ကို တွက်ခြင်း
                    # ပန်းတိုင်ပုံစံ: 
                    # 0 1 2
                    # 3 4 5
                    # 6 7 8
                    target_row = val // 3
                    target_col = val % 3
                    
                    # အကွာအဝေးပေါင်းခြင်း: |current_r - target_r| + |current_c - target_c|
                    distance += abs(r - target_row) + abs(c - target_col)
        return distance

    def find_blank(self):
        """ကွက်လပ် (0) ရှိသော (Row, Col) ကို ရှာဖွေခြင်း"""
        for r in range(3):
            for c in range(3):
                if self.board[r][c] == 0:
                    return r, c
        return None

    def __lt__(self, other):
        # Priority Queue အတွက် f_score နည်းတာကို ဦးစားပေးရန်
        return self.f_score < other.f_score

    def is_goal(self):
        # ပန်းတိုင်: ((0, 1, 2), (3, 4, 5), (6, 7, 8))
        goal_tuple = ((0, 1, 2), (3, 4, 5), (6, 7, 8))
        return self.board == goal_tuple

    def get_neighbors(self):
        """
        2D Grid ပေါ်တွင် ကွက်လပ်ရွေ့လျားပြီး အိမ်နီးချင်း State များ ရှာဖွေခြင်း
        """
        neighbors = []
        zero_r, zero_c = self.find_blank() # 0 ရှိတဲ့နေရာ (r, c)

        # ရွေ့နိုင်သော ဦးတည်ချက်များ (Row change, Col change)
        directions = {
            "UP":    (-1, 0),
            "DOWN":  (1, 0),
            "LEFT":  (0, -1),
            "RIGHT": (0, 1)
        }

        for move_name, (dr, dc) in directions.items():
            new_r, new_c = zero_r + dr, zero_c + dc

            # ဇယားကွက် ဘောင်ကျော်မသွားအောင် စစ်ဆေးခြင်း (0 မှ 2 အတွင်းသာ)
            if 0 <= new_r < 3 and 0 <= new_c < 3:
                
                # Tuple ကို ပြင်၍မရသဖြင့်၊ ယာယီ List of Lists သို့ ပြောင်းမည်
                # (Deep Copy သဘောတရား)
                new_board_list = [list(row) for row in self.board]
                
                # နေရာချင်း လဲလှယ်ခြင်း (Swap)
                # 0 နေရာနှင့် ဂဏန်းနေရာ လဲလိုက်သည်
                new_board_list[zero_r][zero_c], new_board_list[new_r][new_c] = \
                new_board_list[new_r][new_c], new_board_list[zero_r][zero_c]
                
                # ပြန်သိမ်းရန်အတွက် Tuple of Tuples သို့ ပြန်ပြောင်းမည်
                new_board_tuple = tuple(tuple(row) for row in new_board_list)
                
                # State အသစ် ဖန်တီးပြီး ထည့်မည်
                neighbors.append(PuzzleState2D(new_board_tuple, self, move_name, self.cost + 1))
        
        return neighbors

# ---------------------------------------------------------
# အပိုင်း (၂) - A* Search Algorithm (မပြောင်းလဲပါ)
# ---------------------------------------------------------

def solve_8_puzzle_2d(initial_grid):
    # Input List of Lists ကို Tuple of Tuples သို့ ပြောင်းပေးရမည် (Hashable ဖြစ်စေရန်)
    initial_tuple = tuple(tuple(row) for row in initial_grid)
    start_node = PuzzleState2D(initial_tuple)
    
    frontier = []
    heapq.heappush(frontier, start_node)
    
    explored = set()
    
    print("Searching solution with 2D Representation...")
    
    while frontier:
        current_node = heapq.heappop(frontier)
        
        if current_node.is_goal():
            return current_node
        
        explored.add(current_node.board)
        
        for child in current_node.get_neighbors():
            if child.board not in explored:
                heapq.heappush(frontier, child)

    return None

# ---------------------------------------------------------
# အပိုင်း (၃) - ရလဒ် ထုတ်ပြခြင်း
# ---------------------------------------------------------

def print_2d_solution(node):
    path = []
    while node:
        path.append(node)
        node = node.parent
    path.reverse()
    
    print(f"\nSolution Found in {len(path)-1} moves!")
    print("=" * 30)
    
    for i, state in enumerate(path):
        print(f"Step {i}: {state.move if state.move else 'Start State'}")
        
        # 2D Array ကို လှပစွာ ထုတ်ပြခြင်း
        for row in state.board:
            print(f"| {row[0]} {row[1]} {row[2]} |")
        print("-" * 13)

# --- Main Execution ---
if __name__ == "__main__":
    # 2D Array Input (List of Lists)
    # Figure 3.3 Start State:
    # 7 2 4
    # 5 0 6
    # 8 3 1
    start_grid = [
        [7, 2, 4],
        [5, 0, 6],
        [8, 3, 1]
    ]
    
    solution = solve_8_puzzle_2d(start_grid)
    
    if solution:
        print_2d_solution(solution)
    else:
        print("No solution found.")

ပြောင်းလဲမှုများအပေါ် ရှင်းလင်းချက်

1. State Representation (2D Structure):

   • ယခင်က [7, 2, 4, ...] ဟု တစ်တန်းတည်းရေးရာမှ၊ ယခုအခါ [[7, 2, 4], [5, 0, 6], [8, 3, 1]] ဟု အတန်းနှင့် တိုင် (Rows & Columns) ခွဲခြားသတ်မှတ်လိုက်တယ်။

   • Python Class ထဲတွင် သိမ်းဆည်းရာ၌ Tuple of Tuple (Tuple ထဲတွင် Tuple ပြန်ထပ်ထားသောပုံစံ) ကို သုံးပါတယ်။ အဘယ်ကြောင့်ဆိုသော် List များကို explored set ထဲထည့်၍ မရသောကြောင့် ဖြစ်တယ်။

2. Manhattan Distance တွက်ချက်ပုံ:

   • ယခင်က Index တစ်ခုတည်းကို divmod သုံးပြီး တွက်သော်လည်း၊ ယခုအခါ for r in range(3): for c in range(3): ဟူ၍ နှစ်ထပ်ကွပ်ပြီး တွက်ချက်ထားတယ်။ ဒါက 2D Array သဘောတရားနှင့် ပိုကိုက်ညီတယ်။ (computer science သမားတွေက၊ algorithm ရှုထောင့်က ဆင်ခြင်ကြည့်ရင် looping နှစ်ထပ်တွေရဲ့ complexity ကို သတိထားမိလိမ့်မယ်။)

   • target_row = val // 3 နှင့် target_col = val % 3 ကို အသုံးပြု၍ ဂဏန်းတစ်ခုစီ ရှိသင့်သော နေရာကို ရှာဖွေတယ်။

3. Neighbor Generation (အရွေ့များ ရှာဖွေခြင်း):

   • ကွက်လပ် 0 ၏ နေရာကို (row, col) ဖြင့် ရှာဖွေတယ်။

   • နေရာချင်း လဲရာမှာ (Swap)၊ Tuple ကို တိုက်ရိုက်ပြင်မရတဲ့အတွက် List of Lists သို့ ခဏပြောင်း၊ လဲလှယ်၊ ပြီးမှ Tuple ပြန်ပြောင်းသည့် နည်းစနစ်ကို သုံးထားတယ်။

ဒီကုဒ်က ရှင်းလင်းပြီး၊ သင်္ချာမက်ထရစ် (Matrix) သဘောတရားများနဲ့ ပိုမိုနီးစပ်တဲ့အတွက် လေ့လာရာမှာ ပိုမိုအဆင်ပြေစေဖို့ မျှော်လင့်ပါတယ်။