मान लीजिए हमारे पास एक आंशिक रूप से भरा सुडोकू ग्रिड है और हमें इसे हल करना है। हम जानते हैं कि सुडोकू एक 9 × 9 संख्या ग्रिड है, और पूरा ग्रिड 3 × 3 बॉक्स में भी विभाजित है। सुडोकू हल करने के कुछ नियम हैं।
हमें इस समस्या को हल करने के लिए 1 से 9 तक के अंकों का उपयोग करना है।
एक अंक को एक पंक्ति, एक स्तंभ या एक 3 × 3 बॉक्स में दोहराया नहीं जा सकता।
बैकट्रैकिंग एल्गोरिदम का उपयोग करके, हम सुडोकू समस्या को हल करने का प्रयास करेंगे। जब किसी सेल को अंक से भरा जाता है, तो यह जांचता है कि यह वैध है या नहीं। जब यह वैध नहीं होता है, तो यह अन्य संख्याओं की जांच करता है। यदि 1-9 से सभी संख्याओं की जांच की जाती है, और रखने के लिए कोई वैध अंक नहीं मिलता है, तो यह पिछले विकल्प पर बैकट्रैक करता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
isPresentInCol() नामक एक विधि परिभाषित करें, यह कॉलम और नंबर लेगी
ग्रिड में प्रत्येक पंक्ति r के लिए, करें
यदि grid[r, col] = num, तो true लौटाएं
अन्यथा false लौटाएं
isPresentInRow() नामक एक विधि परिभाषित करें, यह पंक्ति और नंबर लेगी
ग्रिड में प्रत्येक स्तंभ c के लिए, करें
यदि grid[row, c] = num, तो true लौटाएं
अन्यथा false लौटाएं
isPresentInBox() नामक एक विधि परिभाषित करें यह boxStartRow, boxStartCol, num लेगी
boxStartRow से अगली 3 पंक्तियों तक प्रत्येक पंक्ति r के लिए, करें
boxStartCol से अगले 3 स्तंभों तक प्रत्येक स्तंभ c के लिए, करें
यदि grid[r, c] = num, तो true लौटाएं
अन्यथा false लौटाएं
findEmptyPlace() नामक एक विधि परिभाषित करें, यह पंक्ति और स्तंभ लेगी
ग्रिड में प्रत्येक पंक्ति r के लिए, करें
ग्रिड में प्रत्येक स्तंभ c के लिए, करें
यदि grid[r, c] = 0, तो true लौटाएं
false लौटाएं
isValidPlace() नामक एक विधि परिभाषित करें, यह पंक्ति, स्तंभ, नंबर लेगी
यदि isPresentInRow(row, num) और isPresentInCol(col, num) और isPresentInBox(row - row mod 3, col - col mod 3, num) सभी false हैं, तो true लौटाएं
solveSudoku() नामक एक विधि परिभाषित करें, यह ग्रिड लेगी
यदि ग्रिड में कोई स्थान खाली नहीं है, तो true लौटाएं
संख्या 1 से 9 के लिए, करें
यदि isValidPlace(row, col, number), तो
grid[row, col] := number
यदि solveSudoku = true, तो true लौटाएं
grid[row, col] := 0
false लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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){ //जांचें कि क्या num कॉलम में मौजूद है for (int row = 0; row < N; row++) if (grid[row][col] == num) return true; return false; } bool isPresentInRow(int row, int num){ //जांचें कि क्या num पंक्ति में मौजूद है for (int col = 0; col < N; col++) if (grid[row][col] == num) return true; return false; } bool isPresentInBox(int boxStartRow, int boxStartCol, int num){ //जांचें कि क्या num 3x3 बॉक्स में मौजूद है 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(){ //हल करने के बाद सुडोकू ग्रिड प्रिंट करें 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){ //खाली स्थान प्राप्त करें और पंक्ति और स्तंभ अपडेट करें for (row = 0; row < N; row++) for (col = 0; col < N; col++) if (grid[row][col] == 0) //0 के साथ खाली चिह्नित return true; return false; } bool isValidPlace(int row, int col, int num){ //जब आइटम कॉलम, पंक्ति और वर्तमान 3x3 बॉक्स में नहीं मिला 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; for(int num = 1; num <= 9; num++){ if(isValidPlace(row, col, num)){ grid[row][col] = num; if(solveSudoku()) return true; grid[row][col] = 0; } } return false; } int main(){ if(solveSudoku()) sudokuGrid(); else cout << "कोई समाधान मौजूद नहीं है"; } इनपुट
{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
