सी++ में सुडोकू सॉल्वर

मान लीजिए कि हमारे पास सुडोकू ग्रिड है और हमें इस प्रसिद्ध संख्या भूलभुलैया समस्या, सुडोकू को हल करना है। हम जानते हैं कि सुडोकू एक 9 x 9 नंबर का ग्रिड है, और पूरे ग्रिड को भी 3 x 3 बॉक्स में विभाजित किया गया है सुडोकू को हल करने के लिए कुछ नियम हैं।

• इस समस्या को हल करने के लिए हमें अंक 1 से 9 तक का उपयोग करना होगा।

• एक अंक को एक पंक्ति, एक कॉलम या एक 3 x 3 बॉक्स में दोहराया नहीं जा सकता।

बैकट्रैकिंग एल्गोरिदम का उपयोग करके, हम सुडोकू समस्या को हल करने का प्रयास करेंगे। जब कोई सेल एक अंक से भर जाता है, तो यह जांचता है कि यह वैध है या नहीं। जब यह मान्य नहीं होता है, तो यह अन्य नंबरों की जांच करता है। यदि सभी नंबरों को 1-9 से चेक किया जाता है, और कोई मान्य अंक नहीं पाया जाता है, तो यह पिछले विकल्प पर वापस आ जाता है।

तो अगर इनपुट की तरह है -

आउटपुट होगा -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• isPresentInCol () नामक एक विधि को परिभाषित करें, यह कॉल और संख्या लेगा

• ग्रिड में प्रत्येक पंक्ति r के लिए, करें

  • अगर ग्रिड [r, col] =num, तो सही लौटें

• अन्यथा झूठी वापसी करें

• isPresentInRow() नामक एक विधि को परिभाषित करें, इसमें पंक्ति और संख्या लगेगी

• ग्रिड में प्रत्येक कॉलम c के लिए, करें

  • अगर ग्रिड [पंक्ति, सी] =संख्या, फिर सही लौटें

• अन्यथा झूठी वापसी करें

• isPresentInBox() नामक एक विधि को परिभाषित करें, यह boxStartRow, boxStartCol, num

  लेगी।

• प्रत्येक पंक्ति r के लिए boxStartRow में अगली 3 पंक्तियों के लिए, करें

  • BoxStartCol में प्रत्येक कॉलम के लिए अगले 3 कॉलम में, करें

    • अगर ग्रिड [r, c] =num, तो सही लौटें

• अन्यथा झूठी वापसी करें

• FindEmptyPlace() नामक एक विधि को परिभाषित करें, यह पंक्ति और कॉल लेगा

• ग्रिड में प्रत्येक पंक्ति r के लिए, करें

  • ग्रिड में प्रत्येक कॉलम c के लिए, करें

    • अगर ग्रिड [आर, सी] =0, तो सही लौटें

• झूठी वापसी

• isValidPlace() नामक एक विधि को परिभाषित करें, इसमें पंक्ति, कॉलम, संख्या लगेगी

• यदि isPresentInRow(row, num) और isPresentInCol(col, num) और isPresntInBox(row - row mod 3, col - col mod 3, num) सभी गलत हैं, तो सही लौटें

• सॉल्वसुडोकू () नामक एक विधि को परिभाषित करें, यह ग्रिड लेगा

• अगर ग्रिड में कोई जगह खाली नहीं है, तो सही लौटें

• 1 से 9 नंबर के लिए करें

  • अगर isValidPlace(row, col, number), तो

    • ग्रिड [पंक्ति, कर्नल] :=संख्या

    • यदि हल सुडोकू =सत्य है, तो सत्य लौटाएं

    • ग्रिड [पंक्ति, col] :=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