019 — N-Queens

Source

• Original source: Classic constraint backtracking exercise (place N non-attacking queens)
• Platform: LeetCode — https://leetcode.com/problems/n-queens/
• Topic: recursion / backtracking (constraint backtracking)
• Difficulty: Hard
• Pattern: constraint backtracking — প্রতি row-এ এক queen, 3টা blocked-line set দিয়ে safe-check
• Basic idea inherited from: Permutations + তিনটা blocked-line set

1. Problem in simple words

একটা n × n দাবার বোর্ডে nটা queen বসাতে হবে এমনভাবে যেন কোনো দুটো queen একে অন্যকে আক্রমণ না করে। দাবায় queen একই row, একই column, আর দুই কোনাকুনি (diagonal) বরাবর আক্রমণ করে। তোমার কাজ: সব রকম বৈধ সাজানো বের করা, প্রতিটা বোর্ড string-এর list হিসেবে — 'Q' মানে queen, '.' মানে খালি।

n = 4 -> 2টা বৈধ সাজ:
.Q..        ..Q.
...Q        Q...
Q...        ...Q
..Q.        .Q..

2. Which basic idea does this inherit from?

ভিত্তি হলো Permutations + তিনটা blocked-line set। প্রতিটা row-এ ঠিক একটা queen, আর প্রতিটা column-এ ঠিক একটা — মানে সমাধান আসলে column-এর একটা permutation (queens[r] = c)। Permutations-এর "প্রতিটা মান একবার" নিয়মই column-clash সামলায়; বাড়তি শুধু দুটো diagonal-শর্ত। তাই N-Queens = permutation generate করা, কিন্তু প্রতি placement-এর আগে diagonal গেট সহ — Generate Parentheses-এর early-validity ভাবেরই বোর্ড-রূপ।

3. What is the hidden math or logic?

লুকানো logic হলো diagonal-গুলোকে সংখ্যায় ধরা: একই ↘ diagonal-এর সব cell-এ r - c সমান; একই ↙ (anti-diagonal)-এর সব cell-এ r + c সমান। তাই তিনটা শর্ত তিনটা set-এ নেমে আসে — cols (ব্যবহৃত column), diag (r-c মান), anti (r+c মান)। একটা cell (r, c) safe ঠিক তখনই, যখন c, r-c, r+c তিনটাই নিজ-নিজ set-এ নেই। এতে safe-check O(1)।

4. Which data structure is needed?

লাগে তিনটা set — cols, diag (r-c), anti (r+c); একটা list queens (queens[r] = c, বোর্ড পুনর্গঠনে); একটা list out (সব সমাধান জমাতে); আর recursion-এর জন্য call stack। row ধরে ধরে নামি, তাই row-clash আপনিই বাদ (প্রতি row-এ একবারই বসাই)।

5. Why this data structure fits

তিনটা set diagonal/column-clash check ও mark/unmark O(1)-তে করে — পুরো বোর্ড scan করে threat খোঁজার দরকার নেই। row-by-row নামায় row-constraint কোডে আলাদা করে রাখতেই হয় না। queens list শুধু leaf-এ একবার string-বোর্ডে রূপান্তরিত হয়, তাই মাঝপথে memory হালকা। mark করে recurse, ফিরে unmark — choose/un-choose-এর নিখুঁত প্রয়োগ, কোনো clash-state leak হয় না।

6. Real-life analogy

ভাবো একটা office-এ n জন প্রহরী রাখতে হবে, প্রতিজন একটা করিডোর (row) পাহারা দেয়; কিন্তু কারও line-of-sight (column বা কোনাকুনি) যেন অন্য প্রহরীর ওপর না পড়ে। একটা করিডোরে একজনকে এমন জায়গায় দাঁড় করাও যেখানে আগের কারও দৃষ্টিরেখায় সে পড়ে না; না মিললে পিছিয়ে এসে অন্য জায়গা দেখো। সব রকম সংঘাতহীন বিন্যাসই উত্তর।

7. Visual explanation

row 0 থেকে নামি; প্রতি row-এ safe column বসাই (cols/diag/anti দেখে), নাহলে branch বাদ। n=4-এর একটা শাখা:

                      go(r=0)
        c0          c1            c2          c3
     go(r=1)      go(r=1)       go(r=1)     go(r=1)
   c0,c1 unsafe   c3 safe ->     ...          ...
                  go(r=2)
                c1 safe -> go(r=3)
                          c2 safe -> go(r=4)
                                    r==n -> record:
                                    .Q.. / ...Q / Q... / ..Q.

প্রতি row-এ unsafe column-এ ঢুকিই না; r==n হলে এক সম্পূর্ণ বোর্ড record।

8. Example input and output

Input : n=4 -> Output: 2টা বোর্ড (উপরে দেখানো)
Input : n=1 -> Output: [["Q"]]

Edge case 1 (অসম্ভব): n=2 -> Output: []   (কোনো সাজ নেই)
Edge case 2 (অসম্ভব): n=3 -> Output: []

9. Brute force thinking

প্রথম সরল চিন্তা: n²টা cell থেকে যেকোনো nটা cell বেছে queen বসানোর সব combination গড়ো, তারপর প্রতিটা বিন্যাসে কোনো দুটো queen পরস্পরকে আক্রমণ করে কিনা যাচাই করো।

for each way to choose n cells out of n*n:      # C(n*n, n)
    if no two chosen cells share row/col/diagonal:
        record the board

10. Why brute force is slow

C(n², n) সংখ্যাটা বিশাল — n=8-এ C(64, 8) ≈ 4.4 বিলিয়ন বিন্যাস, যার সিংহভাগে দুটো queen একই row বা column-এ। backtracking দুটো কাজে এটা ছাঁটে: (a) row ধরে নামায় প্রতি row-এ একটাই queen, তাই row/column-clash অধিকাংশই বাদ; (b) প্রতি placement-এর আগে diagonal safe-check করে — একটা partial বোর্ড অবৈধ হলে তার নিচের পুরো subtree-তে নামেই না। ফলে কেবল promising branch-ই খোলা হয়।

11. Key observation

মূল observation: সমাধান = column-এর permutation + diagonal গেট। "n²টা cell থেকে কোনগুলো?" না ভেবে ভাবো "row r-এ queen-টা কোন column-এ বসবে?" — প্রতি row-এ ঠিক একটা সিদ্ধান্ত। আর তিনটা clash-শর্ত তিনটা সংখ্যায় (c, r-c, r+c) নেমে আসে, তাই safe-check O(1)। validity branch খোলার গেট, শেষের যাচাই নয়।

12. Optimized intuition

go(r): base case r == n হলে queens থেকে string-বোর্ড বানিয়ে record। নাহলে প্রতিটা c (0→n-1): c/r-c/r+c কোনো set-এ থাকলে skip; নাহলে তিন set-এ add + queens.append(c) (choose), go(r+1) (explore), তারপর pop + তিন set থেকে discard (un-choose)। row-by-row নামা + diagonal গেট = early-validity constraint backtracking।

13. Thinking tweak

মোচড়: পুরো বোর্ড একসাথে ভেবো না; এক row-এ একটা queen-এর সিদ্ধান্তে নেমে এসো। আর "এই দুটো queen কি কোনাকুনি?" — geometry না করে দুটো সংখ্যা মেলাও: r-c সমান হলে একই ↘, r+c সমান হলে একই ↙। জ্যামিতিক শর্তকে set-membership-এ বদলে দিলে check তাৎক্ষণিক।

14. Step-by-step dry run

solve_n_queens(4), go(r) (একটা সফল শাখা):

1. go(0): c=1 safe → cols={1}, diag={-1}, anti={1}, queens=[1]; go(1)।
2. go(1): c=0,1,2 কোনো-না-কোনো set-এ আটকায়; c=3 safe → queens=[1,3]; go(2)।
3. go(2): c=0 safe → queens=[1,3,0]; go(3)।
4. go(3): c=2 safe → queens=[1,3,0,2]; go(4): r==n → record .Q.. / ...Q / Q... / ..Q.।
5. backtrack করে দ্বিতীয় mirror-সমাধানও বেরোয়; out-এ 2টা বোর্ড।

15. Python solution

def solve_n_queens(n):
    out = []
    cols = set()
    diag = set()     # r - c (↘ diagonal)
    anti = set()     # r + c (↙ anti-diagonal)
    queens = []      # queens[r] = c

    def go(r):
        if r == n:                       # base case: সব row-এ queen বসানো
            board = ["." * c + "Q" + "." * (n - c - 1) for c in queens]
            out.append(board)            # এক সম্পূর্ণ সাজ record
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue                 # unsafe: এই column বা কোনো diagonal blocked
            cols.add(c); diag.add(r - c); anti.add(r + c)   # CHOOSE
            queens.append(c)
            go(r + 1)                    # EXPLORE: পরের row
            queens.pop()                 # UN-CHOOSE
            cols.discard(c); diag.discard(r - c); anti.discard(r + c)

    go(0)
    return out

# ---- order-independent তুলনার helper (বোর্ডের ভেতরের row-ক্রম অটুট) ----
def norm(boards):
    return sorted(boards)                # প্রতিটা বোর্ড row-string-এর list

# ---- tests ----
assert solve_n_queens(1) == [["Q"]]
assert solve_n_queens(2) == []                    # অসম্ভব
assert solve_n_queens(3) == []                    # অসম্ভব
assert len(solve_n_queens(4)) == 2
assert norm(solve_n_queens(4)) == norm([
    [".Q..", "...Q", "Q...", "..Q."],
    ["..Q.", "Q...", "...Q", ".Q.."]])
assert len(solve_n_queens(5)) == 10
assert len(solve_n_queens(6)) == 4
print("সব test pass!")

16. Line-by-line code explanation

• cols/diag/anti = set() — তিনটা blocked-line: column, r-c diagonal, r+c anti-diagonal।
• if r == n: — base case: প্রতি row-এ queen বসে গেছে, একটা পূর্ণ সমাধান।
• ["." * c + "Q" + "." * (n-c-1) for c in queens] — column-index থেকে 'Q'-যুক্ত string-বোর্ড।
• if c in cols or (r-c) in diag or (r+c) in anti: continue — তিন set-এ safe-check; unsafe হলে branch খোলোই না (গেট)।
• cols.add(c); diag.add(r-c); anti.add(r+c); queens.append(c) — CHOOSE: queen বসিয়ে তিনটা line block।
• go(r + 1) — EXPLORE: পরের row-এ নামো।
• queens.pop(); ...discard(...) — UN-CHOOSE: queen তুলে তিনটা line আবার খালি করো।

17. Output walkthrough

solve_n_queens(4): row 0-এ column 1 ও 2 থেকে দুটো mirror-শাখা বৈধ হয়ে নামে, বাকি column-গুলো নিচের কোনো row-এ আটকে যায় — ফল ঠিক 2টা বোর্ড। প্রতিটা বোর্ড row-string-এর একটা ক্রমিক list (row 0 আগে), তাই norm-এ শুধু বাইরের list sort করি (ভেতরের ক্রম অটুট) — assert stable অথচ সঠিক। n=2,3-এ কোনো safe বিন্যাস নেই → []; n=5,6-এ 10 ও 4। সব মিলে print: সব test pass!।

18. Time complexity

worst case O(n!)-এর কাছাকাছি — row 0-এ n option, row 1-এ ≤ n-1, ... ফলে উপরের সীমা n!, তবে diagonal pruning বাস্তবে এর অনেক নিচে নামিয়ে আনে। বোর্ড record করতে প্রতিটা সমাধানে O(n²) (string গড়া)।

19. Space complexity

Output বাদ দিলে O(n) — তিনটা set-এ সর্বোচ্চ n করে entry, queens list n, call stack গভীরতা n। Output ধরলে সব সমাধান-বোর্ডের মোট আকার।

20. Common mistakes

• diagonal-কে r-c/r+c-তে না নামিয়ে প্রতিবার পুরো বোর্ড scan করা — safe-check ধীর; দুটো diagonal-set ব্যবহার করো।
• backtrack-এ তিনটা set থেকে discard বা queens.pop() ভুলে যাওয়া — পরের branch-এ পুরোনো queen-এর block leak করে।
• r-c ঋণাত্মক হতে পারে — set-এ সমস্যা নেই (negative key চলে), কিন্তু array দিয়ে করলে offset (r-c+n) লাগে; এখানে set বলে নিরাপদ।
• n=2,3-এ [] না দিয়ে crash — base case ও empty-result ঠিকভাবে handle করো।

21. Which basic problem this inherits from

ভিত্তি: Permutations (#9)-এর "প্রতি মান একবার" (column permutation) + Generate Parentheses (#15)-এর early-validity গেট, এখানে তিনটা blocked-line set রূপে। ../patterns.md-এর constraint-backtracking pattern দেখো। এটা tracker-এর চারটা canonical interview shape-এর একটা — এখানে সবচেয়ে বেশি সময় দাও।

22. Similar harder problems

• N-Queens II (শুধু গোনা) — https://leetcode.com/problems/n-queens-ii/ (এই tracker-এর #20)
• Sudoku Solver (প্রতি cell-এ 3টা unit-set) — https://leetcode.com/problems/sudoku-solver/ (#22)
• Chessboard and Queens (blocked cell সহ, CSES) — https://cses.fi/problemset/ (#21)

23. Pattern learned

Constraint backtracking with line-sets: একটা মাত্রা (row) ধরে নামো, অন্য মাত্রার clash-শর্ত (column, দুই diagonal) কয়েকটা set-এ O(1) check/mark করো, আর প্রতি placement-এর আগে safe-check করো; geometry-কে সংখ্যায় (r-c, r+c) নামিয়ে আনাই মূল কৌশল।

24. Final summary

ভবিষ্যতের আমাকে: "N-Queens = row ধরে নামো; প্রতি row-এ safe column বসাও — cols, r-c diag, r+c anti তিন set দিয়ে check/mark; base case r==n।" যখনই 'একটা grid-এ কয়েকটা জিনিস non-attacking/non-conflicting বসাও' শুনবে — এই line-set constraint backtracking skeleton মনে করবে; conflict-শর্তকে set-membership-এ বদলে দাও।

---

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