সুডোকু সমাধান করার অ্যালগরিদম

এই বিভাগে, আমরা সুডোকু নামক বিখ্যাত নম্বর গোলকধাঁধা সমস্যার সমাধান করার চেষ্টা করব। সুডোকু হল একটি 9 x 9 সংখ্যার গ্রিড, এবং পুরো গ্রিডটিও 3 x 3 বাক্সে ভাগ করা হয়েছে সুডোকু সমাধানের জন্য কিছু নিয়ম রয়েছে।

এই সমস্যাটি সমাধানের জন্য আমাদের 1 থেকে 9 সংখ্যাগুলি ব্যবহার করতে হবে৷

একটি সংখ্যা এক সারি, একটি কলাম বা একটি 3 x 3 বাক্সে পুনরাবৃত্তি করা যাবে না৷

ব্যাকট্র্যাকিং অ্যালগরিদম ব্যবহার করে, আমরা সুডোকু সমস্যা সমাধান করার চেষ্টা করব। যখন কিছু ঘর একটি সংখ্যা দিয়ে পূর্ণ হয়, এটি বৈধ কিনা তা পরীক্ষা করে। যখন এটি বৈধ নয়, তখন এটি অন্যান্য নম্বরগুলির জন্য পরীক্ষা করে। যদি সমস্ত সংখ্যা 1-9 পর্যন্ত চেক করা হয়, এবং স্থাপন করার জন্য কোন বৈধ সংখ্যা পাওয়া না যায়, তাহলে এটি পূর্ববর্তী বিকল্পে ফিরে যায়।

ইনপুট এবং আউটপুট

Input:
This will take a 9 x 9 matrix as Sudoku grid. Some values are placed in the grid. The blank spaces are denoted by 0.

Output:
The final matrix (Sudoku grid) filled with numbers. If the solution does not exist, it will return false.

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    

অ্যালগরিদম

isPresentInCol(col, num)

ইনপুট: কলাম, এবং টার্গেট করা সংখ্যা।

আউটপুট - প্রদত্ত কলামে সংখ্যা উপস্থিত থাকলে সত্য৷

Begin
   for each row r in the grid, do
      if grid[r, col] = num, then
         return true
   done
   return false otherwise
End

isPresentInRow(সারি, সংখ্যা)

ইনপুট - সারি, এবং টার্গেট করা সংখ্যা।

আউটপুট - প্রদত্ত কলামে সংখ্যা উপস্থিত থাকলে সত্য৷

Begin
   for each column c in the grid, do
      if grid[row, c] = num, then
         return true
   done
   return false otherwise
End

isPresentInBox(boxStartRow, boxStartCol, num)

ইনপুট - একটি 3 x 3 বাক্সের প্রারম্ভিক সারি এবং কলাম এবং লক্ষ্যযুক্ত সংখ্যা৷

আউটপুট - নম্বরটি বাক্সে উপস্থিত থাকলে সত্য৷

Begin
   for each row r in boxStartRow to next 3 rows, do
      for each col r in boxStartCol to next 3 columns, do
         if grid[r, c] = num, then
            return true
      done
   done
   return false otherwise
End

findEmptyPlace(সারি, কল)

ইনপুট: গ্রিডে সারি এবং কলাম।

আউটপুট - যদি গ্রিড[সারি, কোল] খালি থাকে, তাহলে সত্য ফেরত দিন, অন্যথায় মিথ্যা।

Begin
   for each row r in the grid, do
      for each column c in the grid, do
         if grid[r, c] = 0, then
            return true
      done
   done
   return false
End

isValidPlace(সারি, কল, সংখ্যা)

ইনপুট: সারি, গ্রিডের একটি কলাম এবং চেক করার জন্য নম্বর।

আউটপুট: সত্য, অবস্থান গ্রিডে নম্বর স্থাপন করার সময় [সারি, কোল] বৈধ।

Begin
   if isPresentInRow(row, num) and isPresentInCol(col, num) and
   isPresntInBox(row – row mod 3, col – col mod 3, num) all are false, then
      return true
End

সল্ভ সুডোকু(সুডোকু গ্রিড)

ইনপুট: সুডোকু-এর অমীমাংসিত গ্রিড।

আউটপুট: সমাধানের পরে গ্রিড করুন।

Begin
   if no place in the grid is empty, then
      return true
   for number 1 to 9, do
      if isValidPlace(row, col, number), then
         grid[row, col] := number
         if solveSudoku = true, then
            return true
         grid[row, col] := 0
   done
   return false
End

উদাহরণ

#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 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