Bài 8.4 - Giải Sudoku đơn giản bằng Python
Bài 8.4 - Giải Sudoku đơn giản bằng Python
Chào mừng trở lại với series học Python! Hôm nay, chúng ta sẽ đối mặt với một thử thách kinh điển và thú vị: xây dựng một chương trình Python có khả năng giải tự động các câu đố Sudoku đơn giản. Đây không chỉ là một bài tập lập trình hay mà còn là cơ hội tuyệt vời để bạn làm quen với một trong những kỹ thuật giải thuật quan trọng: Backtracking (Quay Lui).
Sudoku là gì?
Trước khi bắt tay vào code, hãy nhắc lại luật Sudoku một chút. Mục tiêu của trò chơi là điền các số từ 1 đến 9 vào các ô trống trên một lưới 9x9 sao cho các điều kiện sau được thỏa mãn:
- Mỗi hàng (row) phải chứa các số từ 1 đến 9 mà không lặp lại.
- Mỗi cột (column) phải chứa các số từ 1 đến 9 mà không lặp lại.
- Mỗi khối 3x3 nhỏ trong lưới lớn phải chứa các số từ 1 đến 9 mà không lặp lại.
Các ô đã cho sẵn là những "gợi ý" mà chúng ta không được thay đổi.
Chiến lược giải: Thuật toán Backtracking
Làm thế nào để máy tính có thể giải được Sudoku? Chúng ta sẽ sử dụng phương pháp thử và sai một cách có hệ thống, còn gọi là thuật toán Backtracking (Quay Lui).
Ý tưởng cốt lõi của Backtracking trong trường hợp Sudoku là:
- Tìm một ô trống trên bảng.
- Thử đặt một con số từ 1 đến 9 vào ô đó.
- Kiểm tra xem việc đặt số này có hợp lệ theo luật Sudoku hay không (kiểm tra hàng, cột, khối 3x3).
- Nếu hợp lệ: Tiếp tục giải phần còn lại của bảng bằng cách đệ quy gọi lại hàm giải chính cho bảng đã được cập nhật.
- Nếu lời gọi đệ quy thành công (tức là từ vị trí này đã tìm được lời giải hoàn chỉnh): Chúc mừng! Chúng ta đã giải xong, trả về kết quả thành công.
- Nếu lời gọi đệ quy thất bại (tức là việc đặt con số hiện tại vào ô trống không dẫn đến lời giải): Quay lui! Xóa số vừa đặt ra khỏi ô trống đó và thử con số khác cho ô trống ban đầu.
- Nếu đã thử tất cả các số từ 1 đến 9 cho ô trống ban đầu mà không có số nào dẫn đến lời giải: Điều này có nghĩa là có gì đó ở các bước trước đó đã sai. Chúng ta phải trả về kết quả thất bại để cho phép bước gọi trước đó quay lui và thử con số khác.
Quá trình này tiếp diễn cho đến khi hoặc toàn bộ bảng được điền đầy hợp lệ (thành công) hoặc không còn khả năng thử số nào nữa (thất bại).
Biểu diễn bảng Sudoku trong Python
Chúng ta sẽ biểu diễn bảng Sudoku dưới dạng một danh sách các danh sách (list of lists) trong Python. Mỗi danh sách con sẽ là một hàng. Các ô trống sẽ được ký hiệu bằng số 0.
Ví dụ về một bảng Sudoku đơn giản:
grid = [
[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]
]
Đây là bảng chúng ta sẽ cố gắng giải. Các số 0 là các ô cần điền.
Xây dựng các hàm hỗ trợ
Trước khi viết hàm giải chính, chúng ta cần các hàm nhỏ hơn để thực hiện các tác vụ cụ thể:
find_empty(grid): Hàm này tìm kiếm ô trống tiếp theo (có giá trị là 0) trên bảng.is_valid(grid, num, pos): Hàm này kiểm tra xem việc đặt sốnumvào vị trípos(là một tuple(row, col)) có hợp lệ theo luật Sudoku hay không.
Hãy cùng viết mã cho từng hàm một.
1. Tìm ô trống tiếp theo (find_empty)
Hàm này sẽ duyệt qua từng ô trong lưới. Nếu gặp số 0, nó trả về vị trí của ô đó dưới dạng một tuple (row, col). Nếu duyệt hết lưới mà không tìm thấy ô 0 nào, tức là bảng đã đầy, nó sẽ trả về None.
def find_empty(grid):
"""
Tìm ô trống tiếp theo trong bảng (ký hiệu bằng 0).
Trả về tuple (row, col) nếu tìm thấy, ngược lại trả về None.
"""
for r in range(9): # Duyệt qua các hàng (0 đến 8)
for c in range(9): # Duyệt qua các cột (0 đến 8)
if grid[r][c] == 0:
return (r, c) # Trả về vị trí (hàng, cột)
return None # Không còn ô trống nào
# Ví dụ sử dụng:
# pos = find_empty(grid)
# if pos:
# print(f"Tìm thấy ô trống tại vị trí: {pos}")
# else:
# print("Bảng đã đầy!")
Giải thích code find_empty:
- Chúng ta dùng hai vòng lặp
forlồng nhau để duyệt qua từng ô của bảng 9x9.rđại diện cho chỉ số hàng (0 đến 8) vàcđại diện cho chỉ số cột (0 đến 8). if grid[r][c] == 0:kiểm tra xem giá trị tại ô hiện tại có phải là 0 hay không.- Nếu là 0, chúng ta đã tìm thấy ô trống. Hàm ngay lập tức trả về một tuple
(r, c)chứa chỉ số hàng và cột của ô đó. - Nếu vòng lặp kết thúc mà không có câu lệnh
return (r, c)nào được thực thi (tức là không tìm thấy ô 0 nào), hàm sẽ thực thireturn Noneở cuối, báo hiệu rằng bảng đã đầy.
2. Kiểm tra tính hợp lệ (is_valid)
Hàm này là quan trọng nhất để đảm bảo chúng ta tuân thủ luật Sudoku. Nó nhận vào bảng hiện tại (grid), số muốn đặt (num), và vị trí muốn đặt (pos) dưới dạng tuple (row, col). Nó sẽ kiểm tra 3 điều kiện:
- Kiểm tra hàng: Số
numđã tồn tại trong hàngrowchưa? - Kiểm tra cột: Số
numđã tồn tại trong cộtcolchưa? - Kiểm tra khối 3x3: Số
numđã tồn tại trong khối 3x3 chứa vị tríposchưa?
Nếu tất cả 3 điều kiện này đều không vi phạm (tức là số num chưa có ở bất kỳ đâu trong hàng, cột, và khối 3x3 đó), hàm trả về True. Ngược lại, nếu vi phạm một trong ba điều kiện, hàm trả về False.
def is_valid(grid, num, pos):
"""
Kiểm tra xem việc đặt số 'num' vào vị trí 'pos' (tuple (row, col))
có hợp lệ theo luật Sudoku hay không.
"""
row, col = pos # Giải nén tuple vị trí
# 1. Kiểm tra hàng
# Duyệt qua tất cả các cột trong hàng 'row'.
# Bỏ qua vị trí 'col' hiện tại nếu nó không phải là ô trống ban đầu
# (mặc dù trong thuật toán solve, chúng ta chỉ gọi hàm này
# khi ô tại pos là 0, nên việc bỏ qua này không thực sự cần thiết
# nhưng là cách kiểm tra tính hợp lệ tổng quát hơn).
for c in range(9):
if grid[row][c] == num and c != col: # Kiểm tra nếu số đã có trong hàng (và không phải ở chính vị trí đang xét)
return False # Không hợp lệ vì trùng số trong hàng
# 2. Kiểm tra cột
# Duyệt qua tất cả các hàng trong cột 'col'.
for r in range(9):
if grid[r][col] == num and r != row: # Kiểm tra nếu số đã có trong cột (và không phải ở chính vị trí đang xét)
return False # Không hợp lệ vì trùng số trong cột
# 3. Kiểm tra khối 3x3
# Xác định ô bắt đầu của khối 3x3 chứa vị trí (row, col).
# Chia nguyên chỉ số hàng/cột cho 3 rồi nhân lại với 3.
# Ví dụ: row 0, 1, 2 -> start_row = 0
# row 3, 4, 5 -> start_row = 3
# row 6, 7, 8 -> start_row = 6
start_row = row - row % 3
start_col = col - col % 3
# Duyệt qua các ô trong khối 3x3
for r in range(start_row, start_row + 3):
for c in range(start_col, start_col + 3):
# Kiểm tra nếu số đã có trong khối 3x3 (và không phải ở chính vị trí đang xét)
if grid[r][c] == num and (r, c) != pos:
return False # Không hợp lệ vì trùng số trong khối 3x3
# Nếu vượt qua tất cả các kiểm tra, vị trí này hợp lệ để đặt số 'num'
return True
# Ví dụ sử dụng (với bảng 'grid' đã khai báo ở trên):
# print(is_valid(grid, 1, (0, 2))) # Đặt số 1 vào (0, 2) (ô trống đầu tiên) - Sẽ là False vì 1 đã có trong cột 1 và khối 3x3 đầu tiên
# print(is_valid(grid, 4, (0, 2))) # Đặt số 4 vào (0, 2) - Có thể là True (cần kiểm tra lại luật Sudoku cho bảng cụ thể này)
Giải thích code is_valid:
row, col = pos: Tách chỉ số hàng và cột từ tupleposnhận vào.- Kiểm tra hàng: Vòng lặp duyệt qua tất cả 9 cột (
range(9)) trong hàngrow.if grid[row][c] == num and c != col:kiểm tra xem sốnumcó xuất hiện ở cộtcnào khác ngoài cột hiện tại (col) không. Nếu có, trả vềFalse. - Kiểm tra cột: Tương tự, vòng lặp duyệt qua tất cả 9 hàng (
range(9)) trong cộtcol.if grid[r][col] == num and r != row:kiểm tra xem sốnumcó xuất hiện ở hàngrnào khác ngoài hàng hiện tại (row) không. Nếu có, trả vềFalse. - Kiểm tra khối 3x3: Đây là phần hơi phức tạp hơn một chút.
- Chúng ta cần tìm tọa độ bắt đầu của khối 3x3 chứa ô
(row, col). Phép chia nguyênrow // 3sẽ cho biết khối 3x3 nào theo chiều hàng (0, 1, hoặc 2). Nhân kết quả với 3 sẽ cho chỉ số hàng bắt đầu của khối đó (start_row). Tương tự với cột để tìmstart_col. Ví dụ: nếurowlà 5,5 // 3 = 1.1 * 3 = 3. Vậy khối đó bắt đầu từ hàng 3. - Hai vòng lặp lồng nhau
for r in range(start_row, start_row + 3):vàfor c in range(start_col, start_col + 3):duyệt qua tất cả các ô trong khối 3x3 đó. if grid[r][c] == num and (r, c) != pos:kiểm tra xem sốnumcó xuất hiện ở ô(r, c)nào khác ngoài ô hiện tại (pos) trong khối đó không. Nếu có, trả vềFalse.
- Chúng ta cần tìm tọa độ bắt đầu của khối 3x3 chứa ô
- Nếu cả ba phần kiểm tra đều không trả về
False, điều đó có nghĩa là sốnumcó thể đặt vào vị tríposmà không vi phạm bất kỳ luật nào. Hàm trả vềTrue.
Hàm giải chính (solve)
Đây là trái tim của thuật toán Backtracking. Hàm này sẽ thực hiện quá trình thử và quay lui một cách đệ quy.
def solve(grid):
"""
Giải bảng Sudoku bằng thuật toán Backtracking.
Trả về True nếu giải thành công, ngược lại trả về False.
"""
# 1. Điều kiện dừng (Base Case): Tìm ô trống tiếp theo
find = find_empty(grid)
if not find:
# Nếu không tìm thấy ô trống nào, nghĩa là bảng đã điền đầy
# và nếu đến được đây thì tất cả các bước trước đều hợp lệ.
# Bảng đã được giải xong!
return True
else:
# Nếu tìm thấy ô trống, lưu lại vị trí (hàng, cột)
row, col = find
# 2. Bước đệ quy: Thử các số từ 1 đến 9 vào ô trống vừa tìm được
for num in range(1, 10): # Thử các số từ 1 đến 9
# Kiểm tra xem việc đặt số 'num' vào vị trí (row, col) có hợp lệ không
if is_valid(grid, num, (row, col)):
# Nếu hợp lệ:
# Đặt số 'num' vào ô trống
grid[row][col] = num
# Tiếp tục giải phần còn lại của bảng bằng cách gọi đệ quy
if solve(grid):
# Nếu lời gọi đệ quy 'solve(grid)' trả về True,
# điều đó có nghĩa là từ điểm này trở đi, thuật toán đã tìm
# được một lời giải hoàn chỉnh cho toàn bộ bảng.
# Tuyệt vời! Chúng ta chỉ cần trả về True ngay lập tức.
return True
# Nếu lời gọi đệ quy 'solve(grid)' trả về False,
# điều đó có nghĩa là việc đặt số 'num' vào vị trí này
# không dẫn đến lời giải cho toàn bộ bảng.
# Chúng ta phải 'quay lui' (backtrack): xóa số vừa đặt
# và thử con số khác cho ô trống hiện tại.
grid[row][col] = 0 # Đặt lại ô trống thành 0
# 3. Nếu vòng lặp kết thúc mà không có con số nào từ 1 đến 9
# dẫn đến lời giải thành công (tất cả các lời gọi đệ quy đều trả về False),
# điều đó có nghĩa là không thể giải được bảng từ vị trí này
# với các giá trị đã được đặt ở các bước trước.
# Chúng ta trả về False để bước gọi trước đó có thể quay lui.
return False
# Ví dụ sử dụng (cần có hàm print_grid để hiển thị kết quả)
# if solve(grid):
# print("Đã giải thành công:")
# print_grid(grid)
# else:
# print("Không thể giải được bảng Sudoku này.")
Giải thích code solve:
- Base Case: Dòng
find = find_empty(grid)cố gắng tìm ô trống tiếp theo.if not find:kiểm tra xemfind_emptycó trả vềNonekhông. Nếu có (not findlàTrue), điều đó có nghĩa là không còn ô trống nào. Tại điểm này, nếu thuật toán đến được đây, tức là tất cả các ô đã được điền một cách hợp lệ (do các kiểm trais_validở các bước trước đó), vì vậy bảng đã được giải! Hàm trả vềTrue. Đây là điều kiện dừng của đệ quy. - Recursive Step: Nếu vẫn còn ô trống, chúng ta lấy vị trí
(row, col)của nó.- Vòng lặp
for num in range(1, 10):thử lần lượt các số từ 1 đến 9. if is_valid(grid, num, (row, col)):kiểm tra xem việc đặt sốnumvào ô trống hiện tại có hợp lệ không.- Nếu hợp lệ:
grid[row][col] = num: Chúng ta tạm thời đặt sốnumvào ô trống.if solve(grid): return True: Đây là bước đệ quy. Chúng ta gọi lại hàmsolvevới bảng đã được cập nhật. Nếu lời gọi này trả vềTrue, nó có nghĩa là từ điểm này trở đi, toàn bộ phần còn lại của bảng đã được giải thành công. Vì vậy, chúng ta biết rằng con đường giải pháp này là đúng, và chúng ta trả vềTruengay lập tức để các lời gọisolveở các cấp trên cũng trả vềTrue.
- Nếu không hợp lệ hoặc lời gọi đệ quy trả về
False:grid[row][col] = 0: Đây là bước quay lui. Nếu sốnumkhông hợp lệ hoặc không dẫn đến lời giải (đệ quy trả vềFalse), chúng ta phải xóa sốnumvừa đặt bằng cách đặt lại giá trị ô về0. Điều này cho phép vòng lặpfor numtiếp tục thử con số tiếp theo cho ô trống ban đầu.
- Vòng lặp
- Nếu vòng lặp
for numkết thúc: Nếu đã thử tất cả các số từ 1 đến 9 cho ô trống(row, col)mà không có số nào dẫn đến lời giải thành công (tức là không cósolve(grid)nào trả vềTrue), điều đó có nghĩa là ô trống này không thể điền số nào hợp lệ với các giá trị đã được đặt ở các bước trước đó. Hàm trả vềFalseđể báo hiệu cho bước gọi trước đó rằng con đường này là bế tắc và cần phải quay lui ở cấp độ đó.
Hàm hiển thị bảng (print_grid)
Để dễ nhìn kết quả, chúng ta sẽ viết một hàm đơn giản để in bảng Sudoku ra màn hình một cách định dạng.
def print_grid(grid):
"""
In bảng Sudoku ra màn hình với định dạng dễ nhìn.
"""
for r in range(9):
if r % 3 == 0 and r != 0: # In đường kẻ ngang sau mỗi 3 hàng (trừ hàng đầu tiên)
print("- - - - - - - - - - - - ")
for c in range(9):
if c % 3 == 0 and c != 0: # In đường kẻ dọc sau mỗi 3 cột (trừ cột đầu tiên)
print(" | ", end="") # end="" để không xuống dòng sau khi in " | "
if c == 8: # Nếu là cột cuối cùng
print(grid[r][c]) # In giá trị và xuống dòng
else:
print(str(grid[r][c]) + " ", end="") # In giá trị và một khoảng trắng, không xuống dòng
# Ví dụ sử dụng:
# print_grid(grid) # In bảng Sudoku ban đầu
Giải thích code print_grid:
- Chúng ta dùng hai vòng lặp lồng nhau để duyệt qua bảng.
if r % 3 == 0 and r != 0:kiểm tra xem chỉ số hàngrcó chia hết cho 3 hay không (tức là sau hàng 2, hàng 5). Nếu có và không phải là hàng 0, chúng ta in ra một dòng ký tự"-"để tạo đường kẻ ngang.if c % 3 == 0 and c != 0:kiểm tra xem chỉ số cộtccó chia hết cho 3 hay không (tức là sau cột 2, cột 5). Nếu có và không phải là cột 0, chúng ta in ra ký tự" | "để tạo đường kẻ dọc giữa các khối 3x3.end=""ngănprinttự động xuống dòng.if c == 8:Nếu đang ở cột cuối cùng (chỉ số 8), chúng ta in giá trị của ô và dùngprint(grid[r][c])để xuống dòng sau khi in xong một hàng.else: print(str(grid[r][c]) + " ", end=""): Đối với các cột khác, chúng ta in giá trị của ô, thêm một khoảng trắng để các số không dính vào nhau, và dùngend=""để không xuống dòng, chuẩn bị in ô tiếp theo trong cùng hàng.
Kết hợp tất cả lại
Bây giờ, chúng ta đã có tất cả các thành phần cần thiết. Hãy đặt chúng lại với nhau trong một script hoàn chỉnh.
# Bảng Sudoku để giải (ví dụ từ đầu bài)
grid = [
[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]
]
def print_grid(grid):
"""
In bảng Sudoku ra màn hình với định dạng dễ nhìn.
"""
for r in range(9):
if r % 3 == 0 and r != 0:
print("- - - - - - - - - - - - ")
for c in range(9):
if c % 3 == 0 and c != 0:
print(" | ", end="")
if c == 8:
print(grid[r][c])
else:
print(str(grid[r][c]) + " ", end="")
def find_empty(grid):
"""
Tìm ô trống tiếp theo trong bảng (ký hiệu bằng 0).
Trả về tuple (row, col) nếu tìm thấy, ngược lại trả về None.
"""
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
return (r, c)
return None
def is_valid(grid, num, pos):
"""
Kiểm tra xem việc đặt số 'num' vào vị trí 'pos' (tuple (row, col))
có hợp lệ theo luật Sudoku hay không.
"""
row, col = pos
# Kiểm tra hàng
for c in range(9):
if grid[row][c] == num and c != col:
return False
# Kiểm tra cột
for r in range(9):
if grid[r][col] == num and r != row:
return False
# Kiểm tra khối 3x3
start_row = row - row % 3
start_col = col - col % 3
for r in range(start_row, start_row + 3):
for c in range(start_col, start_col + 3):
if grid[r][c] == num and (r, c) != pos:
return False
return True
def solve(grid):
"""
Giải bảng Sudoku bằng thuật toán Backtracking.
Trả về True nếu giải thành công, ngược lại trả về False.
"""
find = find_empty(grid)
if not find:
return True
else:
row, col = find
for num in range(1, 10):
if is_valid(grid, num, (row, col)):
grid[row][col] = num
if solve(grid):
return True
grid[row][col] = 0 # Quay lui
return False
# --- Chương trình chính ---
print("Bảng Sudoku ban đầu:")
print_grid(grid)
print("\n" + "="*20 + "\n") # In dấu phân cách
print("Đang giải...")
if solve(grid):
print("Đã giải thành công:")
print_grid(grid)
else:
print("Không thể giải được bảng Sudoku này.")
# --- Thử với một bảng khác (nếu muốn) ---
# grid_harder = [
# [0, 0, 0, 6, 0, 0, 4, 0, 0],
# [7, 0, 0, 0, 0, 3, 6, 0, 0],
# [0, 0, 0, 0, 9, 1, 0, 8, 0],
# [0, 0, 0, 0, 0, 5, 0, 7, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 4, 0, 2, 0, 0, 0, 0, 0],
# [0, 8, 0, 3, 4, 0, 0, 0, 0],
# [9, 6, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0]
# ]
# print("\n" + "="*20 + "\n")
# print("Bảng Sudoku thứ hai:")
# print_grid(grid_harder)
# print("\n" + "="*20 + "\n")
# print("Đang giải bảng thứ hai...")
# if solve(grid_harder):
# print("Đã giải thành công bảng thứ hai:")
# print_grid(grid_harder)
# else:
# print("Không thể giải được bảng Sudoku thứ hai.")
Giải thích Chương trình Chính:
- Chúng ta bắt đầu bằng cách định nghĩa biến
gridchứa bảng Sudoku cần giải. - Sau đó, chúng ta gọi
print_grid(grid)để hiển thị trạng thái ban đầu của bảng. - Dòng
if solve(grid):là nơi chúng ta bắt đầu quá trình giải. Hàmsolvesẽ cố gắng tìm lời giải bằng thuật toán backtracking. - Nếu
solve(grid)trả vềTrue, điều đó có nghĩa là nó đã tìm thấy lời giải và đồng thời cập nhật trực tiếp bảnggridtruyền vào. Chúng ta in thông báo thành công và hiển thị bảng đã giải. - Nếu
solve(grid)trả vềFalse, điều đó có nghĩa là không có lời giải nào tồn tại cho bảng đã cho (hoặc thuật toán gặp vấn đề, nhưng với Sudoku hợp lệ thì nó sẽ luôn tìm ra lời giải). Chúng ta in thông báo không giải được. - Phần code được chú thích ở dưới là ví dụ bạn có thể bỏ chú thích để thử giải một bảng khó hơn.
Chạy thử mã:
Khi bạn chạy đoạn mã Python này, bạn sẽ thấy bảng Sudoku ban đầu được in ra, sau đó chương trình sẽ chạy thuật toán giải, và cuối cùng in ra bảng Sudoku đã được điền đầy đủ và chính xác.
Ví dụ đầu ra (Output):
Bảng Sudoku ban đầu:
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
====================
Đang giải...
Đã giải thành công:
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
- - - - - - - - - - - -
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
- - - - - - - - - - - -
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9(Lưu ý: Định dạng in có thể hơi khác tùy thuộc vào cách bạn chạy code, nhưng cấu trúc và các đường kẻ nên hiển thị tương tự).
Tổng kết bài học
Qua bài này, bạn đã học cách áp dụng thuật toán Backtracking để giải quyết một bài toán cụ thể là Sudoku. Đây là một kỹ thuật mạnh mẽ có thể được sử dụng để giải nhiều bài toán tìm kiếm lời giải khác như bài toán N-Queens, tìm đường trong mê cung, v.v. Bạn đã xây dựng các hàm hỗ trợ để kiểm tra điều kiện và quản lý dữ liệu (bảng Sudoku), và quan trọng nhất là hiểu được cách hàm đệ quy solve hoạt động với cơ chế thử, kiểm tra, và quay lui khi cần thiết.
Mặc dù đây là phiên bản giải Sudoku "đơn giản" (về mặt thuật toán, nó giải được hầu hết các bảng), nhưng code này đã nắm bắt được đầy đủ logic cốt lõi của phương pháp backtracking. Bạn có thể thử nghiệm với các bảng Sudoku khác nhau để xem chương trình hoạt động như thế nào!
Khóa học liên quan
Giảm giá!
Comments