Đề bài:
Viết một chương trình để giải một câu đố Sudoku bằng cách điền vào các ô trống.
Một giải pháp Sudoku phải thỏa mãn tất cả các quy tắc sau:
- Mỗi chữ số từ 1-9 phải xuất hiện đúng một lần trong mỗi hàng.
- Mỗi chữ số từ 1-9 phải xuất hiện đúng một lần trong mỗi cột.
- Mỗi chữ số từ 1-9 phải xuất hiện đúng một lần trong mỗi trong số 9 ô con 3×3 trên bảng.
Ký tự ‘.’ chỉ định các ô trống.
Ví dụ 1:
Input: board = [["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"]] Output: [["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"]] Giải thích: Bảng đầu vào được hiển thị ở trên và giải pháp duy nhất hợp lệ được hiển thị ở dưới:
Ràng buộc:
- board.length == 9 (độ dài của board là 9)
- board[i].length == 9 (độ dài của mỗi hàng của board là 9)
- board[i][j] là một chữ số hoặc ‘.’.
- Đảm bảo rằng bảng đầu vào chỉ có một giải pháp duy nhất.
Giải thích thuật toán bằng C ++
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
solve(board, 0);
}
private:
bool solve(vector<vector<char>>& board, int s) {
if (s == 81)
return true;
const int i = s / 9;
const int j = s % 9;
if (board[i][j] != '.')
return solve(board, s + 1);
for (char c = '1'; c <= '9'; ++c)
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board, s + 1))
return true;
board[i][j] = '.';
}
return false;
}
bool isValid(vector<vector<char>>& board, int row, int col, char c) {
for (int i = 0; i < 9; ++i)
if (board[i] == c || board[i] == c ||
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
return true;
}
};
Đoạn code trên là một đoạn code C++ để giải một câu đố Sudoku bằng phương pháp đệ quy. Dưới đây là giải thích về thuật toán trong đoạn code:
1. Hàm `solveSudoku` là hàm gọi chính để giải câu đố Sudoku. Hàm này gọi hàm `solve` với đối số là bảng Sudoku và vị trí bắt đầu (s = 0).
2. Hàm `solve` là hàm đệ quy để giải câu đố Sudoku. Đầu tiên, nếu vị trí bằng 81 (đã duyệt qua tất cả các ô), ta trả về true, tức là đã tìm được một giải pháp.
3. Tiếp theo, ta tính toán vị trí hàng (i = s / 9) và vị trí cột (j = s % 9) của ô hiện tại.
4. Nếu ô hiện tại không phải là ô trống (không phải ký tự ‘.’), ta gọi đệ quy hàm `solve` với vị trí tiếp theo (s + 1).
5. Nếu ô hiện tại là ô trống, ta duyệt qua các chữ số từ ‘1’ đến ‘9’ và kiểm tra tính hợp lệ của việc điền chữ số đó vào ô hiện tại bằng cách gọi hàm `isValid`. Nếu chữ số đó hợp lệ, ta gán chữ số vào ô hiện tại và gọi đệ quy hàm `solve` với vị trí tiếp theo (s + 1). Nếu giải pháp tìm được, ta trả về true. Nếu không tìm được giải pháp, ta đặt lại ô hiện tại thành ô trống và tiếp tục vòng lặp để thử các giá trị khác.
6. Nếu không tìm được giải pháp sau khi duyệt qua tất cả các chữ số từ ‘1’ đến ‘9’, ta trả về false.
7. Hàm `isValid` được sử dụng để kiểm tra tính hợp lệ của việc điền chữ số c vào ô tại hàng row, cột col của bảng Sudoku. Hàm này kiểm tra xem chữ số c đã xuất hiện trong cùng một hàng, cột hoặc ô con 3×3 nào khác trên bảng chưa. Nếu đã xuất hiện, ta trả về false. Nếu chưa xuất hiện, ta trả về true.
Thuật toán trên sử dụng phương pháp đệ quy để thử từng giá trị từ ‘1’ đến ‘9’ cho mỗi ô trống. Khi tìm được một giá trị hợp lệ, ta tiếp tục đệ quy để điền các ô tiếp theo. Nếu không tìm được giải pháp cho một ô, ta quay lại và thử giá trị khác cho ô trước đó. Thuật toán này sẽ tiếp tục đệ quy cho đến khi tìm được một giải pháp hoặc duyệt qua tất cả các ô mà không tìm được giải pháp.
Giải thích thuật toán bằng Java
class Solution {
public void solveSudoku(char[][] board) {
dfs(board, 0);
}
private boolean dfs(char[][] board, int s) {
if (s == 81)
return true;
final int i = s / 9;
final int j = s % 9;
if (board[i][j] != '.')
return dfs(board, s + 1);
for (char c = '1'; c <= '9'; ++c)
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (dfs(board, s + 1))
return true;
board[i][j] = '.';
}
return false;
}
private boolean isValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; ++i)
if (board[i] == c || board[i] == c ||
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
return true;
}
}
Giải thích thuật toán bằng Python
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def isValid(row: int, col: int, c: str) -> bool:
for i in range(9):
if board[i] == c or \
board[i] == c or \
board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == c:
return False
return True
def solve(s: int) -> bool:
if s == 81:
return True
i = s // 9
j = s % 9
if board[i][j] != '.':
return solve(s + 1)
for c in string.digits[1:]:
if isValid(i, j, c):
board[i][j] = c
if solve(s + 1):
return True
board[i][j] = '.'
return False
solve(0)
0 / 5 - (0 Đánh Giá)