ব্যাকট্র্যাকিং প্যারাডাইম ও N-Queens

১ · ব্যাকট্র্যাকিং প্যারাডাইম কী

ব্যাকট্র্যাকিংBacktrackingএকটি সমস্যার সমাধান ধাপে ধাপে (একটি একটি করে চয়েস) তৈরি করার কৌশল, যেখানে প্রতিটি আংশিক সমাধানের পরে যাচাই করা হয় এটি এখনো একটি বৈধ পূর্ণ সমাধানে পরিণত হওয়ার সম্ভাবনা রাখে কি না — না রাখলে সেই শাখা তৎক্ষণাৎ ছেড়ে (backtrack করে) আগের অবস্থায় ফিরে যাওয়া হয়। এটি DSA কোর্সে ইতিমধ্যে পরিচিত একটি কৌশল — সেখানে ব্যাকট্র্যাকিং-এর বেসিক মেকানিক্স ও প্রথম ইমপ্লিমেন্টেশনগুলো দেখানো হয়েছে। এই কোর্স ধরে নেয় আপনি সেই মেকানিক্স জানেন — এখানে প্রশ্নটা ভিন্ন: প্রুনিং ঠিক কতটা কাজ বাঁচায়, তা প্রকৃতপক্ষে গুনে দেখানো।

২ · N-Queens মডেলিং — "প্রতি সারিতে একটি কলাম"

একটি বৈধ N-Queens সমাধানে প্রতিটি সারিতে ঠিক একটি কুইন থাকতেই হবে (দুটি কুইন একই সারিতে থাকলে তারা একে অপরকে আক্রমণ করবে)। তাই সমাধান খোঁজার সময় আমরা প্রতিটি সারির জন্য ঠিক একটি কলাম বেছে নেওয়ার সমস্যা হিসেবে মডেল করতে পারি — এতে কোনো বৈধ সমাধান বাদ পড়ে না, কারণ প্রতিটি বৈধ সমাধানই এই আকারে প্রকাশযোগ্য। ফলাফলকে placement[row] = col আকারের একটি অ্যারে হিসেবে রাখা হয়।

এই মডেলিং-এর পরেও, যদি কোনো কনফ্লিক্ট-চেক ছাড়াই প্রতিটি সারিতে $N$টি কলামের যেকোনো একটি বেছে নেওয়া হতো, তাহলে মোট সম্ভাব্য প্লেসমেন্ট সংখ্যা হতো:

কারণ প্রতিটি $N$টি সারির প্রতিটির জন্য স্বাধীনভাবে $N$টি কলামের যেকোনো একটি বেছে নেওয়া যায়। $N=8$-এ এটি $8^8 = 16{,}777{,}216$ — প্রায় ১.৬ কোটি সম্ভাব্য প্লেসমেন্ট, যার বেশিরভাগই অবশ্যই অবৈধ (একাধিক কুইন একই কলামে বা ডায়াগোনালে)।

নিচের কোডে তিনটি সেট ব্যবহার করা হয়েছে — cols, diag1 ($r - c$, একটি ডায়াগোনাল দিক), এবং diag2 ($r + c$, অন্য দিক) — যাতে প্রতিটি কনফ্লিক্ট চেক $O(1)$ সময়ে করা যায়, পুরনো সব কুইনের সাথে সরাসরি তুলনা না করে।

৩ · নোড কাউন্টিং সহ সম্পূর্ণ ইমপ্লিমেন্টেশন

নিচের কোডে backtrack(row) ফাংশনটি যতবার কল হয় ততবার node_count বাড়ানো হয় — অর্থাৎ সার্চ ট্রি-র প্রতিটি নোড (একটি নির্দিষ্ট আংশিক প্লেসমেন্ট স্টেট) ভিজিট করার সাথে সাথে গোনা হয়। এটি সত্যিই চলমান একটি ব্যাকট্র্যাকিং সমাধান — কোনো সংখ্যা অনুমান করা নয়।

def solve_n_queens(n):
    # নোড কাউন্টার: backtrack() যতবার কল হয়, ততবার +1
    # -- প্রতিটি কল মানেই সার্চ ট্রি-র একটি নোড (একটি আংশিক প্লেসমেন্ট) ভিজিট করা
    node_count = 0
    solutions = []
    cols = set()          # ব্যবহৃত কলামসমূহ
    diag1 = set()         # row - col (সমান হলে একই "\" ডায়াগোনাল)
    diag2 = set()         # row + col (সমান হলে একই "/" ডায়াগোনাল)
    placement = []        # placement[row] = সেই সারিতে কুইনের কলাম

    def backtrack(row):
        nonlocal node_count
        node_count += 1
        if row == n:
            solutions.append(placement.copy())
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # কনফ্লিক্ট -- এই শাখা প্রুন, কখনো recurse করা হবে না
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            placement.append(col)
            backtrack(row + 1)
            placement.pop()
            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    backtrack(0)
    return solutions, node_count


print(f"{'N':>3} | {'সমাধান':>8} | {'নোড এক্সপ্লোরড':>15} | {'নেইভ N^N':>15} | {'অনুপাত':>12}")
for n in [6, 8]:
    solutions, nodes = solve_n_queens(n)
    naive_space = n ** n
    ratio = nodes / naive_space
    print(f"{n:>3} | {len(solutions):>8} | {nodes:>15} | {naive_space:>15} | {ratio:.6%}")

# প্রতিটি সমাধান সত্যিই বৈধ কিনা হাতে-কলমে যাচাই (কোনো দুটি কুইন কনফ্লিক্টে নেই তো)
def is_valid_solution(placement):
    n = len(placement)
    for r1 in range(n):
        for r2 in range(r1 + 1, n):
            c1, c2 = placement[r1], placement[r2]
            if c1 == c2 or abs(r1 - r2) == abs(c1 - c2):
                return False
    return True

sample_solutions, _ = solve_n_queens(8)
print("\nN=8-এর সবগুলো সমাধান সত্যিই বৈধ কিনা:", all(is_valid_solution(s) for s in sample_solutions))