৯×৯ সুডোকু বোর্ড বৈধ কিনা চেক করতে হবে: প্রতিটি সারি, কলাম এবং ৩×৩ সাব-বক্সে ১-৯ ডিজিট একবারই থাকতে পারে ('.' = খালি)।
অ্যালগরিদম
- সারি চেক: প্রতিটি সারির জন্য ফ্রিকোয়েন্সি অ্যারে (সাইজ ১০) ব্যবহার করুন।
- কলাম চেক: প্রতিটি কলামের জন্য একই।
- ৩×৩ বক্স চেক: ৯টি বক্সের জন্য (block/3)*3, (block%3)*3 কোঅর্ডিনেট।
- যেকোনো ডুপ্লিকেট পাওয়া গেলে false রিটার্ন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
bool isValidSudoku(vector<vector<char>>& board) {
int count[9];
// Check rows
for (int r = 0; r < 9; r++) {
fill(begin(count), end(count), 0);
for (int c = 0; c < 9; c++) {
if (board[r][c] != '.') count[board[r][c] - '1']++;
}
for (int i = 0; i < 9; i++) if (count[i] > 1) return false;
}
// Check columns
for (int c = 0; c < 9; c++) {
fill(begin(count), end(count), 0);
for (int r = 0; r < 9; r++) {
if (board[r][c] != '.') count[board[r][c] - '1']++;
}
for (int i = 0; i < 9; i++) if (count[i] > 1) return false;
}
// Check 3x3 boxes
for (int block = 0; block < 9; block++) {
fill(begin(count), end(count), 0);
int br = (block / 3) * 3, bc = (block % 3) * 3;
for (int r = br; r < br + 3; r++)
for (int c = bc; c < bc + 3; c++)
if (board[r][c] != '.') count[board[r][c] - '1']++;
for (int i = 0; i < 9; i++) if (count[i] > 1) return false;
}
return true;
}
int main() {
vector<vector<char>> 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'}
};
cout << (isValidSudoku(board) ? "True" : "False") << endl;
return 0;
}
আউটপুট
True
