အခန်း ၁၆ - Backtracking

အခန်း ၁၃–၁၅ မှာ tree တွေကို recursion နဲ့ DFS လေ့လာခဲ့ပါတယ် — node တစ်ခုကို ရောက်ရင် "ဘယ်ဘက် ဆင်း၊ ပြန်တက်၊ ညာဘက် ဆင်း" လုပ်တာ။ အခု ဒီ idea ကို tree မရှိဘဲ — ဖြစ်နိုင်ခြေ အကုန်လုံးကို စနစ်တကျ စမ်းကြည့်ရတဲ့ ပြဿနာတွေမှာ သုံးကြည့်ပါမယ်။

ဥပမာ — "ဂဏန်း [1,2,3] ကို ဖြစ်နိုင်တဲ့ အစီအစဉ် (permutation) အကုန် ထုတ်ပါ" ဆိုရင် [1,2,3], [1,3,2], [2,1,3]... ၆ မျိုး ရှိပါတယ်။ ဒါမျိုး "ရွေးချယ်စရာတွေ ဆင့်ကဲ ပေါင်းပြီး၊ valid အဖြေ အကုန် ရှာ" ရတဲ့ ပြဿနာတွေကို brute force (အကုန် စမ်း) နဲ့ ဖြေနိုင်ပေမယ့် — ရိုးရိုး brute force က မလိုတဲ့ လမ်းကြောင်းတွေပါ စမ်းမိလို့ အချိန် ပိုကုန်ပါတယ်။

Backtracking ဆိုတာ — brute force ထဲက smart search pattern ဖြစ်ပါတယ်။ "ရွေး (Try/Choose) → စမ်း (Explore) → မရရင် ပြန်ဖြုတ် (Undo)" သုံးဆင့်ကို ထပ်ခါတလဲလဲ လုပ်ပြီး၊ မဖြစ်နိုင်တော့တဲ့ လမ်းကြောင်းတွေကို စောစော ဖြတ်ပစ် (pruning) လို့ ရတာ ဖြစ်ပါတယ်။ ဒီအခန်းမှာ backtracking ရဲ့ "Choose–Explore–Undo" pattern ကို လေ့လာပြီး classic ပြဿနာ ၅ ခု ဖြေကြည့်ပါမယ်။

Backtracking ဆိုတာ ဘာလဲ — Choose, Explore, Undo

Backtracking ကို "ဆုံးဖြတ်ချက် သစ်ပင် (decision tree)" အဖြစ် မြင်ရင် အလွယ်ဆုံးပါ။ အဆင့်တိုင်းမှာ "ရွေးစရာ" တွေ ရှိပြီး၊ တစ်ခုစီကို လမ်းခွဲ (branch) တစ်ခုအဖြစ် ဆင်းကြည့်တာ — ဆင်းလို့ မရတော့ရင် ပြန်တက်ပြီး တစ်ခြား လမ်းခွဲ စမ်းတာ ဖြစ်ပါတယ်။

[1,2,3] ရဲ့ permutation ရှာတဲ့ decision tree —

                       [ ] (ဘာမှ မရွေးရသေး)
            /            |             \
          [1]           [2]           [3]      ← ပထမ နေရာ ဘာထည့်မလဲ
         /   \         /   \         /   \
      [1,2] [1,3]  [2,1] [2,3]  [3,1] [3,2]   ← ဒုတိယ နေရာ
        |     |      |     |      |     |
     [1,2,3][1,3,2]...                        ← တတိယ (ပြည့်ပြီ → အဖြေ ၁ ခု)

သစ်ပင်ထဲ လမ်းကြောင်း တစ်ခုစီကို ဆင်းတဲ့အခါ သုံးဆင့် ထပ်ခါ လုပ်သည် —

1. Choose (ရွေး): ရွေးစရာ တစ်ခုကို ယူ၊ လက်ရှိ အဖြေ (path) ထဲ ထည့်။
2. Explore (စမ်း): အဲ့ ရွေးချယ်မှုနဲ့ ဆက်ပြီး အောက်ကို recursion ဆင်း။
3. Undo (ပြန်ဖြုတ်): recursion ပြန်တက်လာရင် — အဆင့် ၁ မှာ ထည့်ထားတာကို ပြန်ထုတ် (path ကို မူလအတိုင်း ပြန်ထား)၊ နောက် ရွေးစရာ စမ်းဖို့။

ဒီ Undo က backtracking ရဲ့ အသက်ပါ — "ဒီ လမ်းကြောင်း စမ်းပြီးပြီ၊ အခု သန့်ရှင်းပြန်လုပ်ပြီး နောက်တစ်ခု စမ်းမယ်" ဆိုတဲ့ သဘောဖြစ်သည်။

   path = []
   choose 1 → path = [1]
       explore... (1 နဲ့ ဆက်တာ အကုန် စမ်း)
   undo 1   → path = []      ← ပြန်သန့်
   choose 2 → path = [2]
       explore...
   undo 2   → path = []
   ...

ပုံသေ Pattern (Template)

Backtracking ပြဿနာ အများစုက Choose → Explore → Undo ဆိုတဲ့ Pattern တစ်ခုတည်းကို အခြေခံထားတာပါ။ Problem ပေါ်မူတည်ပြီး အသေးစိတ် logic ပဲ ပြောင်းသွားတာ ဖြစ်ပါတယ်။

ပထမ အောက်က code က pseudocode idea ဖြစ်ပြီး Java code မဟုတ်ပါ — structure ကို မြင်ဖို့သာ။

backtrack(path):

    if လက်ရှိအခြေအနေက အဖြေရပြီ:
        result.add(path ကို copy ကူး)
        return
    for ရွေးစရာ တစ်ခုစီ:

        if မရွေးသင့်ရင်:
            continue

        path ထဲ ထည့်        // 1. Choose

        backtrack(path)      // 2. Explore

        path ထဲက ပြန်ဖျက်    // 3. Undo

အဲ့ဒီ idea ကို Java မှာ ရေးကြည့်ရင် ဒီလို ဖြစ်သည် — ဥပမာ အနေနဲ့ length n ရဲ့ binary string အကုန် (000, 001, 010, ...) ထုတ်တဲ့ ပြောင်းဖြတ်ကြည့်ပြီး Choose → Explore → Undo ကို ကြည့်ပါမယ်။ Comment ၃ ခု က backtracking ရဲ့ အသက်ဖြစ်ပြီး၊ ဒီအခန်းရဲ့ ပြဿနာ အကုန်လုံးက ဒီ structure တူထည်း သုံးတာပါ။

import java.util.*;

class Main {
    static List<String> result = new ArrayList<>();

    public static void main(String[] args) {
        backtrack(3, new StringBuilder());
        System.out.println(result);
        // [000, 001, 010, 011, 100, 101, 110, 111]   ← 2³ = ၈ မျိုး
    }

    static void backtrack(int n, StringBuilder path) {
        if (path.length() == n) {                // base case — n လုံး ပြည့်ပြီ
            result.add(path.toString());         // copy ကူးပြီး မှတ်
            return;
        }
        for (char c : new char[]{'0', '1'}) {    // ရွေးစရာ ၂ ခု (0 သို့ 1)
            path.append(c);                      // 1. Choose
            backtrack(n, path);                  // 2. Explore
            path.deleteCharAt(path.length()-1);  // 3. Undo
        }
    }
}

path.toString() (copy ကူးခြင်း): result ထဲ path ကို တိုက်ရိုက် မထည့်ရပါ — path က တစ်ခုတည်း ပြန်ပြင်နေတဲ့ object ဖြစ်လို့၊ copy မကူးရင် နောက်ပြီးတာ result ထဲက အဖြေတွေပါ ပြောင်းသွားပါမယ်။ List သုံးရင် new ArrayList<>(path)၊ String သုံးရင် .toString() နဲ့ copy ကူးရပါတယ်။ undo လိုတိုင်း copy လည်း လိုပါ။

Undo ဘာကြောင့် လိုတာလဲ

ဥပမာ path = [1, 2] ရှိနေတယ်ဆိုပါစို့။

3 ကို ရွေးလိုက်ရင်

[1, 2]
   ↓ Choose
[1, 2, 3]

အဲဒီ branch ကို စမ်းပြီးသွားရင် 3 ကို ပြန်ဖျက်ရပါတယ်။

[1, 2, 3]
   ↓ Undo
[1, 2]

ဒါမှ နောက်ထပ် 4 ကို ဆက်စမ်းနိုင်မှာ ဖြစ်ပါတယ်။

[1, 2]
   ↓ Choose
[1, 2, 4]

Undo မလုပ်ရင်

[1, 2, 3, 4]

လိုမျိုး ဖြစ်သွားပြီး branch အဟောင်းရဲ့ data တွေ ကျန်နေတဲ့အတွက် အဖြေမှားသွားပါလိမ့်မယ်။

path.removeLast() (Undo) က Backtracking ရဲ့ အဓိက အစိတ်အပိုင်း ဖြစ်ပါတယ်။ Choose လုပ်ပြီးတိုင်း Explore လုပ်မယ်၊ Explore ပြီးတိုင်း Undo လုပ်မယ်။ ဒီ Pattern ကို Backtracking ပြဿနာ အများစုမှာ အမြဲတွေ့ရပါတယ်။

Backtracking vs Recursion: Backtracking က Recursion ကို အသုံးပြုတဲ့ Algorithm တစ်မျိုး ဖြစ်ပါတယ်။ သာမန် Recursion (ဥပမာ factorial, tree traversal) က လမ်းကြောင်းတစ်ခုကိုပဲ ဆင်းသွားတာ များပါတယ်။ Backtracking ကတော့ လမ်းကြောင်း အမျိုးမျိုးကို စမ်း၊ မရရင် ပြန်ဖြုတ် (Undo)၊ ရတဲ့အဖြေ အားလုံးကို စု တာ ဖြစ်ပါတယ်။ ဒါကြောင့် Choose → Explore → Undo ဆိုတဲ့ Pattern က Backtracking ရဲ့ အမှတ်အသား ဖြစ်ပါတယ်။

Pruning — မလိုတဲ့ လမ်းကြောင်း ဖြတ်ခြင်း

Brute force က ဖြစ်နိုင်ခြေ အကုန် စမ်းတာမို့ နှေးပါတယ်။ Backtracking ရဲ့ အားသာချက်က — လမ်းခွဲ တစ်ခုကို ဆင်းတဲ့အခါ "ဒီကနေ ဆက်သွားရင် valid အဖြေ ဘယ်တော့မှ မဖြစ်နိုင်တော့ဘူး" ဆိုတာ သိရင် — အဲ့ subtree တစ်ခုလုံးကို ချက်ချင်း ဖြတ်ပစ် (prune) လို့ ရတာ ဖြစ်ပါတယ်။

   ဥပမာ — "ပေါင်းလဒ် 5 ဖြစ်အောင် ဂဏန်း ရွေး" မှာ [2,4,...] ရွေးပြီး sum=6 ဖြစ်သွားရင်
   → 5 ထက် ကျော်သွားပြီ → ဒီ subtree ဆက်ဆင်းစရာ မလို → prune

Pruning က decision tree ရဲ့ ကြီးမားတဲ့ အကိုင်းတွေကို ဖြတ်ချလို့ — အမှန်တကယ် စမ်းရတဲ့ လမ်းကြောင်း အရေအတွက် သိသိသာသာ လျော့ကျသွားပါတယ်။ ဒါက backtracking ကို "ရိုးရိုး brute force" ထက် မြန်စေတဲ့ အဓိက အချက်ပါ။

Complexity: ဒါတွေက ဖြစ်နိုင်ခြေ အကုန် ထုတ်ရတဲ့ ပြဿနာတွေမို့ — အဆိုးဆုံး complexity က မကြာခဏ exponential ($O(2^n)$, $O(n!)$ စသည်) ဖြစ်ပါတယ်။ Pruning က လက်တွေ့မှာ မြန်အောင် ကူပေမယ့် အဆိုးဆုံး bound ကို မပြောင်းနိုင်တာ များပါတယ်။

Real-world Examples

Backtracking ဟာ "valid ဖြစ်နိုင်ခြေ အကုန် ရှာ / constraint ပြည့်တဲ့ အစီအစဉ် ရှာ" လိုတဲ့ နေရာတိုင်းမှာ တွေ့ရပါတယ် —

• Permission / Role Combinations — user တစ်ဦးကို ပေးနိုင်တဲ့ permission set အကုန် (သို့) rule ပြည့်တဲ့ combination တွေ ထုတ်ခြင်း။
• Form Rules Combination — field တွေရဲ့ "ဒါ ရွေးရင် ဟို မရွေးရ" မျိုး constraint ပြည့်တဲ့ valid form အခြေအနေ အကုန် ရှာ။
• Search All Valid Configurations — feature flag, settings, pricing rule စတဲ့ configuration တွေထဲက rule ပြည့်တဲ့ အခြေအနေ အကုန် ရှာ။
• Scheduling Options — အချိန်/resource မထပ်အောင် (constraint) event တွေ စီစဉ်နိုင်တဲ့ နည်းလမ်း အကုန် ရှာ။
• Puzzle Solver — Sudoku (ကွက်တိုင်း ၁–၉ ဖြည့်၊ row/column/box မထပ်), N-Queens (queen တွေ မတိုက်အောင် ချ), crossword — အကုန် "ရွေး → စမ်း → ဖောက်ရင် ပြန်ဖြုတ်" pattern။
• Maze / Path Finding — လမ်းကြောင်းတိုင်း စမ်း၊ ပိတ်နေရင် ပြန်ဆုတ်ပြီး တစ်ခြားလမ်း စမ်း။

ဒီ pattern တွေ အကုန်လုံး တူပါတယ် — "ရွေးချယ်စရာ ဆင့်ကဲ ပေါင်းရင်း၊ constraint ဖောက်ရင် ပြန်ဆုတ်၊ ပြည့်ရင် အဖြေ မှတ်"။ ဒါက backtracking ရဲ့ အသုံးချပုံ အနှစ်ချုပ်ပါ။

Questions

Backtracking ကို ပြဿနာ ၅ ခုနဲ့ လေ့လာကြည့်ရအောင်။ ပြဿနာတိုင်းရဲ့ သော့ချက်က — Choose → Explore → Undo pattern ကို မှန်မှန် တပ်ဆင်တတ်ဖို့ နဲ့ base case / pruning ကို ရှာတတ်ဖို့ ဖြစ်ပါတယ်။

၁။ Subsets

ထပ်တူ မရှိတဲ့ ကိန်း array nums ပေးထားသည်။ ဖြစ်နိုင်တဲ့ subset (အစုခွဲ) အကုန် (power set) ကို ပြန်ပါ။

Example 1:

Input: nums = [1,2,3]
Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
   (subset ၈ ခု = 2³)

ရှင်းလင်းချက်

subset တစ်ခုစီအတွက် — element တစ်ခုစီကို "ထည့်မလား / မထည့်ဘူးလား" ဆုံးဖြတ်ရပါတယ်။ ဒါက index တစ်ခုစီကနေ "ထည့်တဲ့ branch" နဲ့ "မထည့်တဲ့ branch" ၂ ခွဲ ဆင်းတဲ့ decision tree ဖြစ်သည်။

ပိုလွယ်တဲ့ မြင်ပုံ — start index ကနေ စပြီး၊ နောက်က element တွေ တစ်ခုစီကို path ထဲ ထည့် (Choose) → ဆက်ဆင်း (Explore) → ပြန်ဖြုတ် (Undo)။ node တိုင်းက valid subset ဖြစ်လို့ — ဆင်းတိုင်း မှတ်ပါတယ် (base case သီးသန့် မလို)။

Time Complexity: $O(n \cdot 2^n)$ - subset $2^n$ ခု၊ တစ်ခုစီ copy ယူ $O(n)$။
Space Complexity: $O(n)$ - recursion depth + path (output မရေတွက်)။

Java Solution

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> path,
                           List<List<Integer>> result) {
        result.add(new ArrayList<>(path));     // node တိုင်း valid subset → မှတ်
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);                 // 1. Choose
            backtrack(nums, i + 1, path, result);  // 2. Explore (i+1 ကစ)
            path.remove(path.size() - 1);      // 3. Undo
        }
    }
}

၂။ Permutations

ထပ်တူ မရှိတဲ့ ကိန်း array nums ပေးထားသည်။ ဖြစ်နိုင်တဲ့ အစီအစဉ် (permutation) အကုန် ကို ပြန်ပါ။

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
   (permutation ၆ ခု = 3!)

ရှင်းလင်းချက်

Subset နဲ့ ကွာတာ — permutation မှာ အစီအစဉ် အရေးကြီးပြီး element အကုန်လုံး သုံးရသည်။ ဒါကြောင့် "သုံးပြီးသား element ကို ထပ် မသုံးရ" ဆိုတဲ့ track လုပ်ဖို့ used[] (သို့ contains စစ်) လိုပါတယ်။

• Base case: path အရှည် = nums အရှည် → permutation ပြည့်ပြီ → မှတ်။
• element တစ်ခုစီ — သုံးပြီးသား မဟုတ်ရင် → Choose (mark used + path ထည့်) → Explore → Undo (unmark + path ဖြုတ်)။

Time Complexity: $O(n \cdot n!)$ - permutation $n!$ ခု၊ တစ်ခုစီ copy $O(n)$။
Space Complexity: $O(n)$ - recursion depth + used array။

Java Solution

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path,
                           List<List<Integer>> result) {
        if (path.size() == nums.length) {          // base case — ပြည့်ပြီ
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;                 // pruning — သုံးပြီးသား ကျော်
            used[i] = true;  path.add(nums[i]);    // 1. Choose
            backtrack(nums, used, path, result);   // 2. Explore
            used[i] = false; path.remove(path.size() - 1);  // 3. Undo
        }
    }
}

၃။ Combinations

ကိန်း n နဲ့ k ပေးထားသည်။ [1..n] ထဲက ကိန်း k လုံး ရွေးတဲ့ combination အကုန် ကို ပြန်ပါ (အစီအစဉ် မရေး)။

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
   (combination ၆ ခု = C(4,2))

ရှင်းလင်းချက်

Permutation နဲ့ ကွာတာ — combination မှာ အစီအစဉ် မရေး ([1,2] နဲ့ [2,1] တူ)။ ဒါကြောင့် Subsets လို start index ကို သုံးပြီး "နောက်ပြန် မလှည့်" အောင် လုပ်ရင်၊ ထပ်နေတာ အလိုအလျောက် ရှောင်ပါတယ်။

• Base case: path အရှည် = k → combination ပြည့်ပြီ → မှတ်။
• start ကစ၊ ကိန်းတစ်ခုစီ Choose → Explore (i+1 ကစ) → Undo။

Pruning: "ကျန် ကိန်း မလောက်တော့ရင်" ဆက်ဆင်းစရာ မလို — for loop ရဲ့ အဆုံးကို n - (k - path.size()) + 1 အထိ ကန့်သတ်ထားရင် မလိုတဲ့ branch တွေ မစမ်းရတော့ပါ။

Time Complexity: $O(k \cdot C(n,k))$။
Space Complexity: $O(k)$ - recursion depth + path။

Java Solution

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(n, k, 1, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int n, int k, int start, List<Integer> path,
                           List<List<Integer>> result) {
        if (path.size() == k) {                    // base case — k လုံး ပြည့်
            result.add(new ArrayList<>(path));
            return;
        }
        int remaining = k - path.size();
        for (int i = start; i <= n - remaining + 1; i++) {
            path.add(i);                           // 1. Choose
            backtrack(n, k, i + 1, path, result);  // 2. Explore (i+1 → နောက်မပြန်)
            path.remove(path.size() - 1);          // 3. Undo
        }
    }
}

၄။ Combination Sum

ထပ်တူ မရှိတဲ့ ကိန်း array candidates နဲ့ ပစ်မှတ် target ပေးထားသည်။ ပေါင်းလဒ် target ဖြစ်တဲ့ combination အကုန် ကို ပြန်ပါ။ ကိန်း တစ်ခုကို အကြိမ်ကြိမ် ပြန်သုံးလို့ ရသည်။

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
   (2+2+3 = 7,  7 = 7)

ရှင်းလင်းချက်

ဒါက Combinations နဲ့ ဆင်ပေမယ့် ၂ ချက် ကွာသည် — (၁) တစ်ခု ပြန်သုံးလို့ ရတာမို့ Explore မှာ i+1 မဟုတ်ဘဲ i ကစ (ကိုယ့်ကို ပြန်ရွေးခွင့်)။ (၂) base case က count မဟုတ်ဘဲ sum။

• ပေါင်းရင်း target ကို လျှော့သွား (remain)။
• Base case ၂ မျိုး: remain == 0 → အဖြေ မှတ်။ remain < 0 → pruning (ကျော်ပြီ → ဖြတ်)။
• candidate တစ်ခုစီ Choose → Explore (i ကစ — ပြန်သုံးခွင့်) → Undo။

Pruning ၏ အရေးပါပုံ: remain < 0 ဖြစ်တာနဲ့ ဆက်မဆင်းတော့တာက decision tree ရဲ့ ကြီးမားတဲ့ အပိုင်းတွေ ဖြတ်ချပေးသည်။

Time Complexity: အဆိုးဆုံး exponential (target/candidate ပေါ် မူတည်)။
Space Complexity: $O(target / min(candidates))$ - recursion depth။

Java Solution

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] cand, int remain, int start,
                           List<Integer> path, List<List<Integer>> result) {
        if (remain == 0) {                         // base case — target ပြည့်
            result.add(new ArrayList<>(path));
            return;
        }
        if (remain < 0) return;                    // pruning — ကျော်ပြီ
        for (int i = start; i < cand.length; i++) {
            path.add(cand[i]);                     // 1. Choose
            backtrack(cand, remain - cand[i], i, path, result);  // 2. Explore (i → ပြန်သုံး)
            path.remove(path.size() - 1);          // 3. Undo
        }
    }
}

၅။ N-Queens

n × n chessboard ပေါ်မှာ queen n ကောင်ကို — တစ်ကောင်နဲ့ တစ်ကောင် မတိုက်အောင် (row, column, diagonal မထပ်အောင်) ချနိုင်တဲ့ နည်းလမ်း ဘယ်နှမျိုး ရှိလဲ (board အပြည့်အစုံ မဟုတ်ဘဲ အရေအတွက်ကိုသာ ပြန်ပေးမည် — count variant)။

Example 1:

Input: n = 4
Output: 2   (4×4 မှာ မတိုက်အောင် ချနိုင်တဲ့ ပုံစံ ၂ မျိုး)

   . Q . .        . . Q .
   . . . Q        Q . . .
   Q . . .        . . . Q
   . . Q .        . Q . .

ရှင်းလင်းချက်

ဒါက backtracking ရဲ့ classic ပြဿနာပါ။ queen တွေ row တစ်ခုစီမှာ တစ်ကောင်စီ ချရမယ် ဆိုတာ သေချာလို့ — row တစ်ခုစီအတွက် "column ဘယ်ဟာမှာ ချမလဲ" ကို ရွေးရတာ ဖြစ်သည်။

• Base case: row n ရောက် (queen n ကောင် အကုန် ချပြီး) → valid အဖြေ ၁ ခု။
• row တစ်ခုစီ — column တစ်ခုစီကို စမ်း၊ safe ဖြစ်မှ (column / diagonal ၂ ဘက် မထပ်) Choose → Explore (နောက် row) → Undo။
• Pruning — safe မဟုတ်တဲ့ column ကို ချက်ချင်း ကျော် (ဒါက N-Queens ကို brute force ထက် အများကြီး မြန်စေသည်)။

safe စစ်ဖို့ — column တစ်ခုစီ၊ diagonal ၂ မျိုး (row+col တူ = / ၊ row-col တူ = \) သုံးထားသလား မှတ်ထားရင် $O(1)$ နဲ့ စစ်လို့ ရသည်။

Time Complexity: အဆိုးဆုံး $O(n!)$ (row တစ်ခုစီ column ရွေးစရာ လျော့သွား)။
Space Complexity: $O(n)$ - column/diagonal set + recursion depth။

Java Solution

class Solution {
    private int count = 0;

    public int totalNQueens(int n) {
        boolean[] cols = new boolean[n];           // column သုံးပြီးသားလား
        boolean[] diag1 = new boolean[2 * n];      // "\" : row - col + n
        boolean[] diag2 = new boolean[2 * n];      // "/" : row + col
        backtrack(0, n, cols, diag1, diag2);
        return count;
    }

    private void backtrack(int row, int n, boolean[] cols,
                           boolean[] diag1, boolean[] diag2) {
        if (row == n) { count++; return; }         // base case — n ကောင် ချပြီး
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n, d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) continue;  // pruning — တိုက်မယ်
            cols[col] = diag1[d1] = diag2[d2] = true;   // 1. Choose
            backtrack(row + 1, n, cols, diag1, diag2);  // 2. Explore (နောက် row)
            cols[col] = diag1[d1] = diag2[d2] = false;  // 3. Undo
        }
    }
}

Sudoku Solver ဆက်စပ်မှု: Sudoku ဖြေတာလည်း N-Queens နဲ့ idea တူပါတယ် — ကွက်လွတ် တစ်ခုစီမှာ 1–9 တစ်ခုစီ စမ်း (Choose) → row/column/box မထပ်မှ ဆက် (Explore) → မရရင် ပြန်ဖြုတ် (Undo)။ "constraint ဖောက်ရင် ချက်ချင်း prune" တာက ၂ ခုလုံးရဲ့ အသက်ပါ။