मान लीजिए हमें 9×9 मैट्रिक्स दिया गया है जिसे सुडोकू कहा जाता है। कार्य यह जांचना है कि दिया गया सुडोकू पैटर्न मान्य है या नहीं।
सामान्य तौर पर, एक सुडोकू बोर्ड इस तरह दिखता है,
सुडोकू के नियम -
- हर रो में 1-9 की रेंज में एक नंबर होता है
- हर कॉलम में 1-9 की रेंज में नंबर होते हैं।
- 3×3 का प्रत्येक ब्लॉक उसमें यूनिक नंबर रखता है।
- कोई विशेष रो एक ही नंबर नहीं रख सकती।
- कोई विशेष कॉलम एक ही नंबर नहीं रख सकता।
उदाहरण के लिए
इनपुट-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"]]
आउटपुट - True.
व्याख्या - चूंकि सुडोकू मैट्रिक्स के अंदर सभी नंबर वैलिड सुडोकू के पैटर्न का पालन करते हैं, आउटपुट True है।
इस समस्या को हल करने का दृष्टिकोण
प्रारंभ में हम जांचेंगे कि दिए गए सुडोकू बोर्ड में कॉलम यूनिक नंबर के साथ है या नहीं। फिर हम रो के लिए जांचेंगे। प्रत्येक 3*3 ब्लॉक में उसमें सभी नंबर यूनिक होते हैं। हम प्रत्येक ब्लॉक रो और ब्लॉक कॉलम की जांच करेंगे यदि इसमें कोई नंबर डुप्लिकेट है तो हम false लौटाएंगे अन्यथा true लौटाएंगे।
- सुडोकू बोर्ड के लिए 2-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;
}
आउटपुट
True
