022 — Sudoku Solver

Source

• 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

1. Problem in simple words

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

. = খালি; নিয়ম: প্রতি row, column, ও 3×3 box-এ 1–9 প্রতিটা ঠিক একবার।
আংশিক:  5 3 . | . 7 . | ...   ->   সমাধান:  5 3 4 | 6 7 8 | ...
        6 . . | 1 9 5 | ...               6 7 2 | 1 9 5 | ...

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 না করে।

6. Real-life analogy

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

7. Visual explanation

খালি cell ধরে index-ক্রমে নামি; প্রতিটায় 1–9 চেষ্টা, তিন unit-set safe হলে বসিয়ে এগোও, আটকালে backtrack:

                 go(k=0)  -> empties[0]=(0,2)
       d=1(box-এ আছে? skip) ... d=4(safe) ...
            বসাও -> go(k=1) -> empties[1]=(0,3)
                 d=6(safe) -> বসাও -> go(k=2) ...
                      ...
                 কোনো d বৈধ না -> '.' ফিরিয়ে False -> উপরে অন্য d

go(k == len(empties)) -> সব খালি ভরা -> True; True পেলেই থামো।

8. Example input and output

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

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

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা খালি 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

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 ফিরিয়ে থেমে যাও — সব সমাধান গোনার দরকার নেই।

14. Step-by-step dry run

solve_sudoku(board), প্রথম খালি cell (0,2) ধরে, go(k):

1. scan: rows/cols/boxes ভরা; empties = [(0,2), (0,3), ...]।
2. go(0): (0,2), box 0; d='1'..: row 0-এ 5,3 আছে; '4' তিন unit-এ নেই → বসাও; add; go(1)।
3. go(1): (0,3); '6' safe → বসাও → go(2)...।
4. কোথাও কোনো d বৈধ না হলে board='.' + set remove → False → উপরে পরের d।
5. শেষ খালি cell ভরলে go(len)=True; চেইন True ফিরে বোর্ড সম্পূর্ণ; board[0] = 5 3 4 6 7 8 9 1 2।

15. Python solution

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 খালি করো।

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

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

21. Which basic problem this inherits from

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

22. Similar harder problems

• 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/

23. Pattern learned

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-এর কঙ্কাল।

24. Final summary

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