Skip to content

020 — N-Queens II

Source

  • Original source: Classic constraint backtracking exercise (count N non-attacking queen placements)
  • Platform: LeetCode — https://leetcode.com/problems/n-queens-ii/
  • Topic: recursion / backtracking (constraint backtracking, count only)
  • Difficulty: Hard
  • Pattern: constraint backtracking (count only) — leaf-এ বোর্ড না বানিয়ে শুধু 1 যোগ করো
  • Basic idea inherited from: N-Queens, board-গুলো বাদ দাও

1. Problem in simple words

আগের problem-এর মতোই — n × n বোর্ডে nটা queen বসাতে হবে যেন কেউ কাউকে আক্রমণ না করে (একই row/column/diagonal নিষেধ)। পার্থক্য একটাই: এবার সব সাজ ছাপাতে হবে না, শুধু মোট কয়টা বৈধ সাজ আছে সেই সংখ্যাটা ফেরত দিতে হবে।

n = 4 -> 2     (দুটো বৈধ সাজ)
n = 1 -> 1
n = 8 -> 92

2. Which basic idea does this inherit from?

ভিত্তি হলো N-Queens, শুধু বোর্ড-গুলো বাদ দাও। হুবহু সেই row-by-row constraint backtracking আর তিনটা blocked-line set (cols, r-c, r+c)। একমাত্র বদল: leaf-এ পৌঁছে আর string-বোর্ড গড়ি না, শুধু count-এ 1 যোগ করি। তাই enumeration-এর কঙ্কাল এক, output-টা সংখ্যা মাত্র।

3. What is the hidden math or logic?

লুকানো logic একই — diagonal-গুলো সংখ্যায়: ↘-তে r-c ধ্রুব, ↙-তে r+c ধ্রুব। তবে এখানে অতিরিক্ত একটা মিতব্যয়িতা: count চাইলে কোনো বৈধ leaf-এর বিস্তারিত বোর্ড গড়ার দরকার নেই — শুধু leaf গোনাই যথেষ্ট। গণিতের ভাষায়, আমরা solution-গুলোর cardinality চাই, তাদের বিবরণ নয়। বৈধ সাজ-সংখ্যা হলো একটা পরিচিত sequence (n = 1..10 → 1, 0, 0, 2, 10, 4, 40, 92, 352, 724)।

4. Which data structure is needed?

লাগে তিনটা set — cols, diag (r-c), anti (r+c) safe-check ও mark-এর জন্য; আর recursion-এর জন্য call stack। N-Queens-এর queens list বা out list লাগেই না — count integer return-ই যথেষ্ট। মানে memory আরও হালকা।

5. Why this data structure fits

তিনটা set diagonal/column safe-check ও mark/unmark O(1)-তে দেয় — ঠিক N-Queens-এর মতো। বোর্ড না জমানোয় আমরা leaf-এ এসে শুধু 1 ফেরাই, তাই কোনো বৈধ সাজের জন্য O(n²) string-গড়ার খরচ বাঁচে। count-গুলো recursion-এর return value হয়ে নিচ থেকে উপরে যোগ হয়ে আসে — কোনো mutable accumulator-ও লাগে না (চাইলে nonlocal counter-ও চলত)।

6. Real-life analogy

ভাবো একটা ভেন্যুতে কয়টা ভাবে অতিথিদের বসানো যায় তা শুধু গুনতে চাও — কে কোথায় বসল তার চার্ট লাগবে না, শুধু সংখ্যা। প্রতিটা বৈধ বিন্যাস পেলে একটা গণনা-ঘরে এক টোকা দাও, বিন্যাসটা লিখে রাখার দরকার নেই। কম খাটনি, কম কাগজ — একই অনুসন্ধান, শুধু ফল হিসেবে একটা সংখ্যা।

7. Visual explanation

N-Queens-এর মতোই গাছ; পার্থক্য leaf-এ — বোর্ড নয়, return 1, আর তা উপরে যোগ হয়। n=4:

                      go(r=0)  = c0..c3 শাখার count-যোগফল
        c0            c1              c2            c3
      go(1)=0       go(1)=1         go(1)=1       go(1)=0
      (নিচে কোনো    (একটা বৈধ        (একটা বৈধ      (নিচে কোনো
       leaf নেই)     leaf -> 1)       leaf -> 1)     leaf নেই)
                         \              /
                          go(0) মোট = 0+1+1+0 = 2

r == n -> return 1; প্রতিটা go(r) তার শাখাগুলোর count যোগ করে ফেরায়।

8. Example input and output

Input : n=4 -> Output: 2
Input : n=1 -> Output: 1

Edge case 1 (অসম্ভব): n=2 -> Output: 0
Edge case 2 (অসম্ভব): n=3 -> Output: 0

9. Brute force thinking

প্রথম সরল চিন্তা: N-Queens-এর মতো সব বৈধ বোর্ড গড়ো, একটা list-এ জমাও, তারপর len(list) ফেরাও।

boards = solve_n_queens(n)     # সব বৈধ সাজ গড়ে জমা
return len(boards)

10. Why brute force is slow

এটা সঠিক উত্তর দেয়, কিন্তু অপ্রয়োজনীয় কাজ করে: প্রতিটা বৈধ সাজের জন্য O(n²) করে string-বোর্ড গড়ে list-এ রাখে, যদিও শেষে শুধু গুনবে। বৈধ সাজ অনেক হলে (যেমন n=9-এ 352) এই বোর্ড-গড়া ও memory খরচ পুরোটাই বাজে। count-only version leaf-এ শুধু 1 ফেরায় — কোনো বোর্ড গড়ে না, list রাখে না; time-এর big-O একই থাকলেও ধ্রুবক ও memory অনেক কম।

11. Key observation

মূল observation: "কীভাবে" বসানো হলো তা দরকার নেই, শুধু "কয়ভাবে"। তাই enumeration চালাও ঠিক আগের মতো, কিন্তু leaf-এ বিবরণ সংরক্ষণ না করে গণনা বাড়াও। count-গুলোকে recursion-এর return value করে দিলে কোডও পরিষ্কার — প্রতি go(r) তার সব বৈধ subtree-র যোগফল ফেরায়।

12. Optimized intuition

go(r): base case r == n হলে return 1 (এক বৈধ সাজ সম্পূর্ণ)। নাহলে count = 0; প্রতিটা safe c-এর জন্য তিন set-এ mark, count += go(r+1), তারপর unmark; শেষে return count। কোনো global list নেই — সংখ্যা নিচ থেকে যোগ হয়ে উপরে ওঠে।

13. Thinking tweak

মোচড়: যখন প্রশ্ন "কয়টা?" — তখন leaf-এ candidate গড়া বন্ধ করে দাও, শুধু 1 ফেরাও। backtracking template-এর একমাত্র পরিবর্তন: out.append(snapshot) → count += 1 (বা return 1)। এই ছোট বদলেই "সব list করো" থেকে "শুধু গোনো"-তে চলে যাও — memory নাটকীয়ভাবে কমে।

14. Step-by-step dry run

total_n_queens(4), go(r):

  1. go(0): c=0 → go(1): কোনো safe column নিচে বৈধ leaf দেয় না → 0।
  2. go(0): c=1 → go(1) → c=3 → go(2) → c=0 → go(3) → c=2 → go(4): r==n → 1। এই শাখা মোট 1।
  3. go(0): c=2 → mirror শাখা → 1।
  4. go(0): c=3 → 0।
  5. মোট 0 + 1 + 1 + 0 = 2 → return 2।

15. Python solution

def total_n_queens(n):
    cols = set()
    diag = set()     # r - c
    anti = set()     # r + c

    def go(r):
        if r == n:                       # base case: এক বৈধ সাজ সম্পূর্ণ
            return 1
        count = 0
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue                 # unsafe column/diagonal -> branch বাদ
            cols.add(c); diag.add(r - c); anti.add(r + c)   # CHOOSE
            count += go(r + 1)           # EXPLORE: subtree-র বৈধ সাজ যোগ
            cols.discard(c); diag.discard(r - c); anti.discard(r + c)  # UN-CHOOSE
        return count

    return go(0)

# ---- tests (পরিচিত N-Queens count sequence) ----
assert total_n_queens(1) == 1
assert total_n_queens(2) == 0           # অসম্ভব
assert total_n_queens(3) == 0           # অসম্ভব
assert total_n_queens(4) == 2
assert total_n_queens(5) == 10
assert total_n_queens(6) == 4
assert total_n_queens(7) == 40
assert total_n_queens(8) == 92
print("সব test pass!")

16. Line-by-line code explanation

  • cols/diag/anti = set() — N-Queens-এর সেই তিন blocked-line; বোর্ড-list এবার নেই।
  • if r == n: return 1 — base case: পূর্ণ এক সাজ, গণনায় 1।
  • count = 0 — এই row থেকে শুরু হওয়া সব বৈধ subtree-র যোগফল।
  • if c in cols or (r-c) in diag or (r+c) in anti: continue — safe-check গেট।
  • cols.add(c); diag.add(r-c); anti.add(r+c) — CHOOSE: তিন line block।
  • count += go(r + 1) — EXPLORE: নিচের সব বৈধ সাজ-সংখ্যা যোগ।
  • ...discard(...) — UN-CHOOSE: line-গুলো খালি করো।
  • return count — এই node-এর মোট বৈধ সাজ উপরে ফেরাও।

17. Output walkthrough

total_n_queens(4): row 0-এর column 1 ও 2 শাখা প্রতিটা থেকে একটা করে বৈধ leaf আসে, 0 ও 3 শাখায় কিছুই না — যোগফল 2। count return-value হয়ে নিচ থেকে উপরে উঠে আসে, কোনো list রাখা হয় না। n=2,3-এ কোনো leaf নেই → 0; n=5..8-এ পরিচিত sequence 10, 4, 40, 92। সব মিলে print: সব test pass!।

18. Time complexity

N-Queens-এর মতোই worst case O(n!)-এর কাছাকাছি, diagonal pruning-এ বাস্তবে অনেক কম। তবে বোর্ড না গড়ায় প্রতি leaf-এ O(n²)-এর বদলে O(1) — ধ্রুবক উল্লেখযোগ্য কম।

19. Space complexity

O(n) — তিনটা set-এ সর্বোচ্চ n করে, আর call stack গভীরতা n। N-Queens-এর তুলনায় কোনো out/queens list নেই, তাই output-এর জন্য বাড়তি memory শূন্য।

20. Common mistakes

  • count-only version-এও leaf-এ বোর্ড গড়া — অপ্রয়োজনীয় কাজ ও memory; শুধু return 1।
  • count += go(r+1)-এর return মান উপেক্ষা করে nonlocal counter ভুলভাবে mix করা — একটাই পদ্ধতি ধরে রাখো (return-যোগফল বা nonlocal, দুটো একসাথে নয়)।
  • backtrack-এ তিন set discard ভুলে যাওয়া — পরের branch-এ block leak।
  • n=2,3-এ 0 ফেরাতে না পারা — base/loop ঠিকভাবে empty subtree handle করুক।

21. Which basic problem this inherits from

ভিত্তি: N-Queens (#19) হুবহু — শুধু leaf-এর action বদল (record board → return 1)। ../patterns.md-এর "enumerate vs. count" নোট দেখো: একই backtracking কঙ্কালে output-এর ধরন বদলে অনেক problem সমাধান হয়। গোনার দরকার হলে candidate গড়া বন্ধ করাই মূল শিক্ষা।

22. Similar harder problems

23. Pattern learned

Count-only backtracking: যখন প্রশ্ন "কয়ভাবে?", তখন একই enumeration চালাও কিন্তু leaf-এ candidate সংরক্ষণ না করে গণনা বাড়াও (return 1, উপরে যোগ); template-এ একটিমাত্র লাইন বদলেই enumerate থেকে count-এ যাও, memory নাটকীয়ভাবে কমে।

24. Final summary

ভবিষ্যতের আমাকে: "N-Queens II = N-Queens-এর তিন set + row-by-row, কিন্তু leaf-এ return 1 আর count যোগ করো — কোনো বোর্ড গড়ো না।" যখনই 'কয়ভাবে করা যায় গোনো' শুনবে — চেনা enumeration-এর leaf-action-টা return 1-এ বদলে দাও; বিবরণ না, শুধু সংখ্যা।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।