Backtracking problems — N-Queens, Sudoku solver, all permutations - subsets

3.7.17 · Coding › Algorithm Paradigms

Backtracking exist kyun karta hai?

WHAT hai search space? Ek tree. Har node = ek partial solution. Har edge = "ek aur choice karo." Leaves = complete candidates.

HOW hum isko walk karte hain? Recursive DFS with this universal skeleton:

"Un-choose" line hi backtracking ko plain recursion se alag banati hai: state shared aur mutated hoti hai, isliye sibling branch try karne se pehle usse restore karna zaroori hai.

Figure — Backtracking problems — N-Queens, Sudoku solver, all permutations - subsets

Pattern 1 — All Subsets (sabse simple skeleton)

$2^{n}$ kyun? Har element independently in ya out hai → $2 \times 2 \times \dots = 2^{n}$ .

HOW — index i par, "take nums[i]" vs "skip it" branch karo:

def subsets(nums):
    res, path = [], []
    def bt(i):
        if i == len(nums):
            res.append(path[:])      # copy! path mutate hoti rehti hai
            return
        bt(i+1)                      # skip nums[i]
        path.append(nums[i])         # choose
        bt(i+1)                      # explore
        path.pop()                   # un-choose
    bt(0)
    return res

Pattern 2 — All Permutations

$n!$ kyun? First slot ke liye $n$ choices, next ke liye $n - 1$ , … $= n!$ .

HOW — track karo kaun se elements used hain:

def permute(nums):
    res, path, used = [], [], [False]*len(nums)
    def bt():
        if len(path) == len(nums):
            res.append(path[:]); return
        for i in range(len(nums)):
            if used[i]: continue     # pruning: har element ek baar
            used[i] = True; path.append(nums[i])   # choose
            bt()                                    # explore
            path.pop(); used[i] = False             # un-choose
    bt()
    return res

Pattern 3 — N-Queens

Column/diagonal $O (1)$ mein kaise check karein?

Same column → pehle cols[c] dekha hua.
Same ↘ diagonal: woh cells jahan row - col constant hai. (Derive karo: down-right move karne par r aur c dono mein 1 add hota hai, toh r-c unchanged rehta hai.)
Same ↗ anti-diagonal: row + col constant hota hai.

Toh hum teen sets rakhte hain: cols, diag (r-c), anti (r+c).

def solveNQueens(n):
    res = []
    cols, diag, anti = set(), set(), set()
    board = [['.']*n for _ in range(n)]
    def bt(r):
        if r == n:
            res.append([''.join(row) for row in board]); return
        for c in range(n):
            if c in cols or (r-c) in diag or (r+c) in anti:
                continue                         # attacked square prune karo
            cols.add(c); diag.add(r-c); anti.add(r+c)   # choose
            board[r][c] = 'Q'
            bt(r+1)                                       # explore
            cols.remove(c); diag.remove(r-c); anti.remove(r+c)  # un-choose
            board[r][c] = '.'
    bt(0)
    return res

Pattern 4 — Sudoku Solver

HOW — agla empty cell dhundho, digits 1–9 try karo, recurse karo, failure par undo karo:

def solveSudoku(board):                # board: list of lists, '.' = empty
    def ok(r, c, ch):
        b = (r//3)*3 + c//3            # box index
        for i in range(9):
            if board[r][i]==ch: return False     # row
            if board[i][c]==ch: return False     # col
            if board[(b//3)*3 + i//3][(b%3)*3 + i%3]==ch: return False  # box
        return True
    def bt():
        for r in range(9):
            for c in range(9):
                if board[r][c]=='.':
                    for ch in '123456789':
                        if ok(r,c,ch):
                            board[r][c]=ch     # choose
                            if bt(): return True   # explore
                            board[r][c]='.'    # un-choose
                    return False               # koi digit kaam nahi kiya → dead end
        return True                            # koi empty cell nahi → solved
    bt()

Steel-manned mistakes

Recall Feynman: 12-saal ke bachche ko explain karo

Socho tum ek maze haath se solve kar rahe ho. Tum aage chalte ho choices banate hue. Agar wall milti hai, tum pichli fork tak wapas chalte ho aur alag raasta try karte ho — poora maze restart nahi karte. Backtracking wahi hai: ek step try karo, agar hopeless lage toh mita do aur doosra try karo. Queens ke liye, tum chess queens ko ek row at a time place karte ho; agar nayi queen ko capture kiya ja sakta hai, usse uthao aur slide karo. Woh "uthao aur box mein wapas rakho" hi secret move hai.

Flashcards

Backtracking kis structure par kaun sa traversal hai?

Tree of partial solutions par DFS.

Backtracking ke teen universal steps

Choose → Explore (recurse) → Un-choose (undo).

Solution record karte waqt path[:] copy kyun karo?

path in-place mutate hoti hai; reference store karne par saare answers same (eventually empty) list ban jaate hain.

N-Queens: same ↘ diagonal O(1) mein kaise detect karein?

Us par saari cells constant r - c share karti hain; r-c ka set rakho.

N-Queens: ↗ anti-diagonal ki key?

Constant r + c.

N-Queens mein ek queen per row kyun place karte hain?

Row conflicts automatically remove ho jaate hain aur branching N² se N per level tak cut ho jaati hai.

Cell (r,c) ke liye Sudoku box index formula?

(r//3)*3 + c//3.

Sudoku solver bool return kyun karta hai lekin N-Queens nahi?

Sudoku ko ek solution chahiye → success par short-circuit; N-Queens sab collect karta hai → sab kuch explore karo.

All subsets vs all permutations ka time/branching?

Subsets

2^{n}

, permutations

n!

Backtracking mein "pruning" kya hoti hai?

Ek partial choice ko early reject karna (recurse karne se pehle) jab woh kisi valid solution tak nahi pahunch sakti.

Agar un-choose step skip kar do toh kya galat hoga?

Sibling branches stale state inherit karti hain → galat/duplicate results.

Connections

Depth-First-Search — backtracking IS DFS with explicit undo.
Recursion-and-the-call-stack — implicit stack partial state store karta hai.
Branch-and-Bound — pruning + optimization ke liye numeric bound.
Constraint-Satisfaction-Problems — Sudoku/N-Queens CSPs hain.
Dynamic-Programming — jab subproblems overlap karein, search ko memoize karo.
Time-Complexity-of-Recursive-Algorithms — search tree mein nodes count karna.