Constraint satisfaction — রুটিন, Sudoku আর backtracking

মডিউল ৭-এর আগের পর্বগুলোতে (পর্ব ৩৯ থেকে ৪২) সমস্যাকে দেখা হয়েছে পথ খোঁজা হিসেবে: শুরুর state থেকে action নিয়ে নিয়ে লক্ষ্যে পৌঁছানো। এই পর্বে পথের দাম বা ক্রম গুরুত্বপূর্ণ নয়; দরকার শুধু এমন একটি পূর্ণ উত্তর, যা সব নিয়ম একসঙ্গে মানে: কোন পরীক্ষা কোন দিনে, Sudoku-র কোন ঘরে কোন অঙ্ক, কোন কর্মী কোন শিফটে। Russell ও Norvig-এর পাঠ্যবই “Artificial Intelligence: A Modern Approach” (৪র্থ সংস্করণ) একে পুরো একটি অধ্যায় দিয়েছে; এখানের উদাহরণগুলো নিজেদের বানানো।

১ · CSP কী — variable, domain আর constraint

কলেজের পরীক্ষা কমিটির কথা ভাবুন। চারটি পরীক্ষা (AI, Database, Networking, Math), তিনটি দিন। নিয়মগুলো এমন: যে পরীক্ষাগুলোর ছাত্রছাত্রী এক, সেগুলো একই দিনে নয়; Math-এর শিক্ষক প্রথম দিন নেই; Networking-এর ল্যাব শুধু তৃতীয় দিন খালি। কমিটি একটি তালিকা চায়, যেখানে প্রতিটি পরীক্ষার পাশে একটি দিন লেখা, আর কোনো নিয়ম ভাঙেনি।

এই কাঠামোর তিনটি অংশ:

• Variable X₁, …, X_n: যার মান ঠিক করতে হবে। এখানে চারটি পরীক্ষা: AI, DB, NET, MATH.
• Domain D_i: প্রতিটি variable-এর সম্ভাব্য মানের সেট। এখানে প্রতিটির জন্য {1, 2, 3}, মানে তিনটি দিন।
• Constraint: কোন কোন মানের মিশ্রণ অনুমোদিত। যেমন AI ≠ DB (এক ছাত্রছাত্রী), MATH ≠ 1.

প্রতিটি variable-এ একটি করে মান বসানোকে বলে assignment. সব variable-এ মান বসলে তা complete assignment; কোনো constraint না ভাঙলে consistent. CSP-র সমাধান মানে একটি complete আর consistent assignment. কখনো সমাধান থাকে না; তখন ভালো পদ্ধতির কাজ হলো সেটি প্রমাণ করা।

Constraint-এর তিন রকম

All-different constraint-কে চাইলে জোড়ায় জোড়ায় ≠ দিয়ে ভেঙে লেখা যায়: ৯টি ঘরের জন্য ⁹C₂ = ৩৬টি binary constraint. কিন্তু global রূপে রাখলে solver বেশি বুঝতে পারে। যেমন তিনটি ঘরে যদি শুধু {1, 2} মান বাকি থাকে, জোড়া-জোড়া ≠ দেখে তা ধরা কঠিন, অথচ all-different সরাসরি বলে “তিনজনের জন্য দুটি মান, অসম্ভব”। এ ছাড়া আছে hard constraint (ভাঙা চলবেই না) আর soft constraint বা পছন্দ (ভাঙলে জরিমানা); দ্বিতীয়টি এলে সমস্যাটি optimization-ও হয়ে যায় (অংশ ৯)।

Constraint graph — নিয়মের মানচিত্র

Binary constraint-গুলো একটি graph-এ আঁকা যায়: প্রতিটি variable একটি বিন্দু (node), আর যে দুটি variable-এর মধ্যে constraint আছে, তাদের মধ্যে একটি রেখা (edge). Graph-এর মৌলিক ধারণা (node, edge, adjacency list, degree) DSA কোর্সের graph পর্বে আছে। নিচে এই পর্বের প্রধান উদাহরণ: বাংলাদেশের ৮টি বিভাগ, যেখানে পাশাপাশি দুটি বিভাগে একই রং দেওয়া যাবে না।

রেখাগুলো ঠিক করতে লেখার সময়ে Wikipedia-র জেলাভিত্তিক পাতায় সীমানার বর্ণনা দেখা হয়েছে: যেমন জামালপুরের (ময়মনসিংহ বিভাগ) পশ্চিমে কুড়িগ্রাম, গাইবান্ধা (রংপুর), বগুড়া আর সিরাজগঞ্জ (রাজশাহী); হবিগঞ্জের (সিলেট) পশ্চিমে কিশোরগঞ্জ (ঢাকা) আর ব্রাহ্মণবাড়িয়া (চট্টগ্রাম); ভোলার (বরিশাল) পূর্বে লক্ষ্মীপুর আর নোয়াখালী (চট্টগ্রাম)। ঢাকার degree (প্রতিবেশীর সংখ্যা) ৬, সবচেয়ে বেশি; অংশ ৬-এ এটি কাজে লাগবে।

২ · চারটি সমস্যা, একই ছাঁচে

একই কাঠামোতে চারটি সমস্যা পাশাপাশি। বাজারঘর (এই কোর্সের কাল্পনিক অনলাইন দোকান)-এর রুটিনের নাম আর নিয়ম সব বানানো।

Sudoku-র ৮১০ সংখ্যাটি হাতে বের করা যায়। প্রতিটি ঘরের “প্রতিবেশী” (peer) ২০টি: নিজের সারির আরও ৮টি, কলামের ৮টি, আর বাক্সের যে ৪টি ঘর সারি বা কলামে আগে গোনা হয়নি। ৮১ × ২০ = ১,৬২০, কিন্তু প্রতিটি জোড়া দুবার গোনা হলো, তাই ৮১০টি binary constraint. পরীক্ষার সময়সূচিতে AI < MATH নিয়মটি (Math-এর প্রশ্ন AI পরীক্ষার পরে ছাপা হবে, ধরা যাক) দেখায় যে constraint শুধু ≠ নয়, যেকোনো সম্পর্ক হতে পারে।

৩ · সব মিশ্রণ পরখ করলে কী হয় — generate-and-test-এর বিস্ফোরণ

সবচেয়ে সরল পদ্ধতি হলো সব সম্ভাব্য complete assignment একে একে বানিয়ে প্রতিটি পরীক্ষা করা। একে বলে generate-and-test. n-টি variable, প্রতিটির d-টি মান হলে মোট মিশ্রণ dⁿ. ছোট সমস্যায় চলে, বড়তে নয়। ধরুন একটি কম্পিউটার প্রতি সেকেন্ডে ১০০ কোটি (10⁹) মিশ্রণ পরীক্ষা করতে পারে, যা খুবই উদার অনুমান।

মহাবিশ্বের বয়স মোটামুটি 1.4 × 10¹⁰ বছর। এটাই combinatorial explosion: variable একটি বাড়লে কাজ d গুণ বাড়ে। মূল ভুলটি হলো generate-and-test পুরো assignment বানানোর পরে নিয়ম দেখে। AI-এর উত্তর: আংশিক assignment-এই নিয়ম দেখা। রংপুর লাল আর রাজশাহী লাল হলে বাকি ৬টি বিভাগের 3⁶ = ৭২৯টি মিশ্রণ আর দেখার দরকার নেই; সেই পুরো শাখাটি একবারে কেটে ফেলা যায়।

৪ · CSP-র backtracking search — একবারে একটি variable

CSP-র backtracking-এর ধাপগুলো সহজ:

1. এখনো মান পায়নি এমন একটি variable বাছুন।
2. তার domain থেকে একটি মান নিন, আর যেসব প্রতিবেশী আগেই মান পেয়েছে শুধু তাদের সঙ্গে constraint মিলিয়ে দেখুন।
3. মিললে মানটি বসিয়ে পরের variable-এ যান (recursion). না মিললে পরের মান।
4. কোনো মানই না চললে এই variable থেকে ফিরে আসুন (backtrack): আগের variable-এর মান তুলে নিয়ে তার পরের মান চেষ্টা করুন।

দুটি পর্যবেক্ষণ এটিকে generate-and-test থেকে আলাদা করে। এক, CSP-তে variable-এর ক্রম বদলালেও সমাধান বদলায় না (assignment commutative), তাই প্রতিটি স্তরে শুধু একটি variable নিয়ে ভাবলেই চলে; এতে search tree-র পাতা dⁿ-এর বেশি হয় না, n!·dⁿ নয়। দুই, নিয়ম ভাঙলেই পুরো শাখা কাটা পড়ে। এটি আসলে depth-first search, যেখানে গভীরতা = কতগুলো variable মান পেয়েছে।

নিচের কোড বিভাগের মানচিত্রে এই সাধারণ backtracking চালায়। তিনটি সংখ্যা গোনা হয়: tried (কতবার একটি রং চেষ্টা করা হলো), checks (কতবার একটি প্রতিবেশীর রঙের সঙ্গে মেলানো হলো) আর backtracks (একটি বসানো রং কতবার তুলে নিতে হলো)। একই সমস্যা তিনভাবে চালানো হয়েছে: পশ্চিম থেকে পূর্বের একটি নির্দিষ্ট ক্রমে, ঢাকাকে প্রথমে রেখে, আর মাত্র দুটি রং দিয়ে। এই ব্লকে শুধু Python-এর মৌলিক অংশ; প্রথমবার চালালে ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে।

EDGES = """Rangpur-Rajshahi Rangpur-Mymensingh Rajshahi-Mymensingh Rajshahi-Dhaka
Rajshahi-Khulna Khulna-Dhaka Khulna-Barishal Barishal-Dhaka Barishal-Chattogram
Dhaka-Chattogram Dhaka-Sylhet Dhaka-Mymensingh Mymensingh-Sylhet Sylhet-Chattogram"""
nb = {}                                   # constraint graph: neighbours
for e in EDGES.split():
    a, b = e.split("-")
    nb.setdefault(a, set()).add(b)
    nb.setdefault(b, set()).add(a)

def solve(order, colors):
    asg, st = {}, {"tried": 0, "checks": 0, "backtracks": 0}
    def bt(i):
        if i == len(order):
            return True
        var = order[i]
        for c in colors:
            st["tried"] += 1
            used = [asg[n] for n in nb[var] if n in asg]   # assigned neighbours
            st["checks"] += len(used)
            if c in used:
                continue                  # violates a constraint: next colour
            asg[var] = c
            if bt(i + 1):
                return True
            del asg[var]                  # undo = one backtrack
            st["backtracks"] += 1
        return False
    return (dict(asg) if bt(0) else None), st
w2e = ["Rangpur", "Rajshahi", "Khulna", "Barishal",
       "Chattogram", "Sylhet", "Mymensingh", "Dhaka"]
for name, order, k in [("west->east, 3 colours", w2e, 3),
                       ("Dhaka first, 3 colours", ["Dhaka"] + w2e[:-1], 3),
                       ("west->east, 2 colours", w2e, 2)]:
    sol, st = solve(order, ["red", "green", "blue"][:k])
    print(name, st, "\n  ", sol)

west->east, 3 colours {'tried': 125, 'checks': 375, 'backtracks': 36}
   {'Rangpur': 'red', 'Rajshahi': 'green', 'Khulna': 'blue', 'Barishal': 'green', 'Chattogram': 'blue', 'Sylhet': 'green', 'Mymensingh': 'blue', 'Dhaka': 'red'}
Dhaka first, 3 colours {'tried': 17, 'checks': 36, 'backtracks': 0}
   {'Dhaka': 'red', 'Rangpur': 'red', 'Rajshahi': 'green', 'Khulna': 'blue', 'Barishal': 'green', 'Chattogram': 'blue', 'Sylhet': 'green', 'Mymensingh': 'blue'}
west->east, 2 colours {'tried': 26, 'checks': 32, 'backtracks': 12}
   None

৫ · Forward checking — ভবিষ্যতের ব্যর্থতা আগে দেখা

সাধারণ backtracking শুধু পেছনে তাকায়: “আগে যারা মান পেয়েছে, তাদের সঙ্গে মিলছে তো?” কিন্তু ঢাকার সমস্যাটি দেখা গেল অনেক পরে। Forward checking সামনে তাকায়: একটি variable-এ মান বসানোর সঙ্গে সঙ্গে তার যেসব প্রতিবেশী এখনো মান পায়নি, তাদের domain থেকে অসঙ্গত মানগুলো মুছে ফেলে। কোনো প্রতিবেশীর domain খালি হয়ে গেলে সঙ্গে সঙ্গে বোঝা যায় এই পথে সমাধান নেই, আর তখনই ফিরে আসা যায়।

নিচের stepper পশ্চিম থেকে পূর্বের সেই একই ক্রমে forward checking চালায়। R = লাল, G = সবুজ, B = নীল; “=R” মানে মান বসানো হয়েছে, বাকিগুলো domain-এ যা অবশিষ্ট। প্রতিটি ধাপে রং বেছে নেওয়া হয় domain-এর ক্রমে (R, তারপর G, তারপর B).

1var = next in fixed order2val = next value in dom[var]3remove val from free neighbours4if a domain is empty: undo

ধাপ ৩-এর ঘটনাটি মনে রাখুন: forward checking দুটি খালি variable-এর মধ্যের বিরোধ দেখে না। ঢাকা {B} আর ময়মনসিংহ {B} পাশাপাশি মানে নিশ্চিত ব্যর্থতা; এটি ধরে arc consistency (অংশ ৭)। তবু forward checking সস্তা, প্রতিবার শুধু প্রতিবেশীদের একবার দেখা।

৬ · কোন variable আগে, কোন মান আগে — MRV, degree আর LCV

অংশ ৪-এর আউটপুট বলেছে, ক্রম বদলালেই কাজ সাত গুণ কমে। কিন্তু প্রতিটি সমস্যার জন্য হাতে ভালো ক্রম খোঁজা চলে না। তিনটি সাধারণ heuristic (অনুমাননির্ভর নিয়ম) সব CSP-তে কাজে লাগে।

একটি আপাত-বিরোধ: variable বাছাইয়ে “সবচেয়ে কঠিনটি আগে”, অথচ মান বাছাইয়ে “সবচেয়ে সহজটি আগে”। কারণ প্রতিটি variable-কে শেষ পর্যন্ত মান পেতেই হবে, তাই কঠিনটির ব্যর্থতা যত আগে ধরা পড়ে তত কম কাজ নষ্ট; কিন্তু মানগুলোর মধ্যে শুধু একটিকে সফল হতে হবে, তাই সম্ভাব্য সফলটি আগে। (সব সমাধান খুঁজতে হলে বা সমাধান না থাকলে মানের ক্রমে লাভ নেই, কারণ সব মানই দেখতে হয়।)

নিচের stepper বিভাগের মানচিত্রে MRV + degree আর forward checking একসঙ্গে চালায়। প্রতিটি ঘরে লেখা “বাকি মানের সংখ্যা · d খালি প্রতিবেশীর সংখ্যা”; সমান হলে তালিকার আগের নাম (রংপুর, রাজশাহী, খুলনা, বরিশাল, চট্টগ্রাম, সিলেট, ময়মনসিংহ, ঢাকা ক্রমে)। ← চিহ্ন দেওয়া variable-টি এই ধাপে বাছা হলো।

1cands = free vars with fewest values2tie: most free neighbours (degree)3assign first value, forward check

LCV-এর একটি হাতে হিসাব

পরীক্ষার সময়সূচিতে unary constraint প্রয়োগের পর domain: AI {1, 2, 3}, DB {1, 2, 3}, NET {3}, MATH {2, 3}. ধরুন AI-কে আগে বাছা হলো। AI-এর প্রতিবেশী DB (≠) আর MATH (AI < MATH). প্রতিটি মান প্রতিবেশীদের থেকে কয়টি মান মোছে:

• AI = 1: MATH-এর {2, 3} দুটিই 1-এর বড়, কিছু মোছে না; DB থেকে 1 মোছে। মোট ১টি।
• AI = 2: MATH থেকে 2 মোছে (2 < 2 নয়); DB থেকে 2. মোট ২টি।
• AI = 3: MATH-এর দুটিই মোছে (খালি!), DB থেকে 3. মোট ৩টি।

তাই LCV-এর ক্রম 1, 2, 3, আর অংশ ৭-এ দেখবেন একমাত্র সমাধানে AI = 1. তবে LCV-এর হিসাবেও constraint check লাগে; বড় domain-এ এর খরচ কখনো লাভ ছাড়িয়ে যায়, তাই অনেক solver মান সাজাতে সস্তা নিয়ম বা কিছুটা randomness ব্যবহার করে।

Sudoku-তে MRV + forward checking বনাম সাধারণ backtracking

এবার একই কৌশল Sudoku-তে। নিচের ধাঁধাটি (৩২টি clue) এই পর্বের জন্য seed দেওয়া Python কোড দিয়ে বানানো: প্রথমে একটি পূর্ণ গ্রিড, তারপর এলোমেলো ক্রমে ঘর খালি করা, যতক্ষণ উত্তর একটিমাত্র থাকে। কোনো বই বা ওয়েবসাইট থেকে নেওয়া নয়। ৮১টি অক্ষরের লেখায় প্রতি ৯টি অক্ষর এক সারি, . মানে খালি ঘর। plain সারি ধরে ধরে ঘর ভরে; mrv_fc প্রতিবার সবচেয়ে কম বিকল্পের ঘর বাছে আর বসানোর পর peer-দের domain ছাঁটে।

P = "....4.3.5..2....9....5.98..6.......9..8.941..4..1..23..8...1.53..3.25..1..53.8972"
C = range(81)
peers = [{j for j in C if j != i and (j // 9 == i // 9 or j % 9 == i % 9
          or (j // 27, j % 9 // 3) == (i // 27, i % 9 // 3))} for i in C]
st = {"plain": [0, 0], "mrv+fc": [0, 0]}          # [values placed, backtracks]
def plain(g, i=0):                                 # row by row, fixed order
    if i == 81: return True
    if g[i]: return plain(g, i + 1)
    for v in range(1, 10):
        if all(g[j] != v for j in peers[i]):       # check against filled peers
            st["plain"][0] += 1
            g[i] = v
            if plain(g, i + 1): return True
            g[i] = 0
            st["plain"][1] += 1                    # undo = backtrack
    return False

def mrv_fc(dom, free):
    if not free: return dom
    i = min(sorted(free), key=lambda k: len(dom[k]))   # MRV
    for v in sorted(dom[i]):
        st["mrv+fc"][0] += 1
        new = [d - {v} if j in peers[i] else d.copy() for j, d in enumerate(dom)]
        new[i] = {v}                                   # forward checking above
        if all(new[j] for j in peers[i] & free) and (res := mrv_fc(new, free - {i})):
            return res
        st["mrv+fc"][1] += 1
    return None
g = [int(c) if c != "." else 0 for c in P]
dom = [{g[i]} if g[i] else set(range(1, 10)) - {g[j] for j in peers[i]} for i in C]
res = mrv_fc(dom, {i for i in C if not g[i]})
print("clues:", 81 - P.count("."), "| plain solved:", plain(g))
print("same answer:", [min(d) for d in res] == g, "| row 1:", g[:9])
for k, (placed, back) in st.items():
    print(f"{k:7} placed={placed:5}  backtracks={back:5}")

clues: 32 | plain solved: True
same answer: True | row 1: [8, 6, 9, 7, 4, 2, 3, 1, 5]
plain   placed= 7996  backtracks= 7947
mrv+fc  placed=   49  backtracks=    0

৭ · Arc consistency আর AC-3 — নিয়মের ঢেউ ছড়ানো

অংশ ৫-এর ধাপ ৩-এ forward checking যা দেখেনি, তা ধরার জন্য একটি শক্তিশালী ধারণা: arc consistency. একটি binary constraint-কে দুই দিকের দুটি “arc” হিসেবে দেখুন: X → Y আর Y → X. X → Y arc consistent মানে X-এর domain-এর প্রতিটি মানের জন্য Y-এর domain-এ অন্তত একটি মান আছে, যার সঙ্গে নিয়মটি মানে। এমন সঙ্গী (support) না থাকলে X-এর সেই মানটি কোনো সমাধানে আসতে পারে না, তাই মুছে ফেলা নিরাপদ। এই মোছার কাজটিকে বলে revise.

একটি মান মুছলে যারা সেই মানের ওপর নির্ভর করছিল, তাদের আবার দেখতে হয়; এই ঢেউ ছড়ানোকে বলে constraint propagation.

AC-3-এর কাজ: সব arc একটি queue-তে রাখা। একটি করে arc (X_i, X_j) বের করে revise. কিছু মুছলে X_i-এর দিকে তাকানো সব arc (X_k, X_i), X_j ছাড়া, আবার queue-তে (আগে থেকে থাকলে আর নয়)। কোনো domain খালি হলে সমস্যাটির সমাধান নেই। queue খালি হলে সব arc consistent. নিচে পরীক্ষার সময়সূচিতে পুরো trace. সংক্ষেপে A = AI, D = DB, N = NET, M = MATH; unary constraint আগেই প্রয়োগ করা।

1queue = all arcs2while queue:3    Xi, Xj = queue.popleft()4    if revise(Xi, Xj):5        if not dom[Xi]: return False6        add (Xk, Xi), Xk != Xj7return True

সাধারণত AC-3 একা সমাধান দেয় না; domain ছোট করে, তারপর search লাগে। তখন দুটি উপায়: search-এর আগে একবার AC-3 (preprocessing), অথবা প্রতিটি মান বসানোর পর সেই variable থেকে শুরু করে AC-3 চালানো। দ্বিতীয়টির নাম MAC (maintaining arc consistency), আর অংশ ৮-এর তুলনায় “MRV + MAC(AC-3)” মানে এটাই। খরচের হিসাব: e-টি binary constraint আর সর্বোচ্চ d আকারের domain হলে AC-3-এর খারাপতম সময় O(e·d³): প্রতিটি arc বড়জোর d বার queue-তে ফেরে (arc-টি যে variable-এর দিকে নির্দেশ করে, তার domain থেকে অন্তত একটি মান মুছলে তবেই ফেরে), আর একটি revise-এ d × d জোড়া দেখা লাগে।

from collections import deque

def ac3(dom, cons):
    arcs = {}
    for (x, y), f in cons.items():                 # each constraint = two arcs
        arcs[(x, y)] = f
        arcs[(y, x)] = lambda b, a, f=f: f(a, b)
    queue, revisions = deque(arcs), 0
    while queue:
        xi, xj = queue.popleft()
        revisions += 1
        bad = {a for a in dom[xi] if not any(arcs[xi, xj](a, b) for b in dom[xj])}
        if bad:
            dom[xi] -= bad                         # revise: drop unsupported values
            if not dom[xi]:
                return False, revisions
            for (xk, xl) in arcs:                  # re-check arcs pointing at xi
                if xl == xi and xk != xj and (xk, xi) not in queue:
                    queue.append((xk, xi))
    return True, revisions

def exam_csp():
    dom = {"AI": {1, 2, 3}, "DB": {1, 2, 3}, "NET": {3}, "MATH": {2, 3}}  # unary done
    cons = {("AI", "MATH"): lambda a, m: a < m,    # AI exam before Math
            ("AI", "DB"): lambda a, b: a != b,     # shared students
            ("DB", "NET"): lambda a, b: a != b,
            ("NET", "MATH"): lambda a, b: a != b}
    return dom, cons

dom, cons = exam_csp()
print("before:", dom)
print("ok, revisions:", ac3(dom, cons), "\nafter: ", dom)
dom, cons = exam_csp()
cons[("DB", "MATH")] = lambda a, b: a != b         # one more clash rule
print("with DB != MATH:", ac3(dom, cons), dom)

before: {'AI': {1, 2, 3}, 'DB': {1, 2, 3}, 'NET': {3}, 'MATH': {2, 3}}
ok, revisions: (True, 12)
after:  {'AI': {1}, 'DB': {2}, 'NET': {3}, 'MATH': {2}}
with DB != MATH: (False, 12) {'AI': set(), 'DB': {1}, 'NET': {3}, 'MATH': {2}}

৮ · সত্যিকারের তুলনা — Sudoku, n-queens আর min-conflicts

এবার চারটি পদ্ধতি একই কোডের কাঠামোয় পাশাপাশি: (১) সাধারণ backtracking, নির্দিষ্ট ক্রম; (২) তার সঙ্গে MRV; (৩) MRV + forward checking; (৪) MRV + MAC, মানে প্রতিবার AC-3. প্রতিটি সংখ্যা একটি ল্যাপটপে সত্যিকারের run থেকে (লেখার সময়ে Python 3.14.4, শুধু standard library, একটি run). Sudoku-র তিনটি ধাঁধাই একই seed-এর একটি পূর্ণ গ্রিড থেকে ঘর মুছে বানানো, প্রতিটির উত্তর একটিই: সহজ (৪০টি clue, AC-3 একাই সমাধান করে), মাঝারি (৩২টি, AC-3 একা ৮১টির ৪৪টি ঘর ঠিক করে) আর কঠিন (২৫টি, এর কোনো clue মুছলে উত্তর আর একটি থাকে না)। placed = বসানো মান, backtracks = তুলে নেওয়া মান, checks = দুটি মানের মধ্যে constraint যাচাইয়ের সংখ্যা।

সারণির কঠিন-২৫ অংশের আসল terminal আউটপুট (সত্যিকারের run, path বদলে নিরপেক্ষ নাম):

~/bazarghar-csp$ python compare.py
Python 3.14.4
…
Sudoku hard-25
method          │     placed │ backtracks │       checks │     time │
plain BT        │  1,609,537 │  1,609,481 │   94,122,597 │   19.58s │ ok
BT + MRV        │         76 │         20 │      108,495 │    0.02s │ ok
MRV + FC        │         76 │         20 │        3,670 │    0.00s │ ok
MRV + MAC(AC-3) │         58 │          2 │       35,945 │    0.01s │ ok
…

সংখ্যাগুলো কী বলে

• কঠিন ধাঁধায় পার্থক্য বিশাল: ১৬ লাখ backtrack আর প্রায় ২০ সেকেন্ড বনাম ২০টি বা ২টি। সহজ ধাঁধায় সাধারণ backtracking-ও চলেছে; কঠিনতা কয়েকটি clue-তে হঠাৎ লাফ দেয়।
• MRV আর MRV + FC-র placed আর backtracks একই। কারণ এখানে forward checking ছাড়া MRV-কে নিজেই প্রতিটি খালি ঘরের বৈধ মান গুনতে হয়; সে একই ঘর বাছে, একই ক্রমে। পার্থক্য খরচে: ১,০৮,৪৯৫ বনাম ৩,৬৭০ check, কারণ forward checking domain মনে রাখে, প্রতিবার নতুন করে গোনে না।
• MAC সবচেয়ে কম ভুল করে, কিন্তু বেশি check করে। কঠিন-২৫-এ মাত্র ২টি backtrack, কিন্তু forward checking-এর প্রায় দশ গুণ check. কোনটি দ্রুত, তা সমস্যা আর implementation-এর ওপর নির্ভর করে; এই ছোট পরীক্ষায় দুটিই এক সেকেন্ডের অনেক নিচে।
• n-queens-এ MRV একা কম কাজের। 8-queens-এ সাধারণ backtracking-এর ২,৪৩৮ check-এর চেয়ে “+ MRV”-এর ৬,৮৫০ বেশি: শুরুতে সব সারির domain সমান, আর বৈধ মান গোনার খরচ লাভকে ছাড়িয়ে গেছে। 20-queens-এ অবশ্য MRV ১,৯৯,৬১৫টি backtrack-কে ১২৫-এ নামিয়েছে।
• সতর্কতা: একটি যন্ত্রে, একটি run-এ, এই পর্বের সরল কোডে পাওয়া সংখ্যা, সাধারণ নিয়ম নয়; ধাঁধা বা ক্রম বদলালে সংখ্যা বদলাবে।

Min-conflicts — পুরো বোর্ড বসিয়ে মেরামত

সম্পূর্ণ ভিন্ন একটি পথ আছে। আংশিক assignment থেকে না শুরু করে, শুরুতেই সব variable-এ এলোমেলো মান বসান, তারপর মেরামত করুন: যে variable নিয়ম ভাঙছে, এমন একটি এলোমেলোভাবে বাছুন, আর তাকে এমন মান দিন যাতে সবচেয়ে কম বিরোধ (conflict) হয়। একে বলে min-conflicts, আর এটি local search-এর একটি রূপ, যার পুরো পরিবার (hill climbing, simulated annealing) পর্ব ৪৪-এ। Minton ও সহকর্মীদের ১৯৯০-এর দশকের শুরুর গবেষণায় দেখানো হয়েছিল যে বড় n-queens-এ এটি বিস্ময়করভাবে দ্রুত, আর এই ধারণা Hubble Space Telescope-এর পর্যবেক্ষণ-সূচির কাজের সঙ্গে যুক্ত ছিল বলে উল্লেখ পাওয়া যায়।

নিচের কোড n-queens-এ দুই পথই চালায়: সাধারণ backtracking আর MRV + forward checking (অংশ ৮-এর সারণির মতো একই গণনা), তারপর min-conflicts. প্রতিটি সারি একটি variable, কলাম তার মান।

import random
def safe(r1, c1, r2, c2):
    return c1 != c2 and abs(c1 - c2) != abs(r1 - r2)

def backtrack(n, mrv):            # rows are variables, columns are values
    count = {"placed": 0, "backtracks": 0}
    def go(dom, asg):
        if len(asg) == n: return asg
        free = [r for r in range(n) if r not in asg]
        r = min(free, key=lambda x: len(dom[x])) if mrv else free[0]
        for c in dom[r]:
            if not all(safe(r, c, r2, c2) for r2, c2 in asg.items()): continue
            count["placed"] += 1
            new = {x: [v for v in dom[x] if safe(r, c, x, v)] if x in free else dom[x]
                   for x in range(n)} if mrv else dom     # forward checking
            if all(new[x] for x in free if x != r) and go(new, {**asg, r: c}):
                return True
            count["backtracks"] += 1
    go({x: list(range(n)) for x in range(n)}, {})
    return count
def min_conflicts(n, seed=42, max_steps=5000):
    rng = random.Random(seed)
    q = [rng.randrange(n) for _ in range(n)]       # random full assignment
    hits = lambda r, c: sum(1 for r2 in range(n) if r2 != r and not safe(r, c, r2, q[r2]))
    for step in range(max_steps):
        bad = [r for r in range(n) if hits(r, q[r])]
        if not bad: return step
        r = rng.choice(bad)                        # a conflicted queen
        costs = [hits(r, c) for c in range(n)]
        q[r] = rng.choice([c for c in range(n) if costs[c] == min(costs)])
    return None
for n in (8, 12, 20):
    print(n, "plain:", backtrack(n, False) if n <= 12 else "skip", "| MRV+FC:", backtrack(n, True))
for n in (8, 20, 50):
    print(f"min-conflicts n={n}: solved after {min_conflicts(n)} steps")

8 plain: {'placed': 113, 'backtracks': 105} | MRV+FC: {'placed': 75, 'backtracks': 67}
12 plain: {'placed': 261, 'backtracks': 249} | MRV+FC: {'placed': 153, 'backtracks': 141}
20 plain: skip | MRV+FC: {'placed': 145, 'backtracks': 125}
min-conflicts n=8: solved after 111 steps
min-conflicts n=20: solved after 33 steps
min-conflicts n=50: solved after 74 steps

ডেস্কটপে কলাম আর দুই কর্ণের রানির সংখ্যা আলাদা তালিকায় রেখে (তাতে একটি ঘরের বিরোধ O(1)-এ জানা যায়) একই কৌশল। সত্যিকারের run (Python 3.14.4, seed 42, একটি run):

~/bazarghar-csp$ python minconf.py
Python 3.14.4
n=     8  start conflicts=    10  steps=    15  time=0.00s
n=    20  start conflicts=    20  steps=    24  time=0.00s
n=   100  start conflicts=   112  steps=   161  time=0.00s
n=  1000  start conflicts=  1149  steps=   744  time=0.08s
n= 10000  start conflicts= 11630  steps=  6236  time=6.08s

দশ হাজার রানি, শুরুতে ১১,৬৩০ জোড়া বিরোধ, ৬,২৩৬টি মেরামতে সমাধান। ধাপের সংখ্যা মোটামুটি n-এর সমানুপাতে বাড়ছে, যা আগের গবেষণার পর্যবেক্ষণের সঙ্গে মেলে; সময় বেশি বাড়ছে কারণ প্রতিটি ধাপে n-টি কলাম দেখা হয়। একই শর্তে 20-queens-এ সাধারণ backtracking-এর লেগেছিল প্রায় দুই লাখ backtrack. তবে min-conflicts-এর completeness নেই (incomplete): সমাধান না থাকলে সে চিরকাল ঘুরবে, “সমাধান নেই” প্রমাণ করতে পারে না; backtracking পারে (অংশ ৪-এর দুই রঙের উদাহরণ)।

৯ · বাস্তবের constraint solver — বাজারঘরের রুটিন CP-SAT দিয়ে

বাস্তবের রুটিন, সময়সূচি বা উৎপাদন-পরিকল্পনায় সাধারণত কেউ নিজের backtracking লেখেন না। সমস্যাটি একটি solver-এর ভাষায় লেখা হয় (modelling), আর solver নিজের ভেতরে propagation, search, ব্যর্থতা থেকে শেখা আর অনেক কৌশল চালায়। একটি পরিচিত বিনামূল্যের, open source বিকল্প Google-এর OR-Tools প্যাকেজের CP-SAT solver, যা constraint programming আর SAT solver-এর কৌশল মেলায়। লেখার সময়ে PyPI-তে সর্বশেষ সংস্করণ ortools 9.15.6755.

বাজারঘরের গুদামের সাপ্তাহিক রুটিন (সব নাম আর নিয়ম বানানো): পাঁচজন কর্মী, Anika, Babul, Chumki, Dipu আর Eti; শনি থেকে শুক্র সাত দিন, প্রতিদিন সকাল (M) আর সন্ধ্যা (E) শিফট। কঠিন নিয়মগুলো অংশ ২-এর সারণিতে। নরম পছন্দ: Chumki শুক্রবার ছুটি চান (ভাঙলে জরিমানা ৩), Dipu সকালের শিফট পছন্দ করেন (প্রতি সন্ধ্যায় ২), Eti শনিবার ছুটি চান (৩); আর সবার শিফট-সংখ্যা যেন কাছাকাছি থাকে (সর্বোচ্চ আর সর্বনিম্নের পার্থক্যে ৪ গুণ জরিমানা)। solver মোট জরিমানা সবচেয়ে কম করবে।

from ortools.sat.python import cp_model
import ortools

staff = ["Anika", "Babul", "Chumki", "Dipu", "Eti"]
senior = {"Anika", "Babul", "Chumki"}
days = ["Sat", "Sun", "Mon", "Tue", "Wed", "Thu", "Fri"]
shifts = ["M", "E"]                        # morning, evening
need = {(d, s): 2 for d in days for s in shifts}
need[("Fri", "M")] = 1                     # Friday morning is quiet

m = cp_model.CpModel()
x = {(p, d, s): m.new_bool_var(f"{p}_{d}_{s}")
     for p in staff for d in days for s in shifts}

# hard constraints
for d in days:
    for s in shifts:
        m.add(sum(x[p, d, s] for p in staff) == need[d, s])
        m.add(sum(x[p, d, s] for p in senior) >= 1)     # a senior on every shift
    for p in staff:
        m.add(x[p, d, "M"] + x[p, d, "E"] <= 1)          # one shift a day
for p in staff:
    m.add(sum(x[p, d, s] for d in days for s in shifts) <= 6)
    for i in range(len(days) - 1):                       # no evening -> next morning
        m.add(x[p, days[i], "E"] + x[p, days[i + 1], "M"] <= 1)

# soft preferences (penalty weights)
pen = []
pen += [3 * x["Chumki", "Fri", s] for s in shifts]       # Chumki: Friday off
pen += [2 * x["Dipu", d, "E"] for d in days]             # Dipu: prefers mornings
pen += [3 * x["Eti", "Sat", s] for s in shifts]          # Eti: Saturday off
load = {p: sum(x[p, d, s] for d in days for s in shifts) for p in staff}
hi, lo = m.new_int_var(0, 14, "hi"), m.new_int_var(0, 14, "lo")
m.add_max_equality(hi, list(load.values()))
m.add_min_equality(lo, list(load.values()))
m.minimize(sum(pen) + 4 * (hi - lo))                     # fairness

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
solver.parameters.num_workers = 1
solver.parameters.random_seed = 42
st = solver.solve(m)
print("ortools", ortools.__version__, "| status:", solver.status_name(st))
print("objective:", solver.objective_value, "| bound:", solver.best_objective_bound)
print("       " + "  ".join(f"{d:>5}" for d in days) + "  total")
for p in staff:
    row = []
    for d in days:
        row.append("".join(s for s in shifts if solver.value(x[p, d, s])) or "-")
    print(f"{p:<7}" + "  ".join(f"{c:>5}" for c in row) + f"  {solver.value(load[p]):>5}")
print("Dipu evenings:", sum(solver.value(x["Dipu", d, "E"]) for d in days),
      "| Chumki Fri:", sum(solver.value(x["Chumki", "Fri", s]) for s in shifts),
      "| Eti Sat:", sum(solver.value(x["Eti", "Sat", s]) for s in shifts))
print(f"wall time: {solver.wall_time:.3f}s, branches: {solver.num_branches}, conflicts: {solver.num_conflicts}")

প্রথম চেষ্টায় সিনিয়র ছিলেন শুধু Anika আর Babul. সত্যিকারের run-এর প্রথম লাইন:

~/bazarghar-csp$ python rota_v1.py
ortools 9.15.6755 | status: INFEASIBLE
…

Solver বলছে কোনো সমাধান নেই, আর হাতে হিসাব করলে কারণটি সরল: ১৪টি শিফটের প্রতিটিতে অন্তত একজন সিনিয়র চাই, কিন্তু দুজন সিনিয়র সপ্তাহে সর্বোচ্চ ৬টি করে, মোট ১২টি শিফট করতে পারেন। ১৪ > ১২. (INFEASIBLE অবস্থায় variable-এর মান অর্থহীন; সেই run-এর বাকি আউটপুট ছিল আবর্জনা সংখ্যা, তাই আগে status.) Chumki-কে সিনিয়র ধরা হলো (উপরের কোড)। সত্যিকারের run (Python 3.14.4, ortools 9.15.6755, এক worker, seed 42):

~/bazarghar-csp$ python rota_cpsat.py
ortools 9.15.6755 | status: OPTIMAL
objective: 4.0 | bound: 4.0
         Sat    Sun    Mon    Tue    Wed    Thu    Fri  total
Anika      E      E      -      E      E      -      M      5
Babul      M      M      M      M      -      M      E      6
Chumki     E      E      E      -      M      E      -      5
Dipu       M      -      M      M      M      M      -      5
Eti        -      M      E      E      E      E      E      6
Dipu evenings: 0 | Chumki Fri: 0 | Eti Sat: 0
wall time: 0.027s, branches: 791, conflicts: 4

ছোট সমস্যার জন্য আরও হালকা একটি Python library আছে: python-constraint, যার রক্ষণাবেক্ষণ-করা সংস্করণ লেখার সময়ে PyPI-তে python-constraint2 2.9.0 নামে (import করার নাম constraint). বিভাগের মানচিত্রে এটি দিয়ে সব সমাধান গোনা হলো:

from importlib.metadata import version
from constraint import Problem, AllDifferentConstraint

edges = [("Rangpur", "Rajshahi"), ("Rangpur", "Mymensingh"), ("Rajshahi", "Mymensingh"),
         ("Rajshahi", "Dhaka"), ("Rajshahi", "Khulna"), ("Khulna", "Dhaka"),
         ("Khulna", "Barishal"), ("Barishal", "Dhaka"), ("Barishal", "Chattogram"),
         ("Dhaka", "Chattogram"), ("Dhaka", "Sylhet"), ("Dhaka", "Mymensingh"),
         ("Mymensingh", "Sylhet"), ("Sylhet", "Chattogram")]
divisions = sorted({v for e in edges for v in e})

for k in (2, 3, 4):
    p = Problem()
    p.addVariables(divisions, list(range(k)))
    for a, b in edges:
        p.addConstraint(AllDifferentConstraint(), [a, b])
    sols = p.getSolutions()
    print(f"{k} colours: {len(sols)} solutions")
print("python-constraint2", version("python-constraint2"))
p = Problem()
p.addVariables(divisions, ["red", "green", "blue"])
for a, b in edges:
    p.addConstraint(lambda x, y: x != y, [a, b])
p.addConstraint(lambda d: d == "red", ["Dhaka"])          # unary constraint
print(p.getSolution())

সত্যিকারের run:

~/bazarghar-csp$ python map_pc.py
2 colours: 0 solutions
3 colours: 6 solutions
4 colours: 528 solutions
python-constraint2 2.9.0
{'Dhaka': 'red', 'Mymensingh': 'blue', 'Rajshahi': 'green', 'Barishal': 'green', 'Chattogram': 'blue', 'Khulna': 'blue', 'Sylhet': 'green', 'Rangpur': 'red'}

দুই রঙে ০টি সমাধান (অংশ ৪-এর প্রমাণের সঙ্গে মেলে), তিন রঙে ঠিক ৬টি। ৬ = 3!, মানে তিনটি রঙের নাম অদলবদলের বাইরে আসলে একটিই রং-বিন্যাস: ঢাকা আর রংপুর এক রঙে, চক্রের ছয়টি বিভাগ পালা করে বাকি দুই রঙে। চার রঙে ৫২৮টি। শেষ লাইনে ঢাকা = red একটি unary constraint হিসেবে যোগ করা হয়েছে, আর solver একটি সমাধান দিয়েছে।

১০ · AI-এর যুগে — AI সহকারী দিয়ে রুটিনের model লেখা

“আমার দোকানের শিফট রুটিন বানাও” বললে AI সহকারী দ্রুত একটি OR-Tools বা python-constraint কোড দেবে। কিন্তু constraint-এর কোডে ভুল প্রায়ই নীরব: solver যা বলা হয়েছে তা-ই নিখুঁতভাবে সমাধান করে, অথচ যা বলা হয়েছে তা-ই ভুল। আর ভাষার মডেল সরাসরি “মাথায়” এমন ধাঁধা সমাধান করতে গেলে নিয়ম-ভাঙা উত্তরও আত্মবিশ্বাসের সঙ্গে দিতে পারে। ভালো ভাগাভাগি: AI সহকারী model লিখতে সাহায্য করুক, solver সমাধান করুক, আর আপনার যাচাই-কোড প্রতিটি নিয়ম আলাদা পরীক্ষা করুক। AI সহকারীরা এ ধরনের কাজে প্রায়ই যা করে:

• একটি নিয়ম বাদ দেওয়া বা উল্টে লেখা: “সন্ধ্যার পরদিন সকালে নয়” বাদ, বা <=-এর জায়গায় >=; solver তখন খুশিমনে নিয়ম-ভাঙা রুটিন “OPTIMAL” বলবে।
• পুরোনো বা বানানো API: OR-Tools-এর পুরোনো CamelCase নাম (NewBoolVar, Solve) আর নতুন snake_case নাম (new_bool_var, solve) মিশিয়ে ফেলা, বা অস্তিত্বহীন method বানানো; python-constraint আর python-constraint2 প্যাকেজ গুলিয়ে ফেলা।
• status না দেখে ফল পড়া: INFEASIBLE বা সময় ফুরিয়ে যাওয়া অবস্থায় variable-এর মান ছাপানো, যেমন অংশ ৯-এর প্রথম run-এর আবর্জনা সংখ্যা।
• FEASIBLE-কে OPTIMAL বলা: সময়-সীমায় থামা solver-এর ফলকে objective আর bound-এর ফাঁক না দেখে “সেরা রুটিন” বলা।
• জরিমানার ওজন চুপচাপ বসানো: কার পছন্দ কত দামি, তা মূল্যবোধের সিদ্ধান্ত, প্রশ্ন না করে মেনে নেওয়ার নয়।

AI-এর লেখা constraint model হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি কঠিন নিয়ম কোডের কোন লাইনে, তা একে একে মিলিয়েছি; কোনো নিয়ম বাদ বা উল্টো নেই
• Solver-এর ফল একটি আলাদা, সরল যাচাই-function দিয়ে পরীক্ষা করেছি, যা solver-এর কোড ব্যবহার করে না
• Status (OPTIMAL, FEASIBLE, INFEASIBLE) দেখে তবেই ফল পড়েছি; objective আর bound-এর ফাঁক দেখেছি
• একটি ছোট, হাতে সমাধান করা যায় এমন উদাহরণে (যেমন ৩ জন, ২ দিন) solver-এর উত্তর হাতের হিসাবের সঙ্গে মিলিয়েছি
• নিজের version-এর অফিসিয়াল docs-এ প্রতিটি অচেনা method দেখেছি; প্যাকেজের নাম আর version pip দিয়ে নিশ্চিত করেছি
• নরম পছন্দের ওজন যাঁদের রুটিন, তাঁদের সঙ্গে আলোচনা করে ঠিক করেছি; আসল কর্মীর নাম বা ব্যক্তিগত তথ্য AI-তে পেস্ট করিনি