022 — Sudoku Solver

Problem link ও উৎস

• Original source: Classic constraint backtracking exercise (fill a 9×9 Sudoku grid)
• Platform: LeetCode — https://leetcode.com/problems/sudoku-solver/
• 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

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

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

একটা 9 × 9 Sudoku বোর্ড দেওয়া আছে, কিছু ঘর ভরা ('1'–'9'), কিছু খালি ('.')। তোমার কাজ: খালি ঘরগুলো এমনভাবে ভরা যেন প্রতিটা row, প্রতিটা column, আর প্রতিটা 3×3 box-এ 1 থেকে 9 ঠিক একবার করে থাকে। সমাধান বোর্ডে in-place বসাও (well-formed puzzle-এর সমাধান একটাই)।

উদাহরণ

. = খালি; নিয়ম: প্রতি row, column, ও 3×3 box-এ 1–9 প্রতিটা ঠিক একবার।
একটি পূর্ণ 9×9 board ও প্রতিটি খালি ঘর ভরার ধাপ section 7-এ দেখানো আছে।

Input ও output

উদাহরণ

Input  : অর্ধেক-ভরা 9×9 বোর্ড (একটা বৈধ Sudoku puzzle)
Output : সম্পূর্ণ-ভরা বোর্ড — প্রতি row/column/box-এ 1–9 ঠিক একবার;
         দেওয়া (clue) ঘরগুলো অপরিবর্তিত।

যাচাই: প্রতি row sorted == "123456789", প্রতি column ও প্রতি 3×3 box একই।

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

ভাবো একটা schedule grid যেখানে প্রতি সারি একটা ঘর, প্রতি কলাম একটা দিন, আর কিছু block একসাথে rule মানে — প্রতিটা একক (সারি/কলাম/block)-এ একটা কাজ একবারই বসে। একটা খালি ঘরে এমন কাজ বসাও যা ওই সারি, ওই কলাম, ও ওই block-এ আগে নেই; না মিললে পিছিয়ে অন্য কাজ চেষ্টা করো। সব ঘর নিয়ম মেনে ভরে গেলেই হয়ে গেল।

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

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

ভিত্তি হলো 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"।

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

লুকানো 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-ই পুরো বৈধতা ধরে।

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

লাগে তিনটা set-এর তালিকা — rows[9], cols[9], boxes[9] (প্রতিটায় ওই unit-এ ব্যবহৃত অঙ্ক); একটা list empties (খালি cell-গুলোর (r,c), যেন একটানা সেগুলোই ভরি); board নিজে (in-place ভরতে); আর recursion-এর জন্য call stack।

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

প্রতি 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 না করে।

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

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা খালি cell-এ 1–9-এর সব সমন্বয় বসাও (9^(খালি cell-সংখ্যা) রকম), তারপর প্রতিটা সম্পূর্ণ বোর্ড Sudoku-নিয়ম মানে কিনা যাচাই করো।

উদাহরণ

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

কোথায় বেশি কাজ হচ্ছে

9^(খালি cell) জ্যোতির্বৈজ্ঞানিক — একটা সাধারণ puzzle-এ 50+ খালি cell মানে 9^50-এর বেশি বোর্ড, যার প্রায় সবই প্রথম দু-একটা cell-এই নিয়ম ভাঙে কিন্তু পুরো ভরার পরে ধরা পড়ে। backtracking প্রতি cell-এ বসানোর আগে তিন unit-set দিয়ে গেট দেয়: অবৈধ অঙ্ক চেষ্টাই করে না, আর একটা cell-এ কোনো অঙ্ক না বসলে সঙ্গে সঙ্গে backtrack করে — পুরো hopeless subtree ছেঁটে ফেলে। তাই বাস্তবে অল্প কিছু cell বসিয়েই সমাধানে পৌঁছায়।

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

মূল observation: প্রতিটা cell তিনটা unit-এর সদস্য, আর বৈধতা = তিন unit-এ অঙ্কটা অনুপস্থিত — তিনটা set-membership-এ পুরো check নেমে আসে। "পুরো বোর্ড ভরে যাচাই করব" না ভেবে ভাবো "এই খালি cell-এ এখন কোন অঙ্ক আইনসম্মত?" — locally সর্বোচ্চ 9, প্রায়ই অনেক কম প্রার্থী; গেটটা বসানোর আগেই।

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

আগে একবার পুরো বোর্ড 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।

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

মোচড়: একটা cell-এ অঙ্ক "বসিয়ে পরে যাচাই" নয় — বসানোর আগেই তিন unit-set জিজ্ঞেস করো "এটা চলবে?" আর backtracking-এ first-success short-circuit: যেহেতু well-formed puzzle-এর সমাধান একটাই, প্রথম True পেলেই পুরো চেইন True ফিরিয়ে থেমে যাও — সব সমাধান গোনার দরকার নেই।

ছবিতে বোঝা

সম্পূর্ণ ছোট dry run-এর জন্য মাত্র দুটি খালি cell-সহ বৈধ board নিই। . মানে খালি cell; কোনো row বা column বাদ দেওয়া হয়নি।

উদাহরণ

+-------+-------+-------+
| 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-ও দেখানো:

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

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 করে পরেরটি নিতে হবে।

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

Python

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

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

• 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 মিলিয়ে দেখা

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

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

সময়

worst case O(9^m) — m খালি cell, প্রতিটায় সর্বোচ্চ 9 চেষ্টা — কিন্তু তিন unit-set pruning বাস্তব puzzle-এ এটিকে নাটকীয়ভাবে কমিয়ে আনে (অধিকাংশ অঙ্ক প্রতি cell-এ আগেই বাতিল)। safe-check ও box-index O(1)।

অতিরিক্ত জায়গা

O(1) constraint-state হিসেবে — 27টা set, প্রতিটায় সর্বোচ্চ 9 (মোট ধ্রুব, কারণ বোর্ড স্থির 9×9); call stack গভীরতা = খালি cell-সংখ্যা ≤ 81 (ধ্রুব)। বোর্ড in-place, তাই বাড়তি বোর্ড-copy নেই।

যে ভুলগুলো এড়াতে হবে

• 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 ব্যবহার করো।

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

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

ভিত্তি: N-Queens (#19)-এর constraint backtracking — "এক একক ধরে নামো, কয়েকটা set দিয়ে clash check, placement-এর আগে গেট।" এখানে "line"-এর জায়গায় তিন ধরনের "unit" (row/column/box)। ../patterns.md-এর constraint-backtracking pattern দেখো। N-Queens-এর শৃঙ্খলা রপ্ত থাকলে Sudoku শুধু একটা তৃতীয় unit যোগ।

পরের অনুশীলন

• N-Queens (line-set constraint) — https://leetcode.com/problems/n-queens/ (এই tracker-এর #19)
• Word Search II (grid backtracking + trie) — https://leetcode.com/problems/word-search-ii/ (#23)
• Valid Sudoku (শুধু বৈধতা যাচাই, ভরা নয়) — https://leetcode.com/problems/valid-sudoku/

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

Constraint backtracking with multiple unit-sets: প্রতিটা cell যতগুলো constraint-unit-এর সদস্য (এখানে row/column/box — 3টা), ততগুলো set রাখো; placement-এর আগে সব unit-এ গেট দাও, in-place choose/un-choose করো, আর unique সমাধানে first-success short-circuit — grid-fill constraint problem-এর কঙ্কাল।

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

ভবিষ্যতের আমাকে: "Sudoku Solver = খালি cell ধরে নামো; প্রতি cell-এ rows[r], cols[c], boxes[(r//3)*3+c//3] তিন set দিয়ে 1–9 গেট; বসাও/recurse/আটকালে ফেরাও; go(k+1) True হলে থামো।" যখনই 'grid এমনভাবে ভরো যেন কয়েকটা unit নিয়ম মানে' শুনবে — এই multi-unit-set constraint backtracking skeleton মনে করবে।

---

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