Problem link ও উৎস
- **Original source:** Classic constraint backtracking exercise (fill a 9×9 Sudoku grid)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (constraint backtracking)
- **Difficulty:** Hard
- **Pattern:** constraint backtracking — প্রতি খালি cell-এ 1–9 চেষ্টা, 3টা unit-set দিয়ে গেট
- **Basic idea inherited from:** N-Queens-এর শৃঙ্খলা, প্রতি cell-এ 3টা unit-set
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `9 × 9` Sudoku বোর্ড দেওয়া আছে, কিছু ঘর ভরা (`'1'`–`'9'`), কিছু খালি (`'.'`)। তোমার কাজ: খালি ঘরগুলো এমনভাবে ভরা যেন প্রতিটা **row**, প্রতিটা **column**, আর প্রতিটা `3×3` **box**-এ `1` থেকে `9` ঠিক একবার করে থাকে। সমাধান বোর্ডে in-place বসাও (well-formed puzzle-এর সমাধান একটাই)।
```text
. = খালি; নিয়ম: প্রতি row, column, ও 3×3 box-এ 1–9 প্রতিটা ঠিক একবার।
একটি পূর্ণ 9×9 board ও প্রতিটি খালি ঘর ভরার ধাপ section 7-এ দেখানো আছে।
```
### Input ও output {#8-example-input-and-output}
```text
Input : অর্ধেক-ভরা 9×9 বোর্ড (একটা বৈধ Sudoku puzzle)
Output : সম্পূর্ণ-ভরা বোর্ড — প্রতি row/column/box-এ 1–9 ঠিক একবার;
দেওয়া (clue) ঘরগুলো অপরিবর্তিত।
যাচাই: প্রতি row sorted == "123456789", প্রতি column ও প্রতি 3×3 box একই।
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা schedule grid যেখানে প্রতি সারি একটা ঘর, প্রতি কলাম একটা দিন, আর কিছু block একসাথে rule মানে — প্রতিটা একক (সারি/কলাম/block)-এ একটা কাজ একবারই বসে। একটা খালি ঘরে এমন কাজ বসাও যা ওই সারি, ওই কলাম, ও ওই block-এ আগে নেই; না মিললে পিছিয়ে অন্য কাজ চেষ্টা করো। সব ঘর নিয়ম মেনে ভরে গেলেই হয়ে গেল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **N-Queens-এর শৃঙ্খলা, প্রতি cell-এ 3টা unit-set**। N-Queens-এ প্রতি row-এ একটা সিদ্ধান্ত আর তিনটা blocked-line (column, দুই diagonal); এখানে প্রতি খালি cell-এ একটা সিদ্ধান্ত (কোন অঙ্ক) আর তিনটা unit-constraint — ওই cell-এর row, column, ও `3×3` box। তিনটা set-এ already-used অঙ্ক রেখে safe-check O(1), ঠিক N-Queens-এর কৌশল, শুধু "line"-এর জায়গায় "unit"।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **প্রতিটা cell ঠিক তিনটা unit-এর সদস্য** — একটা row, একটা column, একটা box — আর প্রতিটা unit `1–9`-এর একটা permutation। তাই একটা অঙ্ক `d` cell `(r,c)`-তে বৈধ ঠিক তখনই, যখন `d` ওই row, ওই column, ও ওই box তিনটাতেই অনুপস্থিত। box-এর index বের হয় `(r // 3) * 3 + c // 3` দিয়ে — `3×3` ব্লককে 0–8 নম্বর দেয়। তিনটা set-এ এই membership-test-ই পুরো বৈধতা ধরে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
লাগে তিনটা **set-এর তালিকা** — `rows[9]`, `cols[9]`, `boxes[9]` (প্রতিটায় ওই unit-এ ব্যবহৃত অঙ্ক); একটা **list `empties`** (খালি cell-গুলোর `(r,c)`, যেন একটানা সেগুলোই ভরি); `board` নিজে (in-place ভরতে); আর recursion-এর জন্য **call stack**।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতি unit-এর জন্য আলাদা set রাখায় "এই অঙ্ক কি এই row/column/box-এ আছে?" check ও add/remove সবই O(1) — বারবার পুরো row/column/box scan করার দরকার নেই। `empties` list আগে থেকে বের করে রাখায় recursion শুধু খালি cell ধরে index-ক্রমে এগোয় (ভরা cell বারবার পেরোতে হয় না)। আর in-place ভরা + backtrack-এ `'.'` ফেরানো = choose/un-choose, যেন কোনো ভুল সিদ্ধান্ত leak না করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা খালি cell-এ `1–9`-এর সব সমন্বয় বসাও (`9^(খালি cell-সংখ্যা)` রকম), তারপর প্রতিটা সম্পূর্ণ বোর্ড Sudoku-নিয়ম মানে কিনা যাচাই করো।
```text
for every assignment of 1..9 to all empty cells: # 9^(#empty)
if every row, column, box has 1..9 exactly once:
return that board
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
`9^(খালি cell)` জ্যোতির্বৈজ্ঞানিক — একটা সাধারণ puzzle-এ 50+ খালি cell মানে `9^50`-এর বেশি বোর্ড, যার প্রায় সবই প্রথম দু-একটা cell-এই নিয়ম ভাঙে কিন্তু পুরো ভরার পরে ধরা পড়ে। backtracking প্রতি cell-এ বসানোর **আগে** তিন unit-set দিয়ে গেট দেয়: অবৈধ অঙ্ক চেষ্টাই করে না, আর একটা cell-এ কোনো অঙ্ক না বসলে সঙ্গে সঙ্গে backtrack করে — পুরো hopeless subtree ছেঁটে ফেলে। তাই বাস্তবে অল্প কিছু cell বসিয়েই সমাধানে পৌঁছায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রতিটা cell তিনটা unit-এর সদস্য, আর বৈধতা = তিন unit-এ অঙ্কটা অনুপস্থিত** — তিনটা set-membership-এ পুরো check নেমে আসে। "পুরো বোর্ড ভরে যাচাই করব" না ভেবে ভাবো "এই খালি cell-এ এখন কোন অঙ্ক আইনসম্মত?" — locally সর্বোচ্চ 9, প্রায়ই অনেক কম প্রার্থী; গেটটা বসানোর আগেই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
আগে একবার পুরো বোর্ড scan করে তিন unit-set ভরো ও `empties` বানাও। `go(k)`: base case `k == len(empties)` হলে `True` (সব ভরা)। নাহলে `(r,c) = empties[k]`, box `b = (r//3)*3 + c//3`; প্রতিটা অঙ্ক `d` `"1".."9"`: তিন set-এ থাকলে skip; নাহলে `board[r][c]=d` + তিন set-এ add (choose), `if go(k+1): return True` (explore), নাহলে `board[r][c]='.'` + তিন set থেকে remove (un-choose)। কোনো `d`-তে না হলে `return False`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** একটা cell-এ অঙ্ক "বসিয়ে পরে যাচাই" নয় — বসানোর আগেই তিন unit-set জিজ্ঞেস করো "এটা চলবে?" আর backtracking-এ first-success short-circuit: যেহেতু well-formed puzzle-এর সমাধান একটাই, প্রথম `True` পেলেই পুরো চেইন `True` ফিরিয়ে থেমে যাও — সব সমাধান গোনার দরকার নেই।
### ছবিতে বোঝা {#7-visual-explanation}
সম্পূর্ণ ছোট dry run-এর জন্য মাত্র দুটি খালি cell-সহ বৈধ board নিই। `.` মানে খালি cell; কোনো row বা column বাদ দেওয়া হয়নি।
```text
+-------+-------+-------+
| 5 3 . | . 7 8 | 9 1 2 |
| 6 7 2 | 1 9 5 | 3 4 8 |
| 1 9 8 | 3 4 2 | 5 6 7 |
+-------+-------+-------+
| 8 5 9 | 7 6 1 | 4 2 3 |
| 4 2 6 | 8 5 3 | 7 9 1 |
| 7 1 3 | 9 2 4 | 8 5 6 |
+-------+-------+-------+
| 9 6 1 | 5 3 7 | 2 8 4 |
| 2 8 7 | 4 1 9 | 6 3 5 |
| 3 4 5 | 2 8 6 | 1 7 9 |
+-------+-------+-------+
```
| call | cell | 1–9-এর মধ্যে বৈধ digit | কাজ |
| --- | --- | --- | --- |
| go(0) | (0,2), box 0 | শুধু 4 | board-এ 4 বসাও; row/col/box set-এ 4 যোগ; go(1) |
| go(1) | (0,3), box 1 | শুধু 6 | 6 বসাও; তিন set-এ যোগ; go(2) |
| go(2) | আর খালি cell নেই | — | True |
| go(1) ফেরে | — | — | True পেয়ে True ফেরায় |
| go(0) ফেরে | — | — | True পেয়ে True ফেরায় |
প্রথম row হলো `5 3 4 | 6 7 8 | 9 1 2`; বাকি আট row অপরিবর্তিত। সাধারণ puzzle-এ একাধিক digit বৈধ হতে পারে। নিচের control-flow-এ ব্যর্থ branch-এর undo-ও দেখানো:
```mermaid
flowchart TD
A["go(k)"] --> B{"সব খালি cell পূর্ণ?"}
B -->|হ্যাঁ| T["return True"]
B -->|না| C["পরের legal digit নাও"]
C --> D{"digit আছে?"}
D -->|না| F["return False"]
D -->|হ্যাঁ| E["board ও তিন set-এ digit বসাও"]
E --> G["go(k+1)"]
G --> H{"সফল?"}
H -->|হ্যাঁ| T
H -->|না| U["board-এ . ফেরাও; তিন set থেকে digit সরাও"]
U --> C
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Section 7-এর দুই খালি cell-এর board ব্যবহার করি।
1. `empties=[(0,2),(0,3)]`; সব ভরা cell থেকে row/column/box set তৈরি।
2. `(0,2)`-তে row-তে 4 ও 6 অনুপস্থিত, কিন্তু column 2-তে 6 আছে। তাই শুধু 4 legal; সেটি বসাও।
3. `(0,3)`-তে শুধু 6 legal; সেটি বসাও।
4. `k=2=len(empties)` হওয়ায় True; দুই parent call-ও True ফেরায়।
5. সম্পূর্ণ row/column/box check করলে প্রতিটিতে 1–9 একবার করে আছে।
নিচের code test-এ আরও বেশি খালি ঘরওয়ালা puzzle আছে। সেখানে প্রথমে locally legal digit বেছে নিলেই তা final solution-এর digit হবে এমন নিশ্চয়তা নেই; ব্যর্থ হলে undo করে পরেরটি নিতে হবে।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def solve_sudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
empties = []
for r in range(9): # প্রথমে state বানাও
for c in range(9):
v = board[r][c]
if v == ".":
empties.append((r, c))
else:
rows[r].add(v); cols[c].add(v); boxes[(r // 3) * 3 + c // 3].add(v)
def go(k):
if k == len(empties): # base case: সব খালি cell ভরা
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in "123456789":
if d in rows[r] or d in cols[c] or d in boxes[b]:
continue # গেট: এই unit-এ অঙ্কটা আছে
board[r][c] = d # CHOOSE
rows[r].add(d); cols[c].add(d); boxes[b].add(d)
if go(k + 1): # EXPLORE
return True # short-circuit: সমাধান পেলাম
board[r][c] = "." # UN-CHOOSE
rows[r].discard(d); cols[c].discard(d); boxes[b].discard(d)
return False # কোনো অঙ্ক বসল না -> backtrack
go(0)
return board
# ---- validity helper: সমাধান সঠিক কিনা (memorized উত্তরের ওপর নির্ভর নয়) ----
def is_valid_solution(board):
for i in range(9):
if sorted(board[i]) != list("123456789"):
return False
if sorted(board[r][i] for r in range(9)) != list("123456789"):
return False
for br in range(0, 9, 3):
for bc in range(0, 9, 3):
box = [board[br + dr][bc + dc] for dr in range(3) for dc in range(3)]
if sorted(box) != list("123456789"):
return False
return True
# ---- tests ----
puzzle = [list(row) for row in [
"53..7....", "6..195...", ".98....6.",
"8...6...3", "4..8.3..1", "7...2...6",
".6....28.", "...419..5", "....8..79"]]
given = [(r, c, puzzle[r][c]) for r in range(9) for c in range(9) if puzzle[r][c] != "."]
solved = solve_sudoku(puzzle)
assert is_valid_solution(solved) # প্রতি row/col/box-এ 1–9
assert all(solved[r][c] == v for r, c, v in given) # দেওয়া clue অটুট
assert all(solved[r][c] != "." for r in range(9) for c in range(9)) # সব ভরা
assert "".join(solved[0]) == "534678912" # প্রথম row (unique সমাধান)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `rows/cols/boxes = [set() ...]` — তিন ধরনের unit-এর প্রতিটির জন্য ব্যবহৃত-অঙ্কের set।
- প্রথম double loop — দেওয়া বোর্ড পড়ে set ভরা ও `empties` জমা।
- `if k == len(empties): return True` — base case: সব খালি cell ভরে গেছে।
- `b = (r // 3) * 3 + c // 3` — `(r,c)` কোন `3×3` box-এ তার 0–8 index।
- `if d in rows[r] or d in cols[c] or d in boxes[b]: continue` — গেট: তিন unit-এর কোথাও অঙ্কটা থাকলে skip।
- `board[r][c]=d; rows[r].add(d); ...` — CHOOSE: অঙ্ক বসিয়ে তিন unit-এ mark।
- `if go(k+1): return True` — EXPLORE + short-circuit: নিচে সমাধান হলে আর খুঁজি না।
- `board[r][c]="."; ...discard(d)` — UN-CHOOSE: অঙ্ক তুলে তিন unit খালি করো।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`solve_sudoku`: প্রথমে state বানিয়ে খালি cell ধরে index-ক্রমে নামে; প্রতিটায় তিন unit-set গেট দিয়ে কেবল বৈধ অঙ্ক চেষ্টা করে, আটকালে backtrack। well-formed puzzle-এর সমাধান unique, তাই first-success short-circuit-ই যথেষ্ট। test-এ memorized পুরো উত্তরের ওপর নির্ভর না করে `is_valid_solution` দিয়ে প্রতি row/column/box যাচাই করি, দেওয়া clue অটুট ও সব cell ভরা নিশ্চিত করি; প্রথম row `534678912`। সব মিলে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
worst case **O(9^m)** — `m` খালি cell, প্রতিটায় সর্বোচ্চ 9 চেষ্টা — কিন্তু তিন unit-set pruning বাস্তব puzzle-এ এটিকে নাটকীয়ভাবে কমিয়ে আনে (অধিকাংশ অঙ্ক প্রতি cell-এ আগেই বাতিল)। safe-check ও box-index O(1)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** constraint-state হিসেবে — 27টা set, প্রতিটায় সর্বোচ্চ 9 (মোট ধ্রুব, কারণ বোর্ড স্থির 9×9); call stack গভীরতা = খালি cell-সংখ্যা ≤ 81 (ধ্রুব)। বোর্ড in-place, তাই বাড়তি বোর্ড-copy নেই।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- box index ভুল — `(r//3)*3 + c//3`-এর বদলে `r//3 + c//3` বা `r*3+c` লেখা; তাহলে box-constraint ভাঙে।
- backtrack-এ `board[r][c]='.'` বা set-discard ভুলে যাওয়া — ভুল অঙ্ক leak করে পরের branch দূষিত করে।
- `if go(k+1): return True` short-circuit বাদ দিয়ে চলতে থাকা — unique সমাধানেও অযথা কাজ; প্রথম `True`-তে থামো।
- প্রতি cell-এ পুরো row/column/box scan করে check — ধীর; তিন set ব্যবহার করো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: N-Queens (#19)-এর constraint backtracking — "এক একক ধরে নামো, কয়েকটা set দিয়ে clash check, placement-এর আগে গেট।" এখানে "line"-এর জায়গায় তিন ধরনের "unit" (row/column/box)। [../patterns.md](../patterns.md)-এর constraint-backtracking pattern দেখো। N-Queens-এর শৃঙ্খলা রপ্ত থাকলে Sudoku শুধু একটা তৃতীয় unit যোগ।
### পরের অনুশীলন {#22-similar-harder-problems}
- N-Queens (line-set constraint) —