Problem link ও উৎস
- **Original source:** Classic seen-set / signature-key exercise
- **Platform:** LeetCode —
- **Topic:** hash set (signatures)
- **Difficulty:** Medium
- **Pattern:** seen-set per unit
- **Basic idea inherited from:** canonical-key signatures — (value, unit) জোড়াকে এক key বানাও
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `9 × 9` সুডোকু board দেওয়া আছে; কিছু ঘরে `'1'`–`'9'` অঙ্ক, বাকি ঘরে `'.'` (খালি)। board-টা **বৈধ** কি না বলতে হবে — অর্থাৎ ভরা ঘরগুলোর মধ্যে কোনো অঙ্ক একই সারিতে, একই কলামে, বা একই `3 × 3` box-এ দুবার নেই। (পুরো সমাধান করা যাবে কি না সেটা প্রশ্ন নয়, শুধু এখনকার অবস্থা valid কি না।)
```text
একই সারিতে দুটো '5' → invalid
একই কলামে দুটো '8' → invalid
একই 3×3 box-এ দুটো '3' → invalid
```
### Input ও output {#8-example-input-and-output}
```text
Input : নিচের valid board Output: True
Input : valid board, কিন্তু (0,0)='8' Output: False (কলাম 0-এ দুটো 8)
Input : valid board, কিন্তু (2,2)='5' Output: False (উপর-বাঁ box-এ দুটো 5)
valid board:
5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা পরীক্ষাহলে আসন বণ্টন: একটা rule "প্রতি সারিতে একই roll একবার", আরেকটা "প্রতি কলামে একবার", আরেকটা "প্রতি ব্লকে একবার"। তুমি প্রতিটা নিয়মের জন্য আলাদা খাতা না রেখে একটাই রেজিস্টারে লিখছ — "সারি 3-এ roll 5", "কলাম 7-এ roll 5", "ব্লক (1,2)-তে roll 5"। নতুন কাউকে বসানোর আগে রেজিস্টারে এই তিনটে এন্ট্রি আগে থেকেই আছে কি না দেখে নাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দুটো pattern মেশায়। মূলটা **seen-set** (Pattern 4) — "এটা কি আগে দেখেছি?" O(1)-এ। কিন্তু চালাকিটা **canonical key / signature** থেকে (Pattern 3, Group Anagrams-এর আত্মীয়): প্রতিটা ভরা ঘরকে কয়েকটা signature-key-তে অনুবাদ করি, তারপর সব signature একটাই set-এ রেখে duplicate ধরি।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: তিনটা আলাদা "no-duplicate" নিয়ম (সারি, কলাম, box) আসলে একই ধাঁচের — "একটা নির্দিষ্ট unit-এর ভেতরে কোনো অঙ্ক দুবার নয়"। যদি প্রতিটা constraint-কে একটা স্বতন্ত্র **signature** দিয়ে চিহ্নিত করি — যেমন `("row", r, v)`, `("col", c, v)`, `("box", r//3, c//3, v)` — তাহলে তিন রকম নিয়ম একটামাত্র "এই signature কি আগে দেখেছি?" প্রশ্নে মিশে যায়। আর box-id বের করার সূত্র `(r//3, c//3)` — integer division দিয়ে 9টা box-কে (0,0)..(2,2)-তে ভাগ করে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash set**, যাতে সব দেখা signature (tuple) জমে। tuple hashable, তাই সরাসরি set-এ রাখা যায়। চাইলে তিনটা আলাদা set (row/col/box)-ও রাখা যায়, কিন্তু একটামাত্র set আর স্বতন্ত্র prefix (`"row"/"col"/"box"`) দিয়ে কাজটা পরিষ্কার থাকে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা ভরা ঘরে আমরা তিনটা "আগে দেখেছি?" check করি — set গড়ে O(1)-এ উত্তর দেয়। মোট 81টা ঘর, প্রতিটায় ধ্রুবক কাজ, তাই পুরো যাচাই **O(1)** (ধ্রুবক 9×9)। List হলে প্রতিটা check O(n) হতো — অযথা ধীর। signature-কে tuple বানানোয় তিন রকম constraint একই set-এ অনায়াসে মিশে যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: আলাদা আলাদাভাবে প্রতিটা সারি যাচাই করো, তারপর প্রতিটা কলাম, তারপর প্রতিটা box — প্রতিবার সেই unit-এর ভরা অঙ্কগুলো জড়ো করে duplicate আছে কি দেখো।
```text
প্রতিটা সারির জন্য: ভরা অঙ্ক জড়ো করো, duplicate আছে?
প্রতিটা কলামের জন্য: একই
প্রতিটা box-এর জন্য: একই
যেকোনো জায়গায় duplicate পেলে False
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
কাজ-পরিমাণে এটা ভয়ংকর ধীর নয় (board স্থির 9×9), কিন্তু এটা **তিনবার আলাদা করে board scan করে** আর তিন রকম collection আলাদাভাবে সামলায় — কোড দীর্ঘ, ভুলের সুযোগ বেশি, আর box-indexing হাতে হাতে করতে গিয়ে গুলিয়ে যায়। আসল অপচয় গতির নয়, **পুনরাবৃত্তি ও জটিলতার** — একই "duplicate আছে?" যুক্তি তিনবার লেখা।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **সারি, কলাম আর box — তিনটাই একই নিয়মের তিনটা রূপ।** প্রতিটা ঘরকে যদি তিনটা স্বতন্ত্র signature দিই (কোন unit + কোন value), তাহলে তিন রকম যাচাই একটামাত্র seen-set lookup-এ মিশে যায়, আর পুরো board মাত্র একবার scan করলেই চলে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা খালি `set` নাও। 81টা ঘরের উপর একবার হাঁটো; খালি হলে skip। ভরা ঘর `(r, c, v)`-এর জন্য তিনটা signature বানাও — `("row", r, v)`, `("col", c, v)`, `("box", r//3, c//3, v)`। যেকোনোটা আগে set-এ থাকলে duplicate → `False`। নইলে তিনটাই set-এ যোগ করে এগোও। শেষ পর্যন্ত নির্ঝঞ্ঝাট হলে `True`। এক pass, ধ্রুবক কাজ।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** *একাধিক "এই unit-এ duplicate?" নিয়মকে আলাদা না সামলে, প্রতিটা ঘরকে (unit-id, value) signature-এ অনুবাদ করো আর একটাই seen-set-এ ফেলে দাও।* signature-চিন্তা (Pattern 3) আর seen-set (Pattern 4) এখানে হাত মিলিয়ে তিনটা constraint একলাইনে এনে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
ছোট trace-এ শুধু তিনটি ভরা cell ধরি, বাকি cell খালি। `(0,0)=5`, `(0,1)=3`, `(2,2)=5`। Row/column আলাদা হলেও তিনটিই উপরের বাঁ 3×3 box-এ।
```text
+---+---+---+
| 5 | 3 | . |
+---+---+---+
| . | . | . |
+---+---+---+
| . | . | 5 |
+---+---+---+
```
| cell | row key | column key | box key | সিদ্ধান্ত |
| --- | --- | --- | --- | --- |
| (0,0)=5 | (row,0,5) | (col,0,5) | (box,0,0,5) | তিনটি নতুন: যোগ |
| (0,1)=3 | (row,0,3) | (col,1,3) | (box,0,0,3) | তিনটি নতুন: যোগ |
| (2,2)=5 | (row,2,5) | (col,2,5) | (box,0,0,5) | box key আগে আছে: False |
এটি একই signature-এর duplicate, hash collision বোঝানো হচ্ছে না। Empty cell `.`-এর জন্য কোনো key তৈরি হয় না।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
ছোট করে শুধু উপর-বাঁ box-এর দুটো ঘর ধরি, যেখানে `(2,2)` কে `'5'` করা হয়েছে:
1. `(0,0)='5'`: keys `("row",0,"5")`, `("col",0,"5")`, `("box",0,0,"5")` — কোনোটা set-এ নেই → তিনটাই যোগ।
2. মাঝের ভরা ঘরগুলো নিজ নিজ signature যোগ করে, কোনো সংঘর্ষ নেই।
3. `(2,2)='5'`: box-id `(2//3, 2//3) = (0,0)`; key `("box",0,0,"5")` — এটা ধাপ 1-এ যোগ হয়েছিল! → পাওয়া গেল duplicate → `return False`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import copy
def is_valid_sudoku(board):
seen = set() # canonical signature গুলো
for r in range(9):
for c in range(9):
val = board[r][c]
if val == ".":
continue
keys = (
("row", r, val),
("col", c, val),
("box", r // 3, c // 3, val),
)
for key in keys:
if key in seen:
return False
seen.add(key)
return True
# ---- tests ----
valid = [
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"],
]
assert is_valid_sudoku(valid) == True
col_bad = copy.deepcopy(valid)
col_bad[0][0] = "8" # column 0-এ দুটো 8
assert is_valid_sudoku(col_bad) == False
box_bad = copy.deepcopy(valid)
box_bad[2][2] = "5" # উপর-বাঁ box-এ দুটো 5
assert is_valid_sudoku(box_bad) == False
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `seen = set()` — সব দেখা signature এক জায়গায়।
- `for r in range(9): for c in range(9)` — 81টা ঘরের উপর একবার হাঁটি।
- `if val == ".": continue` — খালি ঘর constraint তৈরি করে না।
- `keys = (("row", r, val), ("col", c, val), ("box", r // 3, c // 3, val))` — তিনটা স্বতন্ত্র signature; prefix স্ট্রিং তিন রকম unit আলাদা রাখে।
- `for key in keys: if key in seen: return False` — যেকোনো signature আগে থাকলে duplicate।
- `seen.add(key)` — নইলে নতুন signature নথিভুক্ত।
- test-এ `copy.deepcopy` দিয়ে valid board নকল করে এক ঘর বদলে invalid case বানাই (মূল board অটুট থাকে)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`valid` board-এ কোনো signature দুবার আসে না → `True`। `col_bad`-এ `(0,0)` কে `'8'` করায় কলাম 0-এ `(3,0)`-র `'8'`-এর সাথে `("col",0,"8")` সংঘর্ষ → `False`। `box_bad`-এ `(2,2)` কে `'5'` করায় উপর-বাঁ box-এ `(0,0)`-র `'5'`-এর সাথে `("box",0,0,"5")` সংঘর্ষ → `False`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(1)** কার্যত — board স্থির 81টা ঘর, প্রতিটায় ধ্রুবক তিনটা set operation। সাধারণ আকারে `n × n` হলে O(n^2)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** কার্যত — set-এ সর্বোচ্চ `9×9×3` signature, যা স্থির। সাধারণ আকারে O(n^2)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- box-id ভুল করা — `(r//3, c//3)` ব্যবহার করতে হবে; `r//3 * 3 + c//3` দিয়ে একক সংখ্যাও চলে, কিন্তু `(r/3, c/3)` (float) বা `(r//3, c)` ভুল box দেয়।
- তিন রকম signature-কে আলাদা না করা — prefix (`"row"/"col"/"box"`) না দিলে `(0, "5")` মানে row 0 নাকি col 0 গুলিয়ে যায়।
- খালি ঘরকেও signature বানানো — `'.'` কে value ধরলে ভুয়া duplicate ধরা পড়বে; আগে skip করো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: seen-set (Pattern 4)-এর "আগে দেখেছি?" আর canonical-key signature (Pattern 3, Group Anagrams #10-এর আত্মীয়)। এই note দেখায় কীভাবে দুটো hashing pattern একসাথে একটা grid-constraint problem সারে। সম্পূর্ণ আলোচনা [../patterns.md](../patterns.md)-র Pattern 3 ও 4-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Group Anagrams —