Lesson 4 � Intermediate

N-Queens & Sudoku Solver

N-Queens problem backtracking ka sabse famous application hai. N queens ko N�N board pe place karna hai jismein koi two queens ek doosre ko attack na kar sakein. Ye problem recursion + constraint checking ka perfect example hai.

? 25 min✓ Intermediate✓ Backtracking framework

N-Queens kya hai?

WHAT

N�N chess board pe N queens place karni hain. Constraint: koi do queens ek doosre ko attack nahi kar sakti � same row, same column, same diagonal mein nahi honi chahiye. Har row mein exactly ek queen hogi.

WHEN

Ye classic backtracking problem hai. Row-by-row placement karte hain. Har row mein har column check karte hain � safe hai toh queen place karo, nahi toh next column try karo. Agar koi column safe nahi hai toh previous row pe backtrack karo.

WHERE

N-Queens (LeetCode 51 & 52), Sudoku Solver (LeetCode 37), Word Search, Rat in Maze � ye sab similar backtracking pattern follow karte hain with constraint checking.

Mental Model: Imagine karo tum ek chess player ho. Tumhe N queens place karni hain row by row. Har row mein tum har column check karte ho � "Kya yahan queen rakh sakti hoon?" Agar haan toh rakh do aur agle row pe jao. Agar nahi mil raha toh peeche jaao aur pichli row ki queen ki position change karo.

4�4 Board Visualization

Chalo 4-Queens ka example dekhte hain step by step:

# 4-Queens Solution � Step by Step
#
# Step 1: Row 0 mein col 0 pe queen
# Q . . .
# . . . .
# . . . .
# . . . .
#
# Step 2: Row 1 mein col 2 pe queen (safe!)
# Q . . .
# . . Q .
# . . . .
# . . . .
#
# Step 3: Row 2 mein koi safe spot nahi!
# Backtrack ✓ Row 1 ki queen change karo
#
# Step 4: Row 1 mein col 1 bhi safe nahi (diagonal)
# Row 1 mein col 3 try karo
# Q . . .
# . . . Q
# . . . .
# . . . .
#
# Step 5: Row 2 mein col 2 safe nahi, col 1 safe hai!
# Q . . .
# . . . Q
# . Q . .
# . . . .
#
# Step 6: Row 3 mein col 3 safe nahi, col 1 safe hai
# Q . . .
# . . . Q
# . Q . .
# . . . Q
#
# SOLUTION FOUND!

Conflict Checking

Queen place karte waqt 3 cheezein check karni hain � same column, upper-left diagonal, upper-right diagonal:

def is_safe(board, row, col):
 n = len(board)
 
 # Check same column (upar ke rows mein)
 for i in range(row):
 if board[i] == col:
 return False
 
 # Check upper-left diagonal
 i, j = row - 1, col - 1
 while i >= 0 and j >= 0:
 if board[i] == j:
 return False
 i -= 1
 j -= 1
 
 # Check upper-right diagonal
 i, j = row - 1, col + 1
 while i >= 0 and j < n:
 if board[i] == j:
 return False
 i -= 1
 j += 1
 
 return True

Optimization: Har check O(n) hai. Arrays use karke O(1) mein check kar sakte ho � cols[], diag1[], diag2[]. Ye space-time tradeoff hai � optimization lesson mein seekhenge.

N-Queens Solution

def solve_n_queens(n):
 result = []
 board = [-1] * n # board[i] = j means queen at (i, j)
 
 def is_safe(row, col):
 for i in range(row):
 if board[i] == col or \
 abs(board[i] - col) == abs(i - row):
 return False
 return True
 
 def backtrack(row):
 if row == n:
 result.append(board[:])
 return
 
 for col in range(n):
 if is_safe(row, col):
 board[row] = col # Place queen
 backtrack(row + 1) # Next row
 board[row] = -1 # Remove queen (backtrack)
 
 backtrack(0)
 return result

# Find all solutions for N=4
solutions = solve_n_queens(4)
print(f"Total solutions: {len(solutions)}")
for sol in solutions:
 for row in range(4):
 line = ['.' ] * 4
 line[sol[row]] = 'Q'
 print(' '.join(line))
 print()

Sudoku Solver

Sudoku bhi backtracking se solve hota hai. Har empty cell pe 1-9 numbers try karte hain � valid hai toh place karo, nahi toh next number try karo:

def solve_sudoku(board):
 def is_valid(row, col, num):
 # Check row
 if num in board[row]:
 return False
 # Check column
 if num in [board[i][col] for i in range(9)]:
 return False
 # Check 3x3 box
 box_r, box_c = 3 * (row // 3), 3 * (col // 3)
 for i in range(box_r, box_r + 3):
 for j in range(box_c, box_c + 3):
 if board[i][j] == num:
 return False
 return True
 
 def backtrack():
 for i in range(9):
 for j in range(9):
 if board[i][j] == '.':
 for num in '123456789':
 if is_valid(i, j, num):
 board[i][j] = num
 if backtrack():
 return True
 board[i][j] = '.' # Backtrack
 return False # No valid number found
 return True # Board solved
 
 backtrack()

Try it: code khud likho

Exercise

Question: N-Queens problem mein N=4 ke kitne solutions hain✓ Sirf number daalo.

Question: N=8 (8-Queens) ke kitne solutions hain approximately✓ Nearest hundred mein daalo (jaise 92).

Common mistakes

Sirf column check karna: Column ke saath saath diagonals bhi check karo. Bahut log sirf column check karte hain aur galat solution aata hai.
Neeche ke rows check karna: Sirf upar ke rows check karo (current row se pehle). Neeche ki rows abhi placed nahi hui hain.
Backtrack nahi karna: Queen place karne ke baad jab recursion return kare toh queen hata do (board[row] = -1). Nahi toh next iteration mein galat state rahegi.
Board representation galat hona: board[i] = j simple representation hai � row i pe queen column j pe hai. Full 2D matrix ki zaroorat nahi.
Sudoku mein box check bhool jaana: 3�3 box ka check zaroor karo. Sirf row aur column se kaam nahi chalega.

Lesson complete?

N-Queens aur Sudoku samajh aa gaya✓ Ab maze problems dekhte hain � Rat in Maze, Word Search, Flood Fill � ye sab backtracking ke interesting applications hain.