ধরুন আমরা সুডোকু নামে একটি 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"]]
আউটপুট - সত্য।
ব্যাখ্যা − যেহেতু সুডোকু ম্যাট্রিক্সের ভিতরের সমস্ত সংখ্যা একটি বৈধ সুডোকুর প্যাটার্ন অনুসরণ করে, তাই আউটপুটটি সত্য৷
এই সমস্যা সমাধানের পদ্ধতি
প্রাথমিকভাবে আমরা পরীক্ষা করব যে প্রদত্ত সুডোকু বোর্ডে অনন্য সংখ্যা সহ কলাম আছে কি না। তারপর আমরা সারি জন্য পরীক্ষা করা হবে. প্রতিটি 3*3 ব্লকে অনন্য সব সংখ্যা থাকে। আমরা প্রতিটি ব্লক সারি এবং ব্লক কলাম পরীক্ষা করব যদি এতে কোনো নম্বর সদৃশ থাকে তাহলে আমরা মিথ্যা ফেরত দেব অন্যথায় সত্য ফেরত দেব।
-
সুডোকু বোর্ডের জন্য একটি 2-ডি অ্যারের ইনপুট নিন।
-
একটি বুলিয়ান ফাংশন যা সারিটিতে উপস্থিত উপাদানগুলি অনন্য কিনা তা পরীক্ষা করার জন্য৷
৷ -
কলামে উপস্থিত উপাদানগুলি অনন্য কিনা তা পরীক্ষা করার জন্য একটি বুলিয়ান ফাংশন৷
৷ -
একটি বুলিয়ান ফাংশন যা ব্লকে উপস্থিত উপাদানগুলি অনন্য কিনা তা পরীক্ষা করার জন্য৷
উদাহরণ
#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
