Problem link ও উৎস
- **Original source:** Classic constraint backtracking exercise (N queens on a board with reserved squares)
- **Platform:** CSES —
(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
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা বোর্ড দেওয়া আছে যেখানে কিছু ঘর **reserved** (`'*'`) — সেখানে queen বসানো যাবে না — আর বাকি ঘর **free** (`'.'`)। তোমার কাজ: এমন কয়ভাবে queen বসানো যায় তা গোনা, যেন (a) প্রতিটা queen একটা free ঘরে থাকে আর (b) কোনো দুটো queen একে অন্যকে আক্রমণ না করে (একই row/column/diagonal নিষেধ)। CSES-এ বোর্ডটা `n × n` (মূল task-এ 8×8) এবং উত্তর একটা সংখ্যা।
```text
n = 4, সব free n = 4, (0,1) reserved
.... .*..
.... -> 2 .... -> 1 (যে সাজের queen (0,1)-এ পড়ত, সেটা বাদ)
.... ....
.... ....
```
### Input ও output {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
আগের prহরী-উদাহরণ ভাবো, কিন্তু এবার কিছু করিডোরের কিছু জায়গা "নির্মাণকাজ চলছে" বলে বন্ধ — সেখানে কাউকে দাঁড় করানো যাবে না। তাই এক করিডোরে (row) প্রহরী বসানোর সময় শুধু খোলা **এবং** কারও দৃষ্টিরেখার বাইরে — এমন জায়গাই চলবে। কয়ভাবে পুরো team বসানো যায়, শুধু সেই সংখ্যাটা গোনো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 হালকা।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: free ঘরগুলোর মধ্য থেকে যেকোনো `n`টা বেছে queen বসানোর সব combination গড়ো, তারপর প্রতিটায় কোনো দুটো queen পরস্পরকে আক্রমণ করে কিনা যাচাই করে গোনো।
```text
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`-তে নেমে আসে।
### ছবিতে বোঝা {#7-visual-explanation}
N-Queens-এর গাছ, কিন্তু প্রতি row-এ আরও একটা গেট: cell reserved হলে skip। `n=4`, `(0,1)` reserved:
```text
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।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`count_queens([".*..","....","....","...."])` (4×4, `(0,1)` reserved), `go(r)`:
1. `go(0)`: `c=0` safe ও free → mark → `go(1)`: নিচে কোনো বৈধ leaf নেই → 0।
2. `go(0)`: `c=1` → `board[0][1]=='*'` → skip (reserved)।
3. `go(0)`: `c=2` safe ও free → mark → `go(1)`→...→ একটা বৈধ leaf → 1।
4. `go(0)`: `c=3` → নিচে বৈধ leaf নেই → 0।
5. মোট `0 + (skip) + 1 + 0 = 1` → return 1। (পুরো-free বোর্ডে এই (0,1)-শাখাটাই দ্বিতীয় সমাধান দিত, তাই 2 → 1।)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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 খালি করো।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: N-Queens (#19) ও N-Queens II (#20) — তিন set + row-by-row + count, এখানে একটা reserved-square গেট যোগ। [../patterns.md](../patterns.md)-এর constraint-backtracking pattern দেখো: "নতুন constraint = প্রায়ই আর একটা skip-গেট।" বাস্তব problem-এ এভাবেই অতিরিক্ত নিয়ম যুক্ত হয়।
### পরের অনুশীলন {#22-similar-harder-problems}
- N-Queens (সব সাজ ছাপানো) —