Hill-climbing Algorithm for 8-Queens Problem

Stuart Russell နဲ့ Peter Norvig တို့ ရေးသားတဲ့၊ “Artificial Intelligence: A Modern Approach, Fourth Edition” စာအုပ် ရဲ့၊ "CHAPTER 4 SEARCH IN COMPLEX ENVIRONMENTS" အခန်းမှာ ပါတဲ့ "Hill-climbing Algorithm" ကို "8-queens problem" နဲ့ ပေါင်းစပ်ပြီး အပြည့်အစုံ ရှင်းလင်းတင်ပြပေးပါမယ်။

Figure 4.3 (က) ဘုရင်မ ၈-ပါးပြဿနာ။ ဘုရင်မ ၈-ပါးကို စစ်တုရင်ဘုတ်ပေါ်တွင် ဘုရင်မတစ်ပါးနှင့်တစ်ပါး မတိုက်ခိုက်စေရန် ထားပါ။ (ဘုရင်မသည် အတန်း၊ ကော်လံ သို့မဟုတ် ထောင့်ဖြတ် ပေါ်ရှိ မည်သည့် အရာကိုမဆို တိုက်ခိုက်နိုင်ပါသည်။) ပုံတွင် ထောင့်ဖြတ်မျဉ်းတစ်လျှောက်တွင် တစ်ခုနှင့်တစ်ခု တိုက်ခိုက်နေသော စတုတ္ထနှင့် သတ္တမကော်လံရှိ ဘုရင်မနှစ်ပါးမှလွဲ၍ ဤအနေအထားသည် အဖြေတစ်ခု ရလုနီးပါးအဆင့်ဖြစ်သည်။ 

(ခ) heuristic cost estimate [current state အတွက်၊ ကျန်ရှိနေသေးတဲ့ ပဋိပက္ခ conflicts အရေအတွက် ကို တိုင်းတာတဲ့ဖန်ရှင်] h = 17 ပါသော ဘုရင်မ ၈-ပါးအခြေအနေ။ လက်ရှိအခြေအနေ။ စစ်တုရင်ဘုတ်သည် ၎င်း၏ကော်လံအတွင်း ဘုရင်မတစ်ပါးကို ရွှေ့ခြင်းဖြင့် ရရှိနိုင်သော ဆက်ခံသူတိုင်းအတွက် h ၏တန်ဖိုးကို ပြသည်။ h = 12 ဖြင့် အကောင်းဆုံးတွဲဖက်ထားသော ရွေ့လျားမှု ၈-ခုရှိသည်။ hill-climbing algorithm သည် ဤအရာများထဲမှ တစ်ခုကို ရွေးပါမည်။

(နည်းသစ်ဉာဏ်ရည်တုပညာမိတ်ဆက်, စာ-၁၆၀)

ပြီးပြည့်စုံသောအခြေအနေ တည်ဆောက်ခြင်း (Complete-state Formulation)

8-queens ပြဿနာကို ဖြေရှင်းရာမှာ နည်းလမ်းအမျိုးမျိုးရှိပါတယ်။ ဥပမာ - ဘုတ်ပြားအလွတ်ကနေ စပြီး ဘုရင်မ တစ်ပါးချင်းစီကို အဆင့်လိုက် နေရာချသွားတဲ့ နည်းလမ်းရှိသလို၊ ယခု ကျွန်တော်တို့ အသုံးပြုမယ့် Complete-state formulation လိုမျိုး နည်းလမ်းလည်း ရှိပါတယ်။

Complete-state formulation ဆိုတာ အစကတည်းက စစ်တုရင်ဘုတ်ပြားပေါ်မှာ ကော်လံ (Column) တစ်ခုကို ဘုရင်မတစ်ပါးစီနှုန်းနဲ့ ၈ ပါးလုံးကို နေရာချထားလိုက်ခြင်းပါ။ ဆိုလိုတာက အခြေအနေတိုင်းမှာ အဖြေတစ်ခု ဖြစ်လာဖို့ လိုအပ်တဲ့ "အစိတ်အပိုင်းများ အားလုံး (ဘုရင်မ ၈ ပါးလုံး)" ပါရှိနေပြီးသား ဖြစ်ပါတယ်။ ဒါပေမဲ့ ၎င်းတို့ဟာ အချင်းချင်း တိုက်ခိုက်နိုင်တဲ့ (စားနိုင်တဲ့) နေရာတွေမှာ ရှိနေနိုင်တဲ့အတွက် အားလုံးက မှန်ကန်တဲ့ နေရာမှာတော့ ရှိမနေသေးပါဘူး။ ကျွန်တော်တို့ရဲ့ အဓိက ရည်ရွယ်ချက်က အဲဒီ ပဋိပက္ခ (Conflicts) တွေကို တစ်ဆင့်ချင်း လျှော့ချသွားဖို့ပဲ ဖြစ်ပါတယ်။

---

Heuristic Cost Estimate

Hill-climbing (တောင်တက်ခြင်း) အယ်လဂိုရီသမ်က အကောင်းဆုံး အဖြေကို ရှာဖွေဖို့ Heuristic cost ကို အသုံးပြုပါတယ်။ 8-queens ပြဿနာအတွက် Heuristic ဆိုတာ "လက်ရှိအခြေအနေမှာ အချင်းချင်း တိုက်ခိုက်နေတဲ့ (စားလို့ရနေတဲ့) ဘုရင်မ စုံတွဲအရေအတွက် (Number of attacking pairs)" ကို တွက်ချက်တာပါ။ ပဋိပက္ခ လုံးဝမရှိတဲ့ ပြီးပြည့်စုံတဲ့ အဖြေမှန်ကို ရဖို့ဆိုရင် ဒီ Cost တန်ဖိုးက 0 ဖြစ်သွားရပါမယ်။

Python Code

 
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 21 20:59:50 2026
@author: kks
"""
import random
# ဘုရင်မ ၈ ပါးရဲ့ အခြေအနေကို list တစ်ခုအနေနဲ့ ဖော်ပြပါမယ်။
# ဥပမာ - state = [3, 0, 4, 7, 5, 2, 6, 1] ဆိုပါစို့။
# index (0 မှ 7 အထိ) က ကော်လံ (Column) ကို ကိုယ်စားပြုပြီး၊ 
# ထိုနေရာရှိ တန်ဖိုးက အဲဒီကော်လံမှာရှိတဲ့ ဘုရင်မရဲ့ အတန်း (Row) ကို ကိုယ်စားပြုပါတယ်။
# ဒါဟာ Complete-state formulation ကို ကိုယ်စားပြုတဲ့ အကောင်းဆုံး Data Structure ဖြစ်ပါတယ်။
def calculate_conflicts(state):
    """
    Heuristic cost estimate function ပါ။
    လက်ရှိ board အခြေအနေ (state) မှာ အချင်းချင်း တိုက်ခိုက်နိုင်တဲ့ ဘုရင်မ စုံတွဲ အရေအတွက်ကို တွက်ချက်ပေးပါတယ်။
    """
    conflicts = 0
    n = len(state)
    for i in range(n):
        for j in range(i + 1, n):
            # တိုက်ခိုက်နိုင်ခြေ (၂) မျိုးကို စစ်ဆေးရပါမယ်။
            # ၁။ အတန်း (Row) တူနေသလား စစ်ဆေးခြင်း -> state[i] == state[j]
            # ၂။ ထောင့်ဖြတ် (Diagonal) တူနေသလား စစ်ဆေးခြင်း -> abs(state[i] - state[j]) == abs(i - j)
            # မှတ်ချက် - ကော်လံ (Column) ကတော့ Array ရဲ့ Index မတူတဲ့အတွက် အမြဲတမ်း ကွဲပြားနေပြီးသားပါ။
            if state[i] == state[j] or abs(state[i] - state[j]) == abs(i - j):
                conflicts += 1
    return conflicts
def get_best_neighbor(state):
    """
    လက်ရှိအခြေအနေကနေ သွားနိုင်တဲ့ အိမ်နီးချင်း (Neighbors) ၅၆ ခုထဲက
    conflicts အနည်းဆုံးဖြစ်မယ့် အကောင်းဆုံး အိမ်နီးချင်းကို ရှာဖွေပေးပါတယ်။
    (ကော်လံ ၈ ခုမှာရှိတဲ့ ဘုရင်မတွေကို ကိုယ်ပိုင်ကော်လံအတွင်း အခြား row ၇ ခုဆီ တစ်ပါးချင်း ရွှေ့ကြည့်ခြင်းဖြစ်ပါတယ်၊ ၈ x ၇ = ၅၆)
    """
    best_neighbors = []
    # လက်ရှိ cost ကို အနည်းဆုံး cost အဖြစ် အရင်သတ်မှတ်ထားပါမယ်။
    min_conflicts = calculate_conflicts(state)
    n = len(state)
    for col in range(n):
        for row in range(n):
            if state[col] == row:
                continue # လက်ရှိရှိနေတဲ့နေရာကို ရွှေ့စရာမလိုလို့ ကျော်သွားပါမယ်
            # အိမ်နီးချင်း အခြေအနေသစ် တစ်ခု ဖန်တီးပါမယ်
            neighbor = list(state)
            neighbor[col] = row
            
            # အိမ်နီးချင်းအသစ်ရဲ့ Heuristic cost (conflicts) ကို တွက်ချက်ပါမယ်
            neighbor_conflicts = calculate_conflicts(neighbor)
            if neighbor_conflicts < min_conflicts:
                # ပိုကောင်းတဲ့ အခြေအနေ (conflicts ပိုနည်းတဲ့ အခြေအနေ) ကို တွေ့ရင်
                min_conflicts = neighbor_conflicts
                best_neighbors = [neighbor] # တွေ့ထားသမျှ အကောင်းဆုံး list ကို အသစ်ပြန်စပါမယ်
            elif neighbor_conflicts == min_conflicts:
                # တူညီတဲ့ အကောင်းဆုံး အခြေအနေတွေကို list ထဲ ထပ်ထည့်ပါမယ်
                best_neighbors.append(neighbor)
    # အကောင်းဆုံး အိမ်နီးချင်းတွေထဲက တစ်ခုကို ကျပန်းရွေးချယ်ပါမယ်
    if best_neighbors:
        return random.choice(best_neighbors), min_conflicts
    else:
        return state, min_conflicts # ပိုကောင်းတဲ့ အိမ်နီးချင်း မရှိရင် လက်ရှိကိုပဲ ပြန်ပေးပါမယ်
def hill_climbing(initial_state):
    """
    Steepest-ascent Hill-climbing algorithm ရဲ့ အဓိက အပိုင်းဖြစ်ပါတယ်။
    """
    current_state = initial_state
    current_conflicts = calculate_conflicts(current_state)
    step = 0
    print(f"Step {step}: Initial State = {current_state}, Conflicts = {current_conflicts}")
    while True:
        # အကောင်းဆုံး အိမ်နီးချင်းကို ရှာပါမယ်
        neighbor, neighbor_conflicts = get_best_neighbor(current_state)
        # Hill-climbing ရဲ့ အားနည်းချက် သဘောတရားအရ၊ ပိုကောင်းတဲ့ အိမ်နီးချင်း မရှိတော့ရင် (သို့) 
        # လက်ရှိထက် ပဋိပက္ခ မနည်းတော့ဘူးဆိုရင် တောင်ထိပ် (Local Maxima သို့မဟုတ် Global Maxima) ကို ရောက်ပြီဖြစ်လို့ ဆက်မရှာဘဲ ရပ်ပါမယ်။
        if neighbor_conflicts >= current_conflicts:
            print(f"\nSearch stopped. Reached a peak (cost cannot be decreased further).")
            break
        # အခြေအနေသစ်ကို ပြောင်းလဲပါမယ်
        current_state = neighbor
        current_conflicts = neighbor_conflicts
        step += 1
        print(f"Step {step}: Moved to = {current_state}, Conflicts = {current_conflicts}")
    return current_state, current_conflicts
# ပရိုဂရမ် စတင်ခြင်း
if __name__ == "__main__":
    # Complete-state formulation အရ ဘုရင်မ ၈ ပါးကို ကျပန်း နေရာချပါမယ်
    # (ကော်လံတစ်ခုစီအတွက် row 0 ကနေ 7 အထိ ကျပန်းရွေးချယ်ပါမယ်)
    initial_board = [random.randint(0, 7) for _ in range(8)]
    
    print("--- Hill-Climbing Algorithm for 8-Queens ---")
    final_state, final_cost = hill_climbing(initial_board)
    
    print("\n--- Final Result ---")
    print(f"Final State: {final_state}")
    print(f"Remaining Conflicts: {final_cost}")
    
    if final_cost == 0:
        print("Success! A complete solution without any conflicts was found.")
    else:
        print("Failed to find a perfect solution. Got stuck in a Local Maximum.")
        print("(မှတ်ချက် - ရိုးရှင်းသော Hill-climbing သည် တောင်ကုန်းငယ်များ (Local Maxima) တွင် ပိတ်မိလေ့ရှိပါသည်။ ၎င်းသည် ဤ Algorithm ရဲ့ သဘာဝ အားနည်းချက်ဖြစ်ပါသည်။)")

ပရိုဂရမ် အနှစ်ချုပ်

ဒီပရိုဂရမ်က၊ ဘုရင်မ ၈ ပါးကို ကျပန်းချထားခြင်းမှ စတင်ပြီး၊ တစ်ဆင့်ချင်းစီမှာ၊ အချင်းချင်းတိုက်ခိုက်မှု (Conflicts) အနည်းဆုံးဖြစ်စေမဲ့ အိမ်နီးချင်းအခြေအနေဆီသို့ ရွှေ့လျားသွားပါတယ်။ တိုက်ခိုက်မှု လုံးဝမရှိတော့သည့် အခြေအနေ (သို့မဟုတ်) ထပ်မံ၍ လျှော့ချ၍ မရနိုင်တော့သည့် အခြေအနေ (Local Maxima) သို့ရောက်သောအခါ ရပ်တန့်သွားမှာဖြစ်ပါတယ်။

နောက် ပို့စ်မှာ Hill-Climbing ရဲ့ အဓိကပြဿနာဖြစ်တဲ့ "Local Maxima မှာ ပိတ်မိတတ်ခြင်း" ကို ဖြေရှင်းပေးနိုင်တဲ့ "Random-restart hill-climbing" အကြောင်းကိုဆက်လက်တင်ပြပေးပါမယ်။