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

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

• हमें इस समस्या को हल करने के लिए 1 से 9 तक के अंकों का उपयोग करना होगा।
• एक अंक को एक पंक्ति, एक कॉलम या एक 3x3 बॉक्स में दोहराया नहीं जा सकता।

बैकट्रैकिंग एल्गोरिदम का उपयोग करके, हम सुडोकु समस्या को हल करने का प्रयास करेंगे। जब किसी सेल को एक अंक से भरा जाता है, तो यह जांचता है कि यह वैध है या नहीं। जब यह वैध नहीं होता है, तो यह अन्य नंबरों की जांच करता है। यदि 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%3, col - col%3, num) सभी false हैं, तो true वापस करें
• solveSudoku() नामक एक विधि परिभाषित करें, जो ग्रिड लेती है
• यदि ग्रिड में कोई स्थान खाली नहीं है, तो true वापस करें
• संख्या 1 से 9 तक के लिए, करें:
  • यदि isValidPlace(row, col, number), तो:
    • grid[row][col] := number
    • यदि solveSudoku == true, तो true वापस करें
    • grid[row][col] := 0
• false वापस करें

उदाहरण (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){ 
    for (int row = 0; row < N; row++) 
        if (grid[row][col] == num) 
            return true; 
    return false; 
} 
bool isPresentInRow(int row, int 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){ 
    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) 
                return true; 
    return false; 
} 
bool isValidPlace(int row, int col, int num){ 
    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() == 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