Giả sử chúng ta đã đưa ra một ma trận 9 × 9 được gọi là Sudoku. Nhiệm vụ là kiểm tra xem Mẫu Sudoku đã cho có hợp lệ hay không.
Nói chung, một bảng Sudoku trông như thế này,
Quy tắc Sudoku -
-
Mỗi hàng chứa một số trong phạm vi 1-9
-
Mỗi cột chứa các số trong phạm vi 1-9.
-
Mỗi khối 3 × 3 chứa các số duy nhất trong đó.
-
Một hàng cụ thể không được có cùng một số.
-
Một cột cụ thể không được có cùng một số.
Ví dụ
Đầu vào-1 -
sudoku[]= [["3","5",".",".","2",".",".",".","."] ,["7",".",".","1","6","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","5",".","4",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]]
Đầu ra - Đúng.
Giải thích - Vì tất cả các số bên trong ma trận Sudoku đều tuân theo mẫu của một Sudoku hợp lệ nên kết quả đầu ra là True.
Phương pháp tiếp cận để giải quyết vấn đề này
Ban đầu, chúng tôi sẽ kiểm tra xem bảng Sudoku đã cho có cột có các số duy nhất hay không. Sau đó, chúng tôi sẽ kiểm tra hàng. Mỗi khối 3 * 3 chứa tất cả các số duy nhất trong đó. Chúng tôi sẽ kiểm tra từng hàng khối và cột khối nếu nó chứa bất kỳ số nào trùng lặp, chúng tôi sẽ trả về false nếu không sẽ trả về true.
-
Lấy đầu vào của mảng 2-D cho bảng Sudoku.
-
Một hàm Boolean để kiểm tra hàng xem các phần tử có trong nó có phải là duy nhất hay không.
-
Một hàm Boolean để kiểm tra cột xem các phần tử có trong nó có phải là duy nhất hay không.
-
Một hàm Boolean để kiểm tra khối xem các phần tử có trong nó có phải là duy nhất hay không.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
bool validSudoku(vector<vector<char>>& sudoku) {
int row = 0, col = 0, i = 0, block = 0;
int count[9];
for (row = 0; row < 9; ++row){
memset(count, 0, 9 * sizeof(int));
for (col = 0; col < 9; ++col){
if (sudoku[row][col] != '.')
++count[sudoku[row][col]-'1'];
}
for (i = 0; i < 9; ++i)
if (count[i] > 1)
return false;
}
for (col = 0; col < 9; ++col){
memset(count, 0, 9 * sizeof(int));
for (row = 0; row < 9; ++row){
if (sudoku[row][col] != '.')
++count[sudoku[row][col]-'1'];
}
for (i = 0; i < 9; ++i)
if (count[i] > 1)
return false;
}
int block_row = 0, block_col = 0;
for (block = 0; block < 9; ++block){
block_row = (block / 3) * 3, block_col = (block % 3) * 3;
memset(count, 0, 9 * sizeof(int));
for (row = block_row; row < (block_row + 3); ++row)
for (col = block_col; col < (block_col + 3); ++col)
if (sudoku[row][col] != '.')
++count[sudoku[row][col] - '1'];
for (i = 0; i < 9; ++i)
if (count[i] > 1)
return false;
}
return true;
}
int main(){
vector<vector<char> > sudoku= {
{'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'}
};
bool ans= validSudoku(sudoku);
if(ans){
cout<<"True"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
} Đầu ra
True