C++-এ Судোকু সলভার (Sudoku Solver)

ধরুন আমাদের কাছে একটি সুডোকু গ্রিড আছে এবং আমাদের এই বিখ্যাত সংখ্যা পাজল সমাধান করতে হবে। সুডোকু হল একটি 9x9 সংখ্যা গ্রিড, যা 3x3 বক্সগুলিতে ভাগ করা থাকে। সুডোকু সমাধানের কিছু নিয়ম রয়েছে:

• ১ থেকে ৯ পর্যন্ত অঙ্ক ব্যবহার করতে হবে।

• একটি অঙ্ক একই রো, কলাম বা 3x3 বক্সে পুনরাবৃত্তি হতে পারবে না।

ব্যাকট্র্যাকিং (backtracking) অ্যালগরিদম ব্যবহার করে আমরা সুডোকু সমাধান করব। যখন একটি সেলে অঙ্ক বসানো হয়, তখন এটি যাচাই করে যে এটি বৈধ কিনা। যদি বৈধ না হয়, তবে অন্য সংখ্যা চেষ্টা করা হয়। যদি ১-৯ সব সংখ্যা চেষ্টা করার পর কোনো বৈধ অঙ্ক না পাওয়া যায়, তবে এটি পिछले অপশনে ফিরে যায় (backtrack)।

ইনপুট ও আউটপুট চিত্রের মাধ্যমে দেখানো হয়েছে।

সমাধানের ধাপসমূহ:

• isPresentInCol(col, num) - কলামে num আছে কিনা যাচাই করুন

• isPresentInRow(row, num) - রোতে num আছে কিনা যাচাই করুন

• isPresentInBox(boxStartRow, boxStartCol, num) - 3x3 বক্সে num আছে কিনা যাচাই করুন

• findEmptyPlace(row, col) - খালি সেল খুঁজে বের করুন

• isValidPlace(row, col, num) - রো, কলাম ও বক্সে num না থাকলে true রিটার্ন করুন

• solveSudoku() - যদি কোনো খালি জায়গা না থাকে তবে true রিটার্ন করুন। ১ থেকে ৯ পর্যন্ত লুপ চালিয়ে isValidPlace চেক করুন, বৈধ হলে বসিয়ে রিকারসিভ কল করুন, না হলে ০ করে দিন।

উদাহরণ (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"; 
    return 0;
}

ইনপুট

{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