N-Queens Problem - The Backtracking Classic

"N-Queens là bài test liệu bạn có thực sự hiểu backtracking hay không." - HPN

Problem Statement

Đặt N quân hậu trên bàn cờ N×N sao cho không có 2 quân hậu nào tấn công nhau.

Quân hậu tấn công theo:

Hàng ngang (row)
Hàng dọc (column)
Hai đường chéo (diagonals)

N = 4, One Solution:

  . Q . .
  . . . Q
  Q . . .
  . . Q .

Queens at: (0,1), (1,3), (2,0), (3,2)

📘 Số lượng Solutions

N	Solutions	Distinct (removing symmetry)
1	1	1
4	2	1
8	92	12
12	14,200	1,787
14	365,596	45,752

Real-World Applications

Domain	Use Case	Tương đồng
AI Planning	Task scheduling	Constraint satisfaction
Compiler	Register allocation	Resource conflict avoidance
VLSI Design	Component placement	Non-overlapping constraints
Networking	Frequency assignment	Interference avoidance
Game AI	Move generation	Valid position checking

The Backtracking Approach

Constraint Checking

python

def is_safe(board: list, row: int, col: int, n: int) -> bool:
    """
    Check if placing queen at (row, col) is safe.
    
    We only need to check:
    1. Column (upper part only, since we place row by row)
    2. Upper-left diagonal
    3. Upper-right diagonal
    """
    # Check column (rows above)
    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

Basic Implementation

python

from typing import List, Optional


def solve_n_queens(n: int) -> List[List[int]]:
    """
    Find all solutions to N-Queens problem.
    
    Returns: List of solutions, each solution is [col positions per row]
             Example: [1, 3, 0, 2] means queens at (0,1), (1,3), (2,0), (3,2)
    
    Time: O(N!) - Each row has at most N-1 choices, then N-2, ...
    Space: O(N) for the board + O(N) recursion stack
    """
    solutions = []
    board = [-1] * n  # board[row] = column of queen in that row
    
    def is_safe(row: int, col: int) -> bool:
        for prev_row in range(row):
            prev_col = board[prev_row]
            
            # Same column
            if prev_col == col:
                return False
            
            # Same diagonal (|row_diff| == |col_diff|)
            if abs(prev_row - row) == abs(prev_col - col):
                return False
        
        return True
    
    def backtrack(row: int):
        if row == n:
            solutions.append(board[:])  # Found a solution!
            return
        
        for col in range(n):
            if is_safe(row, col):
                board[row] = col        # Place queen
                backtrack(row + 1)      # Recurse
                board[row] = -1         # Remove queen (backtrack)
    
    backtrack(0)
    return solutions

Optimized Implementation (O(1) Conflict Check)

python

from typing import List, Set


def solve_n_queens_optimized(n: int) -> List[List[int]]:
    """
    Optimized N-Queens with O(1) conflict checking using sets.
    
    Key insight:
    - Column conflicts: track used columns
    - Diagonal ↘: (row - col) is constant
    - Diagonal ↙: (row + col) is constant
    
    Time: O(N!) worst case, but much faster in practice
    Space: O(N) for sets
    """
    solutions = []
    board = []
    
    # Sets for O(1) conflict checking
    cols: Set[int] = set()
    diag1: Set[int] = set()  # row - col
    diag2: Set[int] = set()  # row + col
    
    def backtrack(row: int):
        if row == n:
            solutions.append(board[:])
            return
        
        for col in range(n):
            d1 = row - col
            d2 = row + col
            
            if col in cols or d1 in diag1 or d2 in diag2:
                continue  # Not safe
            
            # Place queen
            board.append(col)
            cols.add(col)
            diag1.add(d1)
            diag2.add(d2)
            
            backtrack(row + 1)
            
            # Remove queen (backtrack)
            board.pop()
            cols.remove(col)
            diag1.remove(d1)
            diag2.remove(d2)
    
    backtrack(0)
    return solutions

Production Code

python

# HPN Engineering Standard
# Implementation: N-Queens with All Features

from typing import List, Set, Generator, Optional
from dataclasses import dataclass


@dataclass
class NQueensSolver:
    """
    Production-ready N-Queens solver.
    
    Features:
    - Find all solutions
    - Find first solution only
    - Generator for memory efficiency
    - Pretty print boards
    - Count solutions without storing
    """
    
    n: int
    
    def solve_all(self) -> List[List[int]]:
        """Find all solutions."""
        return list(self._solve_generator())
    
    def solve_first(self) -> Optional[List[int]]:
        """Find first solution only (faster)."""
        try:
            return next(self._solve_generator())
        except StopIteration:
            return None
    
    def count_solutions(self) -> int:
        """Count solutions without storing them."""
        return sum(1 for _ in self._solve_generator())
    
    def _solve_generator(self) -> Generator[List[int], None, None]:
        """Generator for memory-efficient iteration."""
        n = self.n
        board = []
        cols: Set[int] = set()
        diag1: Set[int] = set()
        diag2: Set[int] = set()
        
        def backtrack(row: int):
            if row == n:
                yield board[:]
                return
            
            for col in range(n):
                d1, d2 = row - col, row + col
                
                if col in cols or d1 in diag1 or d2 in diag2:
                    continue
                
                board.append(col)
                cols.add(col)
                diag1.add(d1)
                diag2.add(d2)
                
                yield from backtrack(row + 1)
                
                board.pop()
                cols.remove(col)
                diag1.remove(d1)
                diag2.remove(d2)
        
        yield from backtrack(0)
    
    @staticmethod
    def format_board(solution: List[int]) -> str:
        """Pretty print a solution."""
        n = len(solution)
        lines = []
        
        for row in range(n):
            col = solution[row]
            line = '. ' * col + 'Q ' + '. ' * (n - col - 1)
            lines.append(line.strip())
        
        return '\n'.join(lines)
    
    @staticmethod
    def validate_solution(solution: List[int]) -> bool:
        """Verify a solution is valid."""
        n = len(solution)
        
        # Check column conflicts
        if len(set(solution)) != n:
            return False
        
        # Check diagonal conflicts
        for i in range(n):
            for j in range(i + 1, n):
                if abs(i - j) == abs(solution[i] - solution[j]):
                    return False
        
        return True


# ============================================
# VARIANTS
# ============================================

def n_queens_with_obstacles(n: int, obstacles: Set[tuple]) -> List[List[int]]:
    """
    N-Queens với một số ô bị blocked.
    
    obstacles: Set of (row, col) tuples that cannot have queens
    """
    solutions = []
    board = []
    cols: Set[int] = set()
    diag1: Set[int] = set()
    diag2: Set[int] = set()
    
    def backtrack(row: int):
        if row == n:
            solutions.append(board[:])
            return
        
        for col in range(n):
            if (row, col) in obstacles:
                continue
            
            d1, d2 = row - col, row + col
            
            if col in cols or d1 in diag1 or d2 in diag2:
                continue
            
            board.append(col)
            cols.add(col)
            diag1.add(d1)
            diag2.add(d2)
            
            backtrack(row + 1)
            
            board.pop()
            cols.remove(col)
            diag1.remove(d1)
            diag2.remove(d2)
    
    backtrack(0)
    return solutions


def n_rooks(n: int) -> int:
    """
    Count ways to place N non-attacking rooks.
    (Simpler than queens - only row/column conflicts)
    
    Answer: N! (permutations)
    """
    from math import factorial
    return factorial(n)


# ============================================
# SUDOKU SOLVER (BONUS)
# ============================================

def solve_sudoku(board: List[List[int]]) -> bool:
    """
    Solve Sudoku using backtracking.
    
    board: 9x9 grid, 0 = empty cell
    
    Modifies board in-place, returns True if solvable.
    """
    def is_valid(row: int, col: int, num: int) -> bool:
        # Check row
        if num in board[row]:
            return False
        
        # Check column
        if num in [board[r][col] for r in range(9)]:
            return False
        
        # Check 3x3 box
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for r in range(box_row, box_row + 3):
            for c in range(box_col, box_col + 3):
                if board[r][c] == num:
                    return False
        
        return True
    
    def find_empty() -> Optional[tuple]:
        for r in range(9):
            for c in range(9):
                if board[r][c] == 0:
                    return (r, c)
        return None
    
    def backtrack() -> bool:
        pos = find_empty()
        if pos is None:
            return True  # Solved!
        
        row, col = pos
        
        for num in range(1, 10):
            if is_valid(row, col, num):
                board[row][col] = num
                
                if backtrack():
                    return True
                
                board[row][col] = 0  # Backtrack
        
        return False
    
    return backtrack()


# ============================================
# USAGE EXAMPLE
# ============================================

if __name__ == "__main__":
    # Example 1: N-Queens
    print("=== N-Queens Solver ===\n")
    
    for n in [4, 8]:
        solver = NQueensSolver(n)
        count = solver.count_solutions()
        print(f"N={n}: {count} solutions")
        
        if n == 4:
            solutions = solver.solve_all()
            print("\nAll solutions for N=4:")
            for i, sol in enumerate(solutions):
                print(f"\nSolution {i+1}:")
                print(solver.format_board(sol))
    
    # Example 2: First solution for larger N
    print("\n=== First Solution for N=12 ===")
    solver = NQueensSolver(12)
    first = solver.solve_first()
    if first:
        print(f"Solution: {first}")
    
    # Example 3: Sudoku
    print("\n=== Sudoku Solver ===")
    
    puzzle = [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9],
    ]
    
    if solve_sudoku(puzzle):
        print("Solved!")
        for row in puzzle:
            print(' '.join(map(str, row)))
    else:
        print("No solution exists.")
)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265

Complexity Analysis

Variant	Time	Space
Basic	O(N! × N)	O(N)
Optimized (sets)	O(N!)	O(N)
Count only	O(N!)	O(N)
Sudoku	O(9^M)	O(M)

M = empty cells in Sudoku

Backtracking Template

python

def backtrack(state):
    if is_solution(state):
        process_solution(state)
        return
    
    for choice in get_choices(state):
        if is_valid(choice, state):
            make_choice(choice, state)      # ✅ Choose
            backtrack(state)                # 🔁 Explore
            undo_choice(choice, state)      # ↩️ Unchoose

Pruning Strategies

Strategy	Description	Impact
Early termination	Stop khi tìm thấy 1 solution	Skip remaining
Constraint propagation	Giảm choices dựa trên constraints	Fewer branches
Variable ordering	Chọn variable có ít choices nhất trước	Fail fast
Value ordering	Thử giá trị có khả năng thành công cao trước	Success fast

💡 HPN's Rule

"Backtracking = DFS + Pruning. Không có pruning tốt → Exponential time. Có pruning tốt → Vẫn exponential nhưng nhanh hơn nhiều."

N-Queens Problem - The Backtracking Classic ​

Problem Statement ​

Real-World Applications ​

The Backtracking Approach ​

Constraint Checking ​

Basic Implementation ​

Optimized Implementation (O(1) Conflict Check) ​

Production Code ​

Complexity Analysis ​

Backtracking Template ​

Pruning Strategies ​

N-Queens Problem - The Backtracking Classic

Problem Statement

Real-World Applications

The Backtracking Approach

Constraint Checking

Basic Implementation

Optimized Implementation (O(1) Conflict Check)

Production Code

Complexity Analysis

Backtracking Template

Pruning Strategies