015 — Valid Sudoku¶

Problem link ও উৎস

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 বানাও

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

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

উদাহরণ

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

Input ও 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

চেনা উদাহরণে বোঝা¶

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

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এটা দুটো pattern মেশায়। মূলটা seen-set (Pattern 4) — "এটা কি আগে দেখেছি?" O(1)-এ। কিন্তু চালাকিটা canonical key / signature থেকে (Pattern 3, Group Anagrams-এর আত্মীয়): প্রতিটা ভরা ঘরকে কয়েকটা signature-key-তে অনুবাদ করি, তারপর সব signature একটাই set-এ রেখে duplicate ধরি।

ভেতরের যুক্তি¶

লুকানো 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)-তে ভাগ করে।

কী দিয়ে তথ্য রাখব¶

একটা hash set, যাতে সব দেখা signature (tuple) জমে। tuple hashable, তাই সরাসরি set-এ রাখা যায়। চাইলে তিনটা আলাদা set (row/col/box)-ও রাখা যায়, কিন্তু একটামাত্র set আর স্বতন্ত্র prefix ("row"/"col"/"box") দিয়ে কাজটা পরিষ্কার থাকে।

এটি কেন উপযুক্ত¶

প্রতিটা ভরা ঘরে আমরা তিনটা "আগে দেখেছি?" check করি — set গড়ে O(1)-এ উত্তর দেয়। মোট 81টা ঘর, প্রতিটায় ধ্রুবক কাজ, তাই পুরো যাচাই O(1) (ধ্রুবক 9×9)। List হলে প্রতিটা check O(n) হতো — অযথা ধীর। signature-কে tuple বানানোয় তিন রকম constraint একই set-এ অনায়াসে মিশে যায়।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

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

উদাহরণ

প্রতিটা সারির জন্য: ভরা অঙ্ক জড়ো করো, duplicate আছে?
প্রতিটা কলামের জন্য: একই
প্রতিটা box-এর জন্য: একই
যেকোনো জায়গায় duplicate পেলে False

কোথায় বেশি কাজ হচ্ছে¶

কাজ-পরিমাণে এটা ভয়ংকর ধীর নয় (board স্থির 9×9), কিন্তু এটা তিনবার আলাদা করে board scan করে আর তিন রকম collection আলাদাভাবে সামলায় — কোড দীর্ঘ, ভুলের সুযোগ বেশি, আর box-indexing হাতে হাতে করতে গিয়ে গুলিয়ে যায়। আসল অপচয় গতির নয়, পুনরাবৃত্তি ও জটিলতার — একই "duplicate আছে?" যুক্তি তিনবার লেখা।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: সারি, কলাম আর box — তিনটাই একই নিয়মের তিনটা রূপ। প্রতিটা ঘরকে যদি তিনটা স্বতন্ত্র signature দিই (কোন unit + কোন value), তাহলে তিন রকম যাচাই একটামাত্র seen-set lookup-এ মিশে যায়, আর পুরো board মাত্র একবার scan করলেই চলে।

আরও কম কাজে সমাধান¶

একটা খালি 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, ধ্রুবক কাজ।

ভাবনার পরিবর্তন¶

মোচড়: একাধিক "এই unit-এ duplicate?" নিয়মকে আলাদা না সামলে, প্রতিটা ঘরকে (unit-id, value) signature-এ অনুবাদ করো আর একটাই seen-set-এ ফেলে দাও। signature-চিন্তা (Pattern 3) আর seen-set (Pattern 4) এখানে হাত মিলিয়ে তিনটা constraint একলাইনে এনে দেয়।

ছবিতে বোঝা¶

ছোট trace-এ শুধু তিনটি ভরা cell ধরি, বাকি cell খালি। (0,0)=5, (0,1)=3, (2,2)=5। Row/column আলাদা হলেও তিনটিই উপরের বাঁ 3×3 box-এ।

উদাহরণ

+---+---+---+
| 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-এ ধাপে ধাপে¶

ছোট করে শুধু উপর-বাঁ 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।

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

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 মিলিয়ে দেখা¶

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

খরচ ও সাধারণ ভুল¶

সময়¶

O(1) কার্যত — board স্থির 81টা ঘর, প্রতিটায় ধ্রুবক তিনটা set operation। সাধারণ আকারে n × n হলে O(n^2)।

অতিরিক্ত জায়গা¶

O(1) কার্যত — set-এ সর্বোচ্চ 9×9×3 signature, যা স্থির। সাধারণ আকারে O(n^2)।

যে ভুলগুলো এড়াতে হবে¶

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

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: seen-set (Pattern 4)-এর "আগে দেখেছি?" আর canonical-key signature (Pattern 3, Group Anagrams #10-এর আত্মীয়)। এই note দেখায় কীভাবে দুটো hashing pattern একসাথে একটা grid-constraint problem সারে। সম্পূর্ণ আলোচনা ../patterns.md-র Pattern 3 ও 4-এ।

পরের অনুশীলন¶

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 চিন্তার সরল রূপ)

কৌশলটি মনে রাখুন¶

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

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "এই 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।