ধরুন আমাদের একটি আংশিকভাবে ভরা সুডোকু গ্রিড আছে এবং আমাদের এটি সমাধান করতে হবে। আমরা জানি যে সুডোকু একটি 9 × 9 সংখ্যার গ্রিড, এবং পুরো গ্রিডটিও 3 × 3 বাক্সে বিভক্ত সুডোকু সমাধান করার জন্য কিছু নিয়ম রয়েছে৷
-
এই সমস্যাটি সমাধানের জন্য আমাদের 1 থেকে 9 সংখ্যাগুলি ব্যবহার করতে হবে৷
-
এক সারি, একটি কলাম বা একটি 3 × 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(row − row mod 3, col − col mod 3, num) সবই মিথ্যা হয়, তাহলে সত্য ফেরত দিন
-
সমাধানসুডোকু() নামক একটি পদ্ধতি নির্ধারণ করুন, এটি গ্রিড গ্রহণ করবে
-
যদি গ্রিডে কোনো স্থান খালি না থাকে, তাহলে সত্য ফেরত দিন
-
1 থেকে 9 নম্বরের জন্য, করুন
-
যদি হয় ValidPlace(সারি, কল, সংখ্যা), তাহলে
-
গ্রিড[সারি, কল] :=সংখ্যা
-
যদি solveSudoku =true, তারপর true রিটার্ন করুন
-
গ্রিড[সারি, কল] :=0
-
-
-
মিথ্যা ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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) &&
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) &&
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
