015 — Valid Sudoku¶

Source¶

Original source: Classic seen-set / signature-key exercise
Platform: LeetCode — https://leetcode.com/problems/valid-sudoku/
Topic: hash set (signatures)
Difficulty: Medium
Pattern: seen-set per unit
Basic idea inherited from: canonical-key signatures — (value, unit) জোড়াকে এক key বানাও

1. Problem in simple words¶

একটা 9 × 9 সুডোকু board দেওয়া আছে; কিছু ঘরে '1'–'9' অঙ্ক, বাকি ঘরে '.' (খালি)। board-টা বৈধ কি না বলতে হবে — অর্থাৎ ভরা ঘরগুলোর মধ্যে কোনো অঙ্ক একই সারিতে, একই কলামে, বা একই 3 × 3 box-এ দুবার নেই। (পুরো সমাধান করা যাবে কি না সেটা প্রশ্ন নয়, শুধু এখনকার অবস্থা valid কি না।)

একই সারিতে দুটো '5' → invalid
একই কলামে দুটো '8' → invalid
একই 3×3 box-এ দুটো '3' → invalid

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-এ অনায়াসে মিশে যায়।

6. Real-life analogy¶

ভাবো একটা পরীক্ষাহলে আসন বণ্টন: একটা rule "প্রতি সারিতে একই roll একবার", আরেকটা "প্রতি কলামে একবার", আরেকটা "প্রতি ব্লকে একবার"। তুমি প্রতিটা নিয়মের জন্য আলাদা খাতা না রেখে একটাই রেজিস্টারে লিখছ — "সারি 3-এ roll 5", "কলাম 7-এ roll 5", "ব্লক (1,2)-তে roll 5"। নতুন কাউকে বসানোর আগে রেজিস্টারে এই তিনটে এন্ট্রি আগে থেকেই আছে কি না দেখে নাও।

7. Visual explanation¶

প্রতিটা ভরা ঘর (r, c, v) তিনটা signature বানায়; box-id = (r//3, c//3):

ঘর (0,0)='5' → keys: ("row",0,"5"), ("col",0,"5"), ("box",0,0,"5")   → set-এ যোগ
ঘর (0,1)='3' → keys: ("row",0,"3"), ("col",1,"3"), ("box",0,0,"3")   → set-এ যোগ
...
ঘর (2,2)='5' → ("box",0,0,"5") কি set-এ আছে? হ্যাঁ! (0,0)-তে এসেছিল → invalid

একই box-এ দ্বিতীয় '5' আসতেই তার ("box",0,0,"5") signature collide করে — duplicate ধরা পড়ে।

8. Example input and output¶

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

9. Brute force thinking¶

প্রথম সরল চিন্তা: আলাদা আলাদাভাবে প্রতিটা সারি যাচাই করো, তারপর প্রতিটা কলাম, তারপর প্রতিটা box — প্রতিবার সেই unit-এর ভরা অঙ্কগুলো জড়ো করে duplicate আছে কি দেখো।

প্রতিটা সারির জন্য: ভরা অঙ্ক জড়ো করো, 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 একলাইনে এনে দেয়।

14. Step-by-step dry run¶

ছোট করে শুধু উপর-বাঁ box-এর দুটো ঘর ধরি, যেখানে (2,2) কে '5' করা হয়েছে:

(0,0)='5': keys ("row",0,"5"), ("col",0,"5"), ("box",0,0,"5") — কোনোটা set-এ নেই → তিনটাই যোগ।
মাঝের ভরা ঘরগুলো নিজ নিজ signature যোগ করে, কোনো সংঘর্ষ নেই।
(2,2)='5': box-id (2//3, 2//3) = (0,0); key ("box",0,0,"5") — এটা ধাপ 1-এ যোগ হয়েছিল! → পাওয়া গেল duplicate → return False।

15. Python solution¶

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 অটুট থাকে)।

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!।

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 করো।

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-র Pattern 3 ও 4-এ।

22. Similar harder problems¶

Group Anagrams — https://leetcode.com/problems/group-anagrams/ (এই tracker-এর #10; canonical key-র মূল)
Sudoku Solver — https://leetcode.com/problems/sudoku-solver/ (একই constraint, এবার backtracking দিয়ে ভরাও)
Valid Anagram — https://leetcode.com/problems/valid-anagram/ (এই tracker-এর #3; signature/count চিন্তার সরল রূপ)

23. Pattern learned¶

Seen-set per unit (signature key): একাধিক "এই unit-এ duplicate?" নিয়মকে (unit-id, value) signature-এ অনুবাদ করো, সব signature এক seen-set-এ রাখো — তিন রকম যাচাই একটা O(1) lookup-এ মিশে যায়, এক pass-এ।

24. Final summary¶

ভবিষ্যতের আমাকে: "এই row/col/box/group-এ duplicate আছে?" শুনলেই signature + seen-set মনে পড়বে। মূল কৌশল — প্রতিটা constraint-কে একটা স্বতন্ত্র key-তে অনুবাদ করো, তারপর hash set-কে collision ধরতে দাও। box-id সূত্র (r//3, c//3) মুখস্থ নয়, কেন কাজ করে সেটা বুঝে রাখা চাই।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।