Hi mọi người. Mình có đang giải 1 problem về game Sudoku sau: http://ntucoder.net/Submission/Problem/3261
Ý tưởng của mình sẽ là quay lui từng ô từ trái sang phải trên mỗi dòng từ trên xuống dưới, tại mỗi ô đang xét (có giá trị 0) mình sẽ dùng hàm isSafe() để kiểm tra tính hợp lệ của giá trị đặt vào ô đó. Nếu thỏa mãn tiếp tục đệ quy chạy tiếp, không thì chuyển sang giá trị khác (1 -> 9), nếu ko giá trị nào thỏa mãn thì quay lui lại trường hợp trước.
Mình cài đặt thuật toán như sau: https://ideone.com/4AxU4F
#include <iostream>
#include <vector>
#define N 9
using namespace std;
bool isSafe(const vector<vector<int>> &board, int row, int col, int val)
{
// check row
for (int i = 0; i < N; ++i) {
if (board[row][i] == val)
return false;
}
// check column
for (int i = 0; i < N; ++i) {
if (board[i][col] == val)
return false;
}
// first 3x3 square
if (row <= 2 && col <= 2) {
for (int i = 0; i <= 2; ++i) {
for (int j = 0; j <= 2; ++j) {
if (board[i][j] == val)
return false;
}
}
}
// second 3x3 square
if (row <= 2 && col >= 3 && col <= 5) {
for (int i = 0; i <= 2; ++i) {
for (int j = 3; j <= 5; ++j) {
if (board[i][j] == val)
return false;
}
}
}
// third 3x3 square
if (row <= 2 && col >= 6 && col <= 8) {
for (int i = 0; i <= 2; ++i) {
for (int j = 6; j <= 8; ++j) {
if (board[i][j] == val)
return false;
}
}
}
// fourth 3x3 square
if (row >= 3 && row <= 5 && col <= 2) {
for (int i = 3; i <= 5; ++i) {
for (int j = 0; j <= 2; ++j) {
if (board[i][j] == val)
return false;
}
}
}
// fifth 3x3 square
if (row >= 3 && row <= 5 && col >= 3 && col <= 5) {
for (int i = 3; i <= 5; ++i) {
for (int j = 3; j <= 5; ++j) {
if (board[i][j] == val)
return false;
}
}
}
// sixth 3x3 square
if (row >= 3 && row <= 5 && col >= 6 && col <= 8) {
for (int i = 3; i <= 5; ++i) {
for (int j = 6; j <= 8; ++j) {
if (board[i][j] == val)
return false;
}
}
}
// seventh 3x3 square
if (row >= 6 && row <= 8 && col <= 2) {
for (int i = 6; i <= 8; ++i) {
for (int j = 0; j <= 2; ++j) {
if (board[i][j] == val)
return false;
}
}
}
// eighth 3x3 square
if (row >= 6 && row <= 8 && col >= 3 && col <= 5) {
for (int i = 6; i <= 8; ++i) {
for (int j = 3; j <= 5; ++j) {
if (board[i][j] == val)
return false;
}
}
}
// ninth 3x3 square
if (row >= 6 && row <= 8 && col >= 6 && col <= 8) {
for (int i = 6; i <= 8; ++i) {
for (int j = 6; j <= 8; ++j) {
if (board[i][j] == val)
return false;
}
}
}
return true;
}
bool solveSudoku(vector<vector<int>> &board, int row = 0, int col = 0)
{
// if reaching the final square of sudoku board
if (row == N && col == N) {
return true;
}
// if reaching the final square of each row
if (row < N && col == N) {
if (solveSudoku(board, row + 1)) {
return true;
}
return false;
}
// if the square doesn't have a number
if (board[row][col] == 0)
{
for (int i = 1; i <= 9; ++i)
{
if (isSafe(board, row, col, i))
{
board[row][col] = i;
if (solveSudoku(board, row, col + 1))
return true;
board[row][col] = 0; // backtrack
}
}
return false;
}
else {
// if the final square on each row has a number
if (row < N - 1 && col == N - 1) {
if (solveSudoku(board, row + 1, 0))
return true;
}
// if the final square of sudoku board has a number
if (row == N - 1 && col == N - 1) {
if (solveSudoku(board, row + 1, col + 1))
return true;
}
// normal
else {
if (solveSudoku(board, row, col + 1))
return true;
}
return false;
}
}
int main()
{
vector<vector<int>> sudoku(N);
for (int i = 0; i < N; ++i) {
sudoku[i].resize(N);
for (int j = 0; j < N; ++j) {
cin >> sudoku[i][j];
}
}
if (solveSudoku(sudoku)) {
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
cout << sudoku[i][j] << " ";
}
cout << endl;
}
}
else cout << -1;
return 0;
}
Vì code khá dài dòng nên mình chú thích cho mọi người đọc dễ hiểu hơn tí.
Khi submit thì mình chỉ đúng 6/10 tests, cụ thể như sau: https://ideone.com/IPIVMf
(mình bị runtime error ở test 2, 3, 7, 9)
Dò mãi vẫn không biết code chạy vô tận ở chỗ nào, mong mọi người giúp đỡ ạ !
Xin cảm ơn.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?