Problem link ও উৎস
- **Original source:** Classic constraint backtracking exercise (count N non-attacking queen placements)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (constraint backtracking, count only)
- **Difficulty:** Hard
- **Pattern:** constraint backtracking (count only) — leaf-এ বোর্ড না বানিয়ে শুধু 1 যোগ করো
- **Basic idea inherited from:** N-Queens, board-গুলো বাদ দাও
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
আগের problem-এর মতোই — `n × n` বোর্ডে `n`টা queen বসাতে হবে যেন কেউ কাউকে আক্রমণ না করে (একই row/column/diagonal নিষেধ)। পার্থক্য একটাই: এবার সব সাজ ছাপাতে হবে না, শুধু **মোট কয়টা বৈধ সাজ আছে সেই সংখ্যাটা** ফেরত দিতে হবে।
```text
n = 4 -> 2 (দুটো বৈধ সাজ)
n = 1 -> 1
n = 8 -> 92
```
### Input ও output {#8-example-input-and-output}
```text
Input : n=4 -> Output: 2
Input : n=1 -> Output: 1
Edge case 1 (অসম্ভব): n=2 -> Output: 0
Edge case 2 (অসম্ভব): n=3 -> Output: 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা ভেন্যুতে কয়টা ভাবে অতিথিদের বসানো যায় তা শুধু **গুনতে** চাও — কে কোথায় বসল তার চার্ট লাগবে না, শুধু সংখ্যা। প্রতিটা বৈধ বিন্যাস পেলে একটা গণনা-ঘরে এক টোকা দাও, বিন্যাসটা লিখে রাখার দরকার নেই। কম খাটনি, কম কাগজ — একই অনুসন্ধান, শুধু ফল হিসেবে একটা সংখ্যা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-ও চলত)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: N-Queens-এর মতো সব বৈধ বোর্ড **গড়ো**, একটা list-এ জমাও, তারপর `len(list)` ফেরাও।
```text
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 নাটকীয়ভাবে কমে।
### ছবিতে বোঝা {#7-visual-explanation}
N-Queens-এর মতোই গাছ; পার্থক্য leaf-এ — বোর্ড নয়, `return 1`, আর তা উপরে যোগ হয়। `n=4`:
```text
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 যোগ করে ফেরায়।
```
### ছোট input-এ ধাপে ধাপে {#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।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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-এর মোট বৈধ সাজ উপরে ফেরাও।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 করুক।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: N-Queens (#19) হুবহু — শুধু leaf-এর action বদল (`record board` → `return 1`)। [../patterns.md](../patterns.md)-এর "enumerate vs. count" নোট দেখো: একই backtracking কঙ্কালে output-এর ধরন বদলে অনেক problem সমাধান হয়। গোনার দরকার হলে candidate গড়া বন্ধ করাই মূল শিক্ষা।
### পরের অনুশীলন {#22-similar-harder-problems}
- N-Queens (সব সাজ ছাপানো) —