ধরুন আমাদের একটি সুডোকু গ্রিড আছে এবং আমাদের এই বিখ্যাত সংখ্যার গোলকধাঁধা সমস্যার সমাধান করতে হবে, সুডোকু। আমরা জানি যে সুডোকু একটি 9 x 9 সংখ্যার গ্রিড, এবং পুরো গ্রিডটি 3 x 3 বাক্সে বিভক্ত রয়েছে সুডোকু সমাধানের কিছু নিয়ম রয়েছে।
-
এই সমস্যাটি সমাধানের জন্য আমাদের 1 থেকে 9 সংখ্যাগুলি ব্যবহার করতে হবে৷
-
একটি সংখ্যা এক সারি, একটি কলাম বা একটি 3 x 3 বাক্সে পুনরাবৃত্তি করা যাবে না৷
ব্যাকট্র্যাকিং অ্যালগরিদম ব্যবহার করে, আমরা সুডোকু সমস্যা সমাধান করার চেষ্টা করব। যখন কিছু ঘর একটি সংখ্যা দিয়ে পূর্ণ হয়, এটি বৈধ কিনা তা পরীক্ষা করে। যখন এটি বৈধ নয়, তখন এটি অন্যান্য নম্বরগুলির জন্য পরীক্ষা করে। যদি সমস্ত সংখ্যা 1-9 থেকে চেক করা হয়, এবং কোনও বৈধ সংখ্যা খুঁজে না পাওয়া যায় তবে এটি পূর্ববর্তী বিকল্পে ফিরে যায়৷
তাই যদি ইনপুট −
এর মত হয়
আউটপুট হবে −
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
isPresentInCol() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি কল এবং নম্বর গ্রহণ করবে
-
গ্রিডের প্রতিটি সারির জন্য, করুন
-
যদি grid[r, col] =num হয়, তাহলে true রিটার্ন করুন
-
-
অন্যথায় মিথ্যা ফেরত দিন
-
isPresentInRow() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি সারি এবং সংখ্যা গ্রহণ করবে
-
গ্রিডে প্রতিটি কলাম c-এর জন্য করুন
-
যদি grid[row, c] =num, তাহলে true রিটার্ন করুন
-
-
অন্যথায় মিথ্যা ফেরত দিন
-
isPresentInBox() নামক একটি পদ্ধতি নির্ধারণ করুন এটি boxStartRow, boxStartCol, num
নেবে -
boxStartRow-এ প্রতিটি সারির জন্য পরবর্তী 3 সারিতে, করুন
-
boxStartCol-এ প্রতিটি col r-এর জন্য পরবর্তী 3টি কলাম, করুন
-
যদি grid[r, c] =num, তাহলে true রিটার্ন করুন
-
-
-
অন্যথায় মিথ্যা ফেরত দিন
-
findEmptyPlace() নামে একটি পদ্ধতি নির্ধারণ করুন, এটি সারি এবং কল
লাগবে -
গ্রিডের প্রতিটি সারির জন্য, করুন
-
গ্রিডে প্রতিটি কলাম c-এর জন্য করুন
-
যদি গ্রিড[r, c] =0 হয়, তাহলে true রিটার্ন করুন
-
-
-
মিথ্যা ফেরত দিন
-
isValidPlace() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি সারি, col, num
-
যদি isPresentInRow(সারি, সংখ্যা) এবং isPresentInCol(col, num) এবং isPresntInBox(সারি – সারি মোড 3, কোল – কোল মোড 3, সংখ্যা) সবই মিথ্যা হয়, তাহলে সত্য ফেরত দিন
-
সমাধানসুডোকু() নামক একটি পদ্ধতি নির্ধারণ করুন, এটি গ্রিড গ্রহণ করবে
-
যদি গ্রিডে কোনো স্থান খালি না থাকে, তাহলে সত্য ফেরত দিন
-
1 থেকে 9 নম্বরের জন্য, করুন
-
যদি হয় ValidPlace(সারি, কল, সংখ্যা), তাহলে
-
গ্রিড[সারি, কল] :=সংখ্যা
-
যদি solveSudoku =true, তারপর true রিটার্ন করুন
-
গ্রিড[সারি, কল] :=0
-
-
-
মিথ্যা ফেরত দিন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <iostream>
#define N 9
using namespace std;
int grid[N][N] = {
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}
};
bool isPresentInCol(int col, int num){ //check whether num is present in col or not
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
bool isPresentInRow(int row, int num){ //check whether num is present in row or not
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
bool isPresentInBox(int boxStartRow, int boxStartCol, int num){
//check whether num is present in 3x3 box or not
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
void sudokuGrid(){ //print the sudoku grid after solve
for (int row = 0; row < N; row++){
for (int col = 0; col < N; col++){
if(col == 3 || col == 6)
cout << " | ";
cout << grid[row][col] <<" ";
}
if(row == 2 || row == 5){
cout << endl;
for(int i = 0; i<N; i++)
cout << "---";
}
cout << endl;
}
}
bool findEmptyPlace(int &row, int &col){ //get empty location and update row and column
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == 0) //marked with 0 is empty
return true;
return false;
}
bool isValidPlace(int row, int col, int num){
//when item not found in col, row and current 3x3 box
return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3 ,
col - col%3, num);
}
bool solveSudoku(){
int row, col;
if (!findEmptyPlace(row, col))
return true; //when all places are filled
for (int num = 1; num <= 9; num++){ //valid numbers are 1 - 9
if (isValidPlace(row, col, num)){ //check validation, if yes, put the number in the grid
grid[row][col] = num;
if (solveSudoku()) //recursively go for other rooms in the grid
return true;
grid[row][col] = 0; //turn to unassigned space when conditions are not satisfied
}
}
return false;
}
int main(){
if (solveSudoku() == true)
sudokuGrid();
else
cout << "No solution exists";
} ইনপুট
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0} আউটপুট
3 1 6 | 5 7 8 | 4 9 2 5 2 9 | 1 3 4 | 7 6 8 4 8 7 | 6 2 9 | 5 3 1 --------------------------- 2 6 3 | 4 1 5 | 9 8 7 9 7 4 | 8 6 3 | 1 2 5 8 5 1 | 7 9 2 | 6 4 3 --------------------------- 1 3 8 | 9 4 7 | 2 5 6 6 9 2 | 3 5 1 | 8 7 4 7 4 5 | 2 8 6 | 3 1 9
