Giao diện
Backtracking Puzzles
🎯 Mục tiêu
Luyện tập kỹ thuật quay lui (backtracking) qua bài toán N-Queens, giải Sudoku, sinh hoán vị/tổ hợp và tìm từ trong lưới.
Mô tả bài tập
Backtracking là kỹ thuật thử từng khả năng và quay lui khi gặp ngõ cụt. Đây là nền tảng cho nhiều bài toán tổ hợp và tối ưu khó.
Yêu cầu
Bài 1: Bài toán N-Queens
Đặt n quân hậu trên bàn cờ n×n sao cho không có hai quân nào tấn công nhau. Trả về tất cả cách đặt.
python
def solve_n_queens(n: int) -> list[list[int]]:
# TODO: Cài đặt backtracking
pass
assert len(solve_n_queens(4)) == 2
assert len(solve_n_queens(8)) == 92Bài 2: Giải Sudoku
Giải bảng Sudoku 9×9 (ô trống = 0) bằng backtracking.
python
def solve_sudoku(board: list[list[int]]) -> bool:
# TODO: Cài đặt backtracking
pass
board = [[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]]
assert solve_sudoku(board) == TrueBài 3: Sinh hoán vị và tổ hợp
3a. Sinh tất cả hoán vị của một danh sách.
python
def permutations(nums: list[int]) -> list[list[int]]:
# TODO: Cài đặt backtracking
pass
assert len(permutations([1, 2, 3])) == 63b. Sinh tất cả tổ hợp chập k của một danh sách.
python
def combinations(nums: list[int], k: int) -> list[list[int]]:
# TODO: Cài đặt backtracking
pass
assert len(combinations([1, 2, 3, 4], 2)) == 6Bài 4: Tìm từ trong lưới (Word Search)
Kiểm tra xem từ word có tồn tại trong lưới ký tự hay không (di chuyển 4 hướng, mỗi ô dùng tối đa 1 lần).
python
def word_search(board: list[list[str]], word: str) -> bool:
# TODO: Cài đặt backtracking
pass
grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
assert word_search(grid, "ABCCED") == True
assert word_search(grid, "ABCB") == FalsePhân tích độ phức tạp
| Bài | Time | Space |
|---|---|---|
| 1 - N-Queens | O(n!) | O(n) |
| 2 - Sudoku | O(9^m), m = ô trống | O(m) stack |
| 3a - Hoán vị | O(n × n!) | O(n) |
| 3b - Tổ hợp | O(C(n,k) × k) | O(k) |
| 4 - Word Search | O(m × n × 4^L), L = len(word) | O(L) |
Gợi ý
Gợi ý Bài 1
Đặt hậu theo từng hàng. Dùng 3 set theo dõi: cột đã dùng, đường chéo chính (row-col), đường chéo phụ (row+col). Nếu vị trí hợp lệ → đặt hậu và đệ quy hàng tiếp theo.
Gợi ý Bài 2
Tìm ô trống, thử số 1-9. Kiểm tra hàng, cột, khối 3×3 xem số đã tồn tại chưa. Nếu hợp lệ → đệ quy. Nếu không có số nào hợp lệ → quay lui (reset ô về 0).
Gợi ý Bài 4
Từ mỗi ô, DFS theo 4 hướng. Đánh dấu ô đã thăm bằng cách thay ký tự (ví dụ '#'), phục hồi khi backtrack. So khớp từng ký tự của word.
Lời giải tham khảo
Xem lời giải
python
def solve_n_queens(n):
solutions, cols, d1, d2 = [], set(), set(), set()
def bt(row, cur):
if row == n: solutions.append(cur[:]); return
for c in range(n):
if c in cols or (row-c) in d1 or (row+c) in d2: continue
cols.add(c); d1.add(row-c); d2.add(row+c); cur.append(c)
bt(row+1, cur)
cur.pop(); cols.discard(c); d1.discard(row-c); d2.discard(row+c)
bt(0, []); return solutions
def permutations(nums):
result = []
def bt(path, rest):
if not rest: result.append(path[:]); return
for i in range(len(rest)):
path.append(rest[i]); bt(path, rest[:i]+rest[i+1:]); path.pop()
bt([], nums); return result
def word_search(board, word):
R, C = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word): return True
if r<0 or r>=R or c<0 or c>=C or board[r][c]!=word[i]: return False
tmp, board[r][c] = board[r][c], '#'
for dr,dc in [(0,1),(0,-1),(1,0),(-1,0)]:
if dfs(r+dr,c+dc,i+1): return True
board[r][c] = tmp; return False
return any(dfs(r,c,0) for r in range(R) for c in range(C))