021 — Chessboard and Queens¶

Source¶

Original source: Classic constraint backtracking exercise (N queens on a board with reserved squares)
Platform: CSES — https://cses.fi/problemset/ (task name: Chessboard and Queens)
Topic: recursion / backtracking (N-Queens with blocked cells)
Difficulty: Hard
Pattern: N-Queens with blocked cells — safe-check-এর সাথে আরও একটা গেট: cell reserved কিনা
Basic idea inherited from: N-Queens + বাড়তি constraint

1. Problem in simple words¶

একটা বোর্ড দেওয়া আছে যেখানে কিছু ঘর reserved ('*') — সেখানে queen বসানো যাবে না — আর বাকি ঘর free ('.')। তোমার কাজ: এমন কয়ভাবে queen বসানো যায় তা গোনা, যেন (a) প্রতিটা queen একটা free ঘরে থাকে আর (b) কোনো দুটো queen একে অন্যকে আক্রমণ না করে (একই row/column/diagonal নিষেধ)। CSES-এ বোর্ডটা n × n (মূল task-এ 8×8) এবং উত্তর একটা সংখ্যা।

n = 4, সব free        n = 4, (0,1) reserved
....                  .*..
....   -> 2           ....   -> 1   (যে সাজের queen (0,1)-এ পড়ত, সেটা বাদ)
....                  ....
....                  ....

2. Which basic idea does this inherit from?¶

ভিত্তি হলো N-Queens + একটা বাড়তি constraint। হুবহু সেই row-by-row backtracking আর তিনটা blocked-line set (cols, r-c, r+c)। নতুন শুধু একটা গেট: column c নেওয়ার আগে দেখি board[r][c] reserved কিনা — হলে skip। আর যেহেতু CSES-এ "কয়ভাবে" জিজ্ঞেস, leaf-এ N-Queens II-এর মতো শুধু 1 যোগ করি। মানে #19 + #20-এর মিশ্রণ, ওপরে reserved-square গেট।

3. What is the hidden math or logic?¶

লুকানো logic আগের মতোই — diagonal-গুলো সংখ্যায় (r-c, r+c), safe-check O(1)। বাড়তি constraint শুধু সম্ভাব্য placement-এর ডোমেন ছোট করে: প্রতি row-এ free এবং safe column-ই কেবল প্রার্থী। reserved ঘর যত বেশি, বৈধ সাজ তত কম — পুরো-free বোর্ড সর্বোচ্চ সংখ্যা দেয় (8×8-এ 92, ঠিক N-Queens-এর মান)। অর্থাৎ এটা N-Queens-এর সংখ্যার একটা নিম্নমুখী রূপভেদ, reserved গেট দিয়ে নিয়ন্ত্রিত।

4. Which data structure is needed?¶

লাগে board (2D grid, reserved-check-এর জন্য, read-only); তিনটা set — cols, diag (r-c), anti (r+c); আর recursion-এর জন্য call stack। উত্তর সংখ্যা বলে কোনো solution-list লাগে না — count integer return-ই যথেষ্ট।

5. Why this data structure fits¶

board[r][c] == '*' check O(1), তাই reserved গেট প্রায় বিনা খরচে যোগ হয়। তিনটা set আগের মতোই column/diagonal safe-check ও mark/unmark O(1)-তে দেয়। row-by-row নামায় row-constraint আপনিই মেটে। count return-value হয়ে নিচ থেকে উপরে যোগ হয়ে আসে — কোনো বোর্ড গড়া বা list রাখার দরকার নেই, memory হালকা।

6. Real-life analogy¶

আগের prহরী-উদাহরণ ভাবো, কিন্তু এবার কিছু করিডোরের কিছু জায়গা "নির্মাণকাজ চলছে" বলে বন্ধ — সেখানে কাউকে দাঁড় করানো যাবে না। তাই এক করিডোরে (row) প্রহরী বসানোর সময় শুধু খোলা এবং কারও দৃষ্টিরেখার বাইরে — এমন জায়গাই চলবে। কয়ভাবে পুরো team বসানো যায়, শুধু সেই সংখ্যাটা গোনো।

7. Visual explanation¶

N-Queens-এর গাছ, কিন্তু প্রতি row-এ আরও একটা গেট: cell reserved হলে skip। n=4, (0,1) reserved:

                       go(r=0)
       c0          c1(reserved: skip)      c2            c3
     go(1)=0                               go(1)=1      go(1)=0
                                          (একটা বৈধ
                                           leaf -> 1)
                          \-> go(0) মোট = 0 + (skip) + 1 + 0 = 1

reserved column-এ ঢুকিই না; safe হলে mark করে নামি; r==n -> return 1।

8. Example input and output¶

Input : 4×4 সব free               -> Output: 2
Input : 4×4, (0,1) reserved        -> Output: 1
Input : 8×8 সব free                -> Output: 92   (= N-Queens)

Edge case 1 (এক ঘর free):  1×1 "."        -> Output: 1
Edge case 2 (সব বন্ধ row0): 4×4 ".**." উপরে -> Output: 0

9. Brute force thinking¶

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

free_cells = [(r, c) for r, c free]
for each way to choose n cells out of free_cells:
    if no two share row/col/diagonal:
        count += 1

10. Why brute force is slow¶

free ঘর বেছে combination গড়ার সংখ্যা বিশাল (C(|free|, n)), আর তার সিংহভাগে দুটো queen একই row/column-এ পড়ে — অর্থহীন যাচাই। backtracking row ধরে নামে (এক row-এ এক queen, তাই অধিকাংশ clash বাদ), আর প্রতি placement-এর আগে reserved + diagonal গেট দিয়ে hopeless partial বোর্ডে নামেই না। ফলে বৈধ-হওয়ার সম্ভাবনা আছে এমন branch-ই কেবল খোলা হয়।

11. Key observation¶

মূল observation: reserved square শুধু একটা অতিরিক্ত skip-গেট — N-Queens-এর safe-check-এর পাশে board[r][c] == '*' যোগ করলেই হয়ে যায়। নতুন কোনো algorithm নয়, চেনা constraint backtracking-এ একটা গেট বসানো। আর প্রশ্ন "কয়ভাবে" বলে leaf-এ বোর্ড না গড়ে শুধু গোনা।

12. Optimized intuition¶

go(r): base case r == n হলে return 1। নাহলে count = 0; প্রতিটা c-এর জন্য — board[r][c] == '*' হলে skip (reserved গেট); c/r-c/r+c কোনো set-এ থাকলে skip (attack গেট); নাহলে তিন set-এ mark, count += go(r+1), তারপর unmark; শেষে return count। দুটো গেট পরপর, বাকি সব N-Queens II-এর মতো।

13. Thinking tweak¶

মোচড়: নতুন constraint মানেই নতুন algorithm নয় — প্রায়ই চেনা backtracking-এ আর একটা if-গেট। "reserved square" দেখে ভয় না পেয়ে ভাবো "N-Queens-ই, শুধু কিছু column প্রতি row-এ আগে থেকে নিষিদ্ধ।" বড় বদল মনে হওয়া জিনিসটা এক লাইনের continue-তে নেমে আসে।

14. Step-by-step dry run¶

count_queens([".*..","....","....","...."]) (4×4, (0,1) reserved), go(r):

go(0): c=0 safe ও free → mark → go(1): নিচে কোনো বৈধ leaf নেই → 0।
go(0): c=1 → board[0][1]=='*' → skip (reserved)।
go(0): c=2 safe ও free → mark → go(1)→...→ একটা বৈধ leaf → 1।
go(0): c=3 → নিচে বৈধ leaf নেই → 0।
মোট 0 + (skip) + 1 + 0 = 1 → return 1। (পুরো-free বোর্ডে এই (0,1)-শাখাটাই দ্বিতীয় সমাধান দিত, তাই 2 → 1।)

15. Python solution¶

def count_queens(board):
    n = len(board)
    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 board[r][c] == "*":       # reserved গেট: এই ঘরে queen নিষেধ
                continue
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue                 # attack গেট: column/diagonal blocked
            cols.add(c); diag.add(r - c); anti.add(r + c)   # CHOOSE
            count += go(r + 1)           # EXPLORE
            cols.discard(c); diag.discard(r - c); anti.discard(r + c)  # UN-CHOOSE
        return count

    return go(0)

# ---- tests (নিজের গড়া বোর্ড, প্রতিটার উত্তর যুক্তিতে নিশ্চিত) ----
assert count_queens(["....", "....", "....", "...."]) == 2     # সব free = N-Queens(4)
assert count_queens([".*..", "....", "....", "...."]) == 1     # (0,1) blocked -> 1 বাদ
assert count_queens([".**.", "....", "....", "...."]) == 0     # row0-এর দুই queen-ঘরই বন্ধ
assert count_queens(["." * 8 for _ in range(8)]) == 92         # সব free = N-Queens(8)
assert count_queens(["."]) == 1                                # 1×1 free
example8 = ["........", "........", "..*.....", "........",
            "....*...", "........", "........", "........"]
assert count_queens(example8) == 80                            # দুটো reserved ঘর -> 92 থেকে কমে 80
print("সব test pass!")

16. Line-by-line code explanation¶

n = len(board) — বোর্ডের মাপ (CSES মূল task-এ 8)।
cols/diag/anti = set() — N-Queens-এর সেই তিন blocked-line।
if r == n: return 1 — base case: পূর্ণ এক বৈধ সাজ।
if board[r][c] == "*": continue — reserved গেট: নিষিদ্ধ ঘর বাদ (এটাই বাড়তি constraint)।
if c in cols or (r-c) in diag or (r+c) in anti: continue — attack গেট: column/diagonal clash।
cols.add(...); diag.add(...); anti.add(...) — CHOOSE: তিন line block।
count += go(r + 1) — EXPLORE: নিচের বৈধ সাজ-সংখ্যা যোগ।
...discard(...) — UN-CHOOSE: line খালি করো।

17. Output walkthrough¶

count_queens-এ পুরো-free 4×4 ও 8×8 যথাক্রমে 2 ও 92 দেয় — ঠিক N-Queens-এর মান, কারণ reserved গেট তখন কখনো ট্রিগারই হয় না। (0,1) block করলে যে সমাধানের queen ওখানে পড়ত সেটা বাদ → 1; row 0-এর দুটো queen-উপযোগী ঘরই block করলে → 0। শেষ example-এ দুটো reserved ঘর (2,2) ও (4,4) বৈধ সাজ 92 থেকে কমিয়ে 80-তে আনে। সব মিলে print: সব test pass!।

18. Time complexity¶

N-Queens-এর মতোই worst case O(n!)-এর কাছাকাছি, diagonal + reserved pruning-এ বাস্তবে অনেক কম। reserved ঘর যত বেশি, প্রার্থী column তত কম — তাই extra constraint উল্টো গতি বাড়ায়। leaf-এ গোনা O(1)।

19. Space complexity¶

O(n) — তিনটা set-এ সর্বোচ্চ n করে, call stack গভীরতা n। board input-ই (বাড়তি নয়); কোনো solution-list রাখা হয় না।

20. Common mistakes¶

reserved গেট attack-গেটের পরে রেখে আগে set-এ mark করে ফেলা — তারপর * দেখে skip করলে mark leak; reserved-check আগে, mark-এর আগে রাখো।
'*'/'.' উল্টে পড়া — কোনটা free কোনটা reserved গুলিয়ে ভুল count।
N-Queens II-এর মতো leaf-এ বোর্ড গড়া — শুধু return 1 যথেষ্ট।
backtrack-এ তিন set discard ভুলে যাওয়া — পরের branch-এ block leak।

21. Which basic problem this inherits from¶

ভিত্তি: N-Queens (#19) ও N-Queens II (#20) — তিন set + row-by-row + count, এখানে একটা reserved-square গেট যোগ। ../patterns.md-এর constraint-backtracking pattern দেখো: "নতুন constraint = প্রায়ই আর একটা skip-গেট।" বাস্তব problem-এ এভাবেই অতিরিক্ত নিয়ম যুক্ত হয়।

22. Similar harder problems¶

N-Queens (সব সাজ ছাপানো) — https://leetcode.com/problems/n-queens/ (এই tracker-এর #19)
N-Queens II (শুধু গোনা) — https://leetcode.com/problems/n-queens-ii/ (#20)
Sudoku Solver (প্রতি cell-এ 3টা unit-set) — https://leetcode.com/problems/sudoku-solver/ (#22)

23. Pattern learned¶

Constraint backtracking + extra domain gate: চেনা backtracking-এ একটা নতুন নিয়ম এলে প্রায়ই সেটা branch খোলার আগে একটা বাড়তি continue-গেট মাত্র (এখানে reserved-square); মূল কঙ্কাল অপরিবর্তিত, ডোমেন শুধু ছোট হয় — তাই প্রায়ই উল্টো দ্রুত চলে।

24. Final summary¶

ভবিষ্যতের আমাকে: "Chessboard and Queens = N-Queens II-এর তিন set + count, প্লাস board[r][c]=='*' হলে আগে skip।" যখনই 'চেনা problem + কিছু ঘর/অপশন নিষিদ্ধ' শুনবে — নতুন algorithm না খুঁজে চেনা backtracking-এ একটা reserved-গেট বসিয়ে দাও।

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