-
Bạn đã biết cách kiểm tra bảng Sudoku, giờ là lúc dạy máy tính tự điền số vào ô trống.
-
Nắm vững Backtracking (Quay lui) – chìa khóa để giải quyết mọi bài toán liệt kê, tìm đường và tối ưu.
-
Một bộ code mẫu chuẩn mực, giải quyết được mọi bảng Sudoku (nếu có nghiệm) chỉ trong tích tắc.
Tóm tắt nội dung
-
Tư duy “Thử – Sai – Sửa”.
-
Triển khai thuật toán Backtracking đệ quy.
-
Phân tích Time & Space Complexity (Tại sao nó chậm nhưng vẫn cần thiết?).
-
Code Python hoàn chỉnh chạy được ngay.
Bạn xem thêm:
- 7 Sai Lầm Chí Mạng Khi Tự Học Python – Đừng Làm Những Điều Này
- Hướng Dẫn Cài Đặt Python và PyCharm Chi Tiết: Tránh 5 Lỗi Sai Người Mới Hay Gặp
- 9 Bước Học Lập Trình Giao Diện Python Với tkinter: Xây Dựng Máy Tính Đơn Giản
1. Đề bài
Cho một bảng Sudoku 9×9 chứa các số từ 1-9 và các ô trống (ký hiệu là số 0). Hãy điền các số vào ô trống sao cho bảng Sudoku trở nên hợp lệ (thỏa mãn quy tắc hàng, cột, khối 3×3).
Giả định rằng bảng đầu vào luôn có duy nhất một lời giải.
Input:
-
Mảng 2 chiều 9×9. Ô trống là
0.
Output:
-
In ra bảng Sudoku đã được điền đầy đủ.
Constraints:
-
Kích thước cố định 9×9.
-
Dữ liệu đảm bảo có nghiệm.
Ví dụ:
Input:
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
Output:
(Bảng đã điền kín số hợp lệ)
2. Phân tích tư duy
Backtracking (Quay lui) bản chất là thuật toán Vét cạn thông minh (Brute-force with pruning). Thay vì thử điền lung tung, chúng ta điền có nguyên tắc:
Logic Step-by-Step:
-
Tìm ô trống: Quét bảng tìm ô đầu tiên có giá trị
0. -
Thử giá trị: Tại ô đó, thử lần lượt các số từ
1đến9. -
Kiểm tra hợp lệ: Với mỗi số vừa điền thử, kiểm tra xem nó có bị trùng trong Hàng, Cột, hoặc Khối 3×3 hay không?
-
Nếu HỢP LỆ: Tạm thời chấp nhận số đó => Gọi đệ quy để giải tiếp ô trống tiếp theo.
-
Nếu KHÔNG hợp lệ: Bỏ qua số đó, thử số tiếp theo.
-
-
Backtrack (Quay lui):
-
Nếu thử hết từ 1-9 mà không số nào điền được (ngõ cụt) => Quay lại bước trước đó (Return False).
-
Quan trọng: Trước khi quay lại, phải Reset ô hiện tại về
0để bước trước đó thử số khác.
-
Ví dụ tư duy:
Giống như bạn đi vào mê cung. Gặp ngã ba, bạn rẽ Trái. Đi một hồi thấy đường cụt, bạn quay lại ngã ba cũ, xóa dấu chân ở đường Trái, và thử rẽ Phải.
3. Giải pháp: Code Python chuẩn Backtracking
Đây là giải pháp kinh điển, clean code và dễ hiểu nhất.
import sys
def print_board(board):
"""Hàm in bảng đẹp mắt để dễ nhìn kết quả"""
for i in range(9):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - -")
for j in range(9):
if j % 3 == 0 and j != 0:
print("| ", end="")
if j == 8:
print(board[i][j])
else:
print(str(board[i][j]) + " ", end="")
def is_valid(board, row, col, num):
"""
Kiểm tra xem đặt số `num` vào vị trí (row, col) có hợp lệ không.
"""
# 1. Kiểm tra hàng
for x in range(9):
if board[x] == num:
return False
# 2. Kiểm tra cột
for x in range(9):
if board[x]
== num:
return False
# 3. Kiểm tra khối 3x3
start_row = (row // 3) * 3
start_col = (col // 3) * 3
for i in range(3):
for j in range(3):
if board[start_row + i][start_col + j] == num:
return False
return True
def solve_sudoku(board):
"""
Hàm đệ quy Backtracking để giải Sudoku
Return True nếu giải được, False nếu không.
"""
for i in range(9):
for j in range(9):
# Tìm ô trống đầu tiên (số 0)
if board[i][j] == 0:
# Thử điền các số từ 1 đến 9
for num in range(1, 10):
if is_valid(board, i, j, num):
# Nếu hợp lệ, điền thử vào
board[i][j] = num
# ĐỆ QUY: Gọi hàm giải tiếp cho trạng thái mới
if solve_sudoku(board):
return True
# BACKTRACK: Nếu nhánh đệ quy trên thất bại (trả về False)
# Thì ta phải hoàn tác (reset về 0) để thử số `num` khác
board[i][j] = 0
# Nếu thử hết 1-9 mà vẫn không được -> Bài toán tại nhánh này vô nghiệm
return False
# Nếu chạy hết 2 vòng lặp mà không còn số 0 nào -> Đã điền xong
return True
# --- Phần đọc Input ---
def main():
# Ví dụ Hardcoded để test nhanh.
# Bạn có thể thay bằng sys.stdin.read() như bài trước nếu cần.
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]
]
print("--- Đề Bài ---")
print_board(board)
if solve_sudoku(board):
print("\n--- Lời Giải ---")
print_board(board)
else:
print("\nKhông tìm thấy lời giải!")
if __name__ == "__main__":
main()
4. Phân tích độ phức tạp (Big-O Analysis)
Đây là phần giúp bạn ghi điểm trong các buổi phỏng vấn.
Time Complexity: O(9^m)
-
Trong đó m là số lượng ô trống.
-
Với mỗi ô trống, trong trường hợp tệ nhất, ta phải thử tới 9 khả năng.
-
Đây là độ phức tạp số mũ (Exponential Time). Tuy nhiên, nhờ thao tác “cắt tỉa” (pruning) – tức là hàm
is_validtrả về False ngay lập tức, nên thực tế code chạy nhanh hơn nhiều so với lý thuyết.
Space Complexity: O(m)
-
Không gian bộ nhớ dùng cho Call Stack (ngăn xếp đệ quy).
-
Độ sâu tối đa của đệ quy chính bằng số lượng ô trống cần điền .
5. Lỗi thường gặp
| Lỗi sai | Hậu quả | Cách sửa |
| Quên bước Reset (Backtrack) | Bảng bị điền sai nhưng không quay lại được, dẫn đến kết quả sai hoặc tắc đường. | Bắt buộc có dòng board[i][j] = 0 sau khi đệ quy thất bại. |
| Return sai chỗ | Code chỉ điền được 1 số rồi dừng, hoặc chạy mãi không dừng. | Kiểm tra kỹ điều kiện dừng (return True khi hết ô trống, return False khi thử hết số). |
| Sửa mảng gốc | Nếu viết hàm dạng class, cẩn thận việc self.board bị sửa đổi ngoài ý muốn. |
Backtracking sửa trực tiếp trên mảng (in-place) là tốt, nhưng phải kiểm soát flow. |
6. FAQ: Câu hỏi thường gặp
1. Làm sao để code chạy nhanh hơn?
Thay vì duyệt từ ô (0,0) đến (8,8), hãy dùng chiến thuật MRV (Minimum Remaining Values): Luôn chọn điền ô trống có ít khả năng điền hợp lệ nhất trước. Điều này giúp phát hiện nhánh sai sớm hơn (Fail-fast).
2. Có cách nào không dùng đệ quy không?
Có, bạn có thể dùng Stack (Ngăn xếp) để giả lập quá trình đệ quy (Iterative Backtracking), nhưng code sẽ dài và phức tạp hơn. Đệ quy là cách tự nhiên nhất cho bài toán này.
3. Tại sao giải thuật Sudoku Solver dùng Backtracking mà không dùng Greedy (Tham lam)?
Thuật toán Tham lam (chọn nước đi tốt nhất hiện tại) không đảm bảo tìm ra lời giải cho Sudoku, vì một lựa chọn đúng ở hiện tại có thể dẫn đến bế tắc ở tương lai 10 bước sau. Chỉ có Backtracking mới đảm bảo thử hết các trường hợp.
7. Học tiếp gì sau bài này?
Bạn đã chinh phục được Backtracking cơ bản. Hãy thử thách bản thân với các cấp độ cao hơn:
-
Sudoku Solver (Optimized – Bitmasking): Sử dụng bit manipulation để kiểm tra trùng lặp trong O(1) cực nhanh.
-
N-Queens (Bài toán xếp hậu): Một bài toán Backtracking kinh điển khác trên bàn cờ vua.
-
Word Search: Áp dụng Backtracking để tìm chữ trong ma trận ký tự.
Các khóa học liên quan:
Một số sản phẩm từ Python:
Một số sách lập trình Python bạn hãy tham khảo