Bài toán Sudoku
Bài toán Sudoku là một trò chơi trí tuệ phổ biến trên toàn thế giới. Nó được chơi trên một lưới ô vuông 9×9 được chia thành 9 ô vuông con 3×3. Mục tiêu của trò chơi là điền số từ 1 đến 9 vào các ô trống trên lưới sao cho mỗi số chỉ xuất hiện một lần trên mỗi hàng, cột và ô vuông con.
Một bảng Sudoku có dạng như sau:
5 3 _ | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
---------------------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
---------------------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9
Trong bảng này, các ô trống được đánh dấu bằng dấu gạch chân. Để giải bài toán, ta cần điền các số vào các ô trống này sao cho thỏa mãn điều kiện trên.
Có nhiều phương pháp để giải bài toán Sudoku, bao gồm phương pháp thử và sai, phương pháp giải đường đi (backtracking), phương pháp dùng logic và phương pháp dùng thuật toán. Mỗi phương pháp có những ưu điểm và nhược điểm riêng, và có thể áp dụng tốt cho những bài toán Sudoku khác nhau.
Cài đặt Bài toán Sudoku với Python
Để giải bài toán Sudoku với Python, ta có thể sử dụng thuật toán quay lui (backtracking). Bước đầu tiên là đọc vào bảng Sudoku và lưu vào một ma trận 9×9. Các ô trống có thể được đại diện bằng giá trị 0.
Sau đó, ta có thể định nghĩa một hàm để kiểm tra xem một giá trị có hợp lệ để điền vào một ô cụ thể không. Hàm này sẽ kiểm tra xem giá trị đã xuất hiện trên cùng một hàng, cột hoặc ô vuông con hay chưa.
Tiếp theo, ta có thể định nghĩa một hàm quay lui để giải bài toán. Hàm này sẽ điền các giá trị vào các ô trống của bảng Sudoku, bắt đầu từ ô đầu tiên. Nếu giá trị được điền vào ô hiện tại hợp lệ, hàm sẽ chuyển sang ô tiếp theo. Nếu không có giá trị nào hợp lệ, hàm sẽ trở lại ô trước đó và thử các giá trị khác.
Khi hàm điền được giá trị vào ô cuối cùng của bảng Sudoku, ta sẽ in ra bảng đã giải.
Dưới đây là một đoạn mã Python đơn giản để giải bài toán Sudoku:
def is_valid(board, row, col, num):
# Kiểm tra hàng và cột
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
# Kiểm tra ô vuông con
row_start = (row // 3) * 3
col_start = (col // 3) * 3
for i in range(row_start, row_start+3):
for j in range(col_start, col_start+3):
if board[i][j] == num:
return False
return True
def solve(board, row=0, col=0):
if col == 9:
row += 1
col = 0
if row == 9:
return True
if board[row][col] != 0:
return solve(board, row, col+1)
for num in range(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
if solve(board, row, col+1):
return True
board[row][col] = 0
return False
# Đọc vào bảng Sudoku từ file
board = []
with open('sudoku.txt', 'r') as f:
for line in f:
board.append([int(c) for c in line.strip()])
# Giải bài toán
if solve(board):
for row in board:
print(row)
else:
print('Không tìm thấy giải pháp')
Cài đặt Bài toán Sudoku với C++
Tương tự như Python, để giải bài toán Sudoku với C++, ta cũng có thể sử dụng thuật toán quay lui (backtracking). Bước đầu tiên là đọc vào bảng Sudoku và lưu vào một mảng hai chiều 9×9. Các ô trống có thể được đại diện bằng giá trị 0.
Sau đó, ta có thể định nghĩa một hàm để kiểm tra xem một giá trị có hợp lệ để điền vào một ô cụ thể không. Hàm này sẽ kiểm tra xem giá trị đã xuất hiện trên cùng một hàng, cột hoặc ô vuông con hay chưa.
Tiếp theo, ta có thể định nghĩa một hàm quay lui để giải bài toán. Hàm này sẽ điền các giá trị vào các ô trống của bảng Sudoku, bắt đầu từ ô đầu tiên. Nếu giá trị được điền vào ô hiện tại hợp lệ, hàm sẽ chuyển sang ô tiếp theo. Nếu không có giá trị nào hợp lệ, hàm sẽ trở lại ô trước đó và thử các giá trị khác.
Khi hàm điền được giá trị vào ô cuối cùng của bảng Sudoku, ta sẽ in ra bảng đã giải.
Dưới đây là một đoạn mã C++ đơn giản để giải bài toán Sudoku:
#include <iostream>
#include <fstream>
using namespace std;
const int N = 9;
bool isValid(int board[N][N], int row, int col, int num) {
// Kiểm tra hàng và cột
for (int i = 0; i < N; i++) {
if (board[row][i] == num || board[i][col] == num) {
return false;
}
}
// Kiểm tra ô 3x3 chứa ô (row, col)
int startRow = row - row % 3;
int startCol = col - col % 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == num) {
return false;
}
}
}
return true;
}
bool solveSudoku(int board[N][N], int row, int col) {
if (row == N) {
// Đã duyệt hết tất cả các ô trong bảng
return true;
}
if (col == N) {
// Đã duyệt hết tất cả các cột trong hàng hiện tại, chuyển sang hàng tiếp theo
return solveSudoku(board, row + 1, 0);
}
if (board[row][col] != 0) {
// Ô hiện tại đã có giá trị, chuyển sang ô tiếp theo
return solveSudoku(board, row, col + 1);
}
// Thử từng giá trị có thể cho ô hiện tại
for (int num = 1; num <= N; num++) {
if (isValid(board, row, col, num)) {
// Nếu giá trị num hợp lệ, gán giá trị num cho ô hiện tại và chuyển sang ô tiếp theo
board[row][col] = num;
if (solveSudoku(board, row, col + 1)) {
return true;
}
// Nếu không tìm thấy giải pháp, quay lui và thử giá trị khác
board[row][col] = 0;
}
}
// Không tìm thấy giải pháp cho ô hiện tại
return false;
}
void printBoard(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
}
int main() {
int board[N][N];
// Đọc vào bảng Sudoku từ file
ifstream infile("sudoku.txt");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
infile >> board[i][j];
}
}
// Giải bài toán Sudoku
if (solveSudoku(board, 0, 0)) {
// In
Giải thích:
- Hàm
isValidkiểm tra xem giá trịnumcó hợp lệ khi được gán vào ô(row, col)không. Nếu hợp lệ thì trả vềtrue, ngược lại trả vềfalse. - Hàm
solveSudokugiải quyết bài toán Sudoku bằng thuật toán quay lui. Nó sử dụng đệ quy để duyệt qua từng ô trong bảng và thử từng giá trị có thể cho ô đó. Nếu tìm thấy giải pháp thì trả vềtrue, ngược lại trả vềfalse. - Hàm
printBoardin bảng Sudoku ra màn hình.
Trong main(), chương trình đọc bảng Sudoku từ file sudoku.txt, sau đó giải bài toán bằng cách gọi hàm solveSudoku. Nếu tìm thấy giải pháp thì in ra bảng Sudoku đó, ngược lại in ra thông báo không tìm thấy giải pháp.
Đánh giá độ phức tạp
Thuật toán quay lui là một trong những phương pháp phổ biến để giải quyết các bài toán tìm kiếm và tối ưu, và được sử dụng để giải quyết bài toán Sudoku. Tuy nhiên, độ phức tạp của thuật toán này có thể rất lớn, phụ thuộc vào kích thước của bảng Sudoku và số lượng ô trống.
Độ phức tạp của thuật toán quay lui trong trường hợp tốt nhất là O(1), khi bảng Sudoku đã được điền đầy đủ. Tuy nhiên, trong trường hợp xấu nhất, độ phức tạp của thuật toán quay lui là O(9^(n*n)), với n là kích thước của bảng Sudoku. Điều này có nghĩa là số lần đệ quy cần thực hiện sẽ tăng theo cấp số nhân với số ô trống còn lại trong bảng, và sẽ trở thành rất lớn đối với các bảng Sudoku có kích thước lớn.
Thuật toán quay lui có độ phức tạp lớn hơn so với các thuật toán tìm kiếm thông thường như tìm kiếm theo chiều rộng hoặc theo chiều sâu, bởi vì nó cần thực hiện nhiều lần đệ quy để duyệt qua toàn bộ các giá trị có thể cho từng ô trống. Tuy nhiên, trong một số trường hợp, thuật toán quay lui vẫn có thể tốt hơn so với các thuật toán tìm kiếm thông thường, đặc biệt là khi số lượng giá trị có thể cho cho mỗi ô là ít.
Một số thuật toán khác có độ phức tạp thấp hơn và được sử dụng để giải bài toán Sudoku, bao gồm:
- Thuật toán Dancing Links (Xuất hiện từ cuộc thi Sudoku World Championship năm 2005)
- Thuật toán thống kê (Sử dụng các quy tắc thống kê để giải bài toán Sudoku)
- Thuật toán giải mã và mã hóa tương tự (Sử dụng các phương pháp giải mã và mã hóa để giải bài toán Sudoku)
Tuy nhiên, các thuật toán này có thể khó hiểu và khó cài đặt hơn so với thuật toán quay lui./.