Problem link ও উৎস
- **Original source:** Classic constraint backtracking exercise (place N non-attacking queens)
- **Platform:** LeetCode —
- **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
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `n × n` দাবার বোর্ডে `n`টা queen বসাতে হবে এমনভাবে যেন **কোনো দুটো queen একে অন্যকে আক্রমণ না করে**। দাবায় queen একই row, একই column, আর দুই কোনাকুনি (diagonal) বরাবর আক্রমণ করে। তোমার কাজ: সব রকম বৈধ সাজানো বের করা, প্রতিটা বোর্ড string-এর list হিসেবে — `'Q'` মানে queen, `'.'` মানে খালি।
```text
n = 4 -> 2টা বৈধ সাজ:
.Q.. ..Q.
...Q Q...
Q... ...Q
..Q. .Q..
```
### Input ও output {#8-example-input-and-output}
```text
Input : n=4 -> Output: 2টা বোর্ড (উপরে দেখানো)
Input : n=1 -> Output: [["Q"]]
Edge case 1 (অসম্ভব): n=2 -> Output: [] (কোনো সাজ নেই)
Edge case 2 (অসম্ভব): n=3 -> Output: []
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা office-এ `n` জন প্রহরী রাখতে হবে, প্রতিজন একটা করিডোর (row) পাহারা দেয়; কিন্তু কারও line-of-sight (column বা কোনাকুনি) যেন অন্য প্রহরীর ওপর না পড়ে। একটা করিডোরে একজনকে এমন জায়গায় দাঁড় করাও যেখানে আগের কারও দৃষ্টিরেখায় সে পড়ে না; না মিললে পিছিয়ে এসে অন্য জায়গা দেখো। সব রকম সংঘাতহীন বিন্যাসই উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 হয় না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: `n²`টা cell থেকে যেকোনো `n`টা cell বেছে queen বসানোর সব combination গড়ো, তারপর প্রতিটা বিন্যাসে কোনো দুটো queen পরস্পরকে আক্রমণ করে কিনা যাচাই করো।
```text
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 তাৎক্ষণিক।
### ছবিতে বোঝা {#7-visual-explanation}
`n=4`-এর **সব বৈধ partial placement** নিচে আছে। Label-এর list-এ row অনুযায়ী column থাকে; যেমন `[1,3,0]` মানে row 0→col 1, row 1→col 3, row 2→col 0। Attack করে এমন column recursive call হওয়ার আগেই বাদ যায়।
```mermaid
graph TD
q0["[]; search"]
q1["[0]; search"]
q2["[0, 2]; dead end"]
q1 -->|"row 1, col 2"| q2
q3["[0, 3]; search"]
q4["[0, 3, 1]; dead end"]
q3 -->|"row 2, col 1"| q4
q1 -->|"row 1, col 3"| q3
q0 -->|"row 0, col 0"| q1
q5["[1]; search"]
q6["[1, 3]; search"]
q7["[1, 3, 0]; search"]
q8["[1, 3, 0, 2]; record"]
q7 -->|"row 3, col 2"| q8
q6 -->|"row 2, col 0"| q7
q5 -->|"row 1, col 3"| q6
q0 -->|"row 0, col 1"| q5
q9["[2]; search"]
q10["[2, 0]; search"]
q11["[2, 0, 3]; search"]
q12["[2, 0, 3, 1]; record"]
q11 -->|"row 3, col 1"| q12
q10 -->|"row 2, col 3"| q11
q9 -->|"row 1, col 0"| q10
q0 -->|"row 0, col 2"| q9
q13["[3]; search"]
q14["[3, 0]; search"]
q15["[3, 0, 2]; dead end"]
q14 -->|"row 2, col 2"| q15
q13 -->|"row 1, col 0"| q14
q16["[3, 1]; dead end"]
q13 -->|"row 1, col 1"| q16
q0 -->|"row 0, col 3"| q13
```
দুটি leaf record হয়: `[1,3,0,2]` ও `[2,0,3,1]`। অন্য leaf-গুলো dead end; সেখান থেকে undo করে parent-এর পরের column চেষ্টা করতে হয়।
### ছোট input-এ ধাপে ধাপে {#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টা বোর্ড।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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 আবার খালি করো।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 করো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Permutations (#9)-এর "প্রতি মান একবার" (column permutation) + Generate Parentheses (#15)-এর early-validity গেট, এখানে তিনটা blocked-line set রূপে। [../patterns.md](../patterns.md)-এর constraint-backtracking pattern দেখো। এটা tracker-এর চারটা canonical interview shape-এর একটা — এখানে সবচেয়ে বেশি সময় দাও।
### পরের অনুশীলন {#22-similar-harder-problems}
- N-Queens II (শুধু গোনা) —