VẤN ĐỀ
Viết một chương trình để giải quyết một câu đố Sudoku bằng cách lấp đầy các ô trống.
Giải pháp Sudoku phải đáp ứng tất cả các quy tắc sau:
- Mỗi chữ số từ 1-9 phải xuất hiện duy nhất một lần trong mỗi hàng.
- Mỗi chữ số từ 1-9 phải xuất hiện duy nhất một lần trong mỗi cột.
- Mỗi chữ số từ 1-9 phải xuất hiện duy nhất một lần trong mỗi trong 9 ô lưới 3x3 của bàn.
- Ký tự '.' chỉ thị các ô trống.
Giải pháp 1: Cách tiếp cận ban đầu (Quay lui - Brute Force)
Cách Tiếp Cận
-
Thuật toán quay lui:
- Duyệt bảng từng ô và từng hàng.
- Đối với mỗi ô trống ('.'), kiểm tra xem có số nào từ ('1' đến '9') có thể đặt vào bảng hay không bằng cách tuân theo các quy tắc sau:
- Kiểm Tra Hàng: Đảm bảo số không đã có trong hàng hiện tại.
- Kiểm Tra Cột: Đảm bảo số không đã có trong cột hiện tại.
- Kiểm Tra Ô: Đảm bảo số không đã có trong ô 3x3 hiện tại.
- Nếu hợp lệ, đặt số và tiếp tục ô tiếp theo (gọi đệ quy).
- Nếu vị trí số không dẫn đến một giải pháp hợp lệ, trả về True.
- Nếu không có số nào hợp lệ, quay lui bằng cách đặt lại ô thành '.'.
-
Trường hợp cơ bản: Nếu hàng đạt đến 9, có nghĩa là tất cả các hàng đã được xử lý, và giải pháp đã hoàn tất.
-
Bước đệ quy: Nếu cột đạt đến 9, chuyển sang hàng tiếp theo (hàng + 1, cột = 0).
Độ Phức Tạp
- Độ phức tạp về thời gian: O(9^81)
- Độ phức tạp về không gian: O(81)
Mã nguồn Giải pháp 1
python
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def is_valid(row:int, col: int, num):
# KIỂM TRA HÀNG
for i in range(9):
if board[row][i] == num:
return False
if board[i][col] == num:
return False
if board[3*(row//3) + i//3][3*(col//3) + i%3] == num:
return False
return True
def backtrack(row, col):
if row == 9:
return True
if col == 9:
return backtrack(row + 1, 0)
if board[row][col] == '.':
for i in '123456789':
if is_valid(row, col, i):
board[row][col] = i
if backtrack(row, col + 1):
return True
else:
board[row][col] = '.'
return False
else:
return backtrack(row, col + 1)
backtrack(0, 0)Giải pháp 2: Cách tiếp cận tối ưu (Sử dụng Tập hợp - Sets)
Khởi tạo:
- Theo như Giải pháp 1
- Thay vì kiểm tra tính hợp lệ mỗi lần, sử dụng ba danh sách của tập hợp để theo dõi các số đã sử dụng.
Độ Phức Tạp
- Độ phức tạp về thời gian: O(9^m) - m là số ô trống.
- Độ phức tạp về không gian: O(81)
Mã nguồn Giải pháp 2
python
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
# Khởi tạo các tập hợp với các giá trị có sẵn trong bảng
for r in range(9):
for c in range(9):
if board[r][c] != ".":
rows[r].add(board[r][c])
cols[c].add(board[r][c])
boxes[3 * (r // 3) + c // 3].add(board[r][c])
def is_valid(r, c, num):
return (
num not in rows[r]
and num not in cols[c]
and num not in boxes[(r // 3) * 3 + c // 3]
)
def backtracking(row, col):
if row == 9:
return True
if col == 9:
return backtracking(row + 1, 0)
if board[row][col] == ".":
for i in "123456789":
if is_valid(row, col, i):
board[row][col] = i
rows[row].add(i)
cols[col].add(i)
boxes[3 * (row // 3) + col // 3].add(i)
if backtracking(row, col + 1):
return True
board[row][col] = "."
rows[row].remove(i)
cols[col].remove(i)
boxes[3 * (row // 3) + col // 3].remove(i)
return False
else:
return backtracking(row, col + 1)
backtracking(0, 0)source: viblo
