C++-এ ৮ সংখ্যা গ্রিডে শর্ত মেনে রাখা বসান

মান লিজিয়ে ১ থেকে ৮ সংখ্যাগুলো দেওয়া চিত্রের আটটি বৃত্তে বসাতে হবে এমনভাবে যাতে কোনো সংখ্যা তার পরের সংখ্যার পাশে না থাকে।

ইনপুট:

আউটপুট:

সমাধানের ধাপগুলো:

• N := 3, M := 4
• NOTCONSIDERED := -1
• present_in_grid() ফাংশন: grid[N][M], num নিয়ে সার্চ করুন
• isSafe() ফাংশন: grid, row, col, num নিয়ে প্রতিটি সেলের জন্য আলাদা শর্ত চেক করুন (প্রতিটি সেলের আশেপাশের সেলের সাথে পার্থক্য ১-এর চেয়ে বড় কিনা)
• search_free_location() ফাংশন: খালি সেল খুঁজুন
• Solve() ফাংশন: ব্যাকট্র্যাকিং দিয়ে সমাধান করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশন দেখুন:

#include <cmath> 
#include <iostream> 
#define N 3 
#define M 4 
#define NOTCONSIDERED -1 
using namespace std; 

bool present_in_grid(int grid[N][M], int num) { 
    for (int i = 0; i < N; i++) 
        for (int j = 0; j < M; j++) 
            if (grid[i][j] == num) 
                return true; 
    return false; 
} 

bool isSafe(int grid[N][M], int row, int col, int num) { 
    // প্রতিটি সেলের জন্য আলাদা শর্ত চেক করা হয়েছে 
    if (row == 0 && col == 1) { 
        if (present_in_grid(grid, num) || abs(num - grid[row][col + 1]) <= 1 || abs(num - grid[row + 1][col]) <= 1 || abs(num - grid[row + 1][col - 1]) <= 1 || abs(num - grid[row + 1][col + 1]) <= 1) 
            return false; 
    } 
    else if (row == 0 && col == 2) { 
        if (present_in_grid(grid, num) || abs(num - grid[row][col - 1]) <= 1 || abs(num - grid[row + 1][col]) <= 1 || abs(num - grid[row + 1][col + 1]) <= 1 || abs(num - grid[row + 1][col - 1]) <= 1) 
            return false; 
    } 
    else if (row == 1 && col == 0) { 
        if (present_in_grid(grid, num) || abs(num - grid[row - 1][col + 1]) <= 1 || abs(num - grid[row][col + 1]) <= 1 || abs(num - grid[row + 1][col + 1]) <= 1) 
            return false; 
    } 
    else if (row == 1 && col == 3) { 
        if (present_in_grid(grid, num) || abs(num - grid[row - 1][col - 1]) <= 1 || abs(num - grid[row][col - 1]) <= 1 || abs(num - grid[row + 1][col - 1]) <= 1) 
            return false; 
    } 
    else if (row == 2 && col == 1) { 
        if (present_in_grid(grid, num) || abs(num - grid[row - 1][col - 1]) <= 1 || abs(num - grid[row - 1][col]) <= 1 || abs(num - grid[row - 1][col + 1]) <= 1 || abs(num - grid[row][col + 1]) <= 1) 
            return false; 
    } 
    else if (row == 2 && col == 2) { 
        if (present_in_grid(grid, num) || abs(num - grid[row][col - 1]) <= 1 || abs(num - grid[row - 1][col]) <= 1 || abs(num - grid[row - 1][col + 1]) <= 1 || abs(num - grid[row - 1][col - 1]) <= 1) 
            return false; 
    } 
    else if (row == 1 && col == 1) { 
        if (present_in_grid(grid, num) || abs(num - grid[row][col - 1]) <= 1 || abs(num - grid[row - 1][col]) <= 1 || abs(num - grid[row - 1][col + 1]) <= 1 || abs(num - grid[row][col + 1]) <= 1 || abs(num - grid[row + 1][col + 1]) <= 1 || abs(num - grid[row + 1][col]) <= 1) 
            return false; 
    } 
    else if (row == 1 && col == 2) { 
        if (present_in_grid(grid, num) || abs(num - grid[row][col - 1]) <= 1 || abs(num - grid[row - 1][col]) <= 1 || abs(num - grid[row + 1][col - 1]) <= 1 || abs(num - grid[row][col + 1]) <= 1 || abs(num - grid[row - 1][col - 1]) <= 1 || abs(num - grid[row + 1][col]) <= 1) 
            return false; 
    } 
    return true; 
} 

bool search_free_location(int grid[N][M], int& row, int& col) { 
    for (row = 0; row < N; row++) 
        for (col = 0; col < M; col++) 
            if (grid[row][col] == NOTCONSIDERED) 
                return true; 
    return false; 
} 

void show_res(int grid[N][M]) { 
    for (int i = 0; i < N; i++) { 
        if (i == 0 || i == N - 1) 
            cout << " "; 
        for (int j = 0; j < M; j++) { 
            if (grid[i][j] == 0) 
                cout << " "; 
            else 
                cout << grid[i][j] << " "; 
        } 
        cout << endl; 
    } 
} 

bool Solve(int grid[N][M]) { 
    int row, col; 
    if (!search_free_location(grid, row, col)) 
        return true; 
    for (int num = 1; num <= 8; num++) { 
        if (isSafe(grid, row, col, num)) { 
            grid[row][col] = num; 
            if (Solve(grid)) 
                return true; 
            grid[row][col] = NOTCONSIDERED; 
        } 
    } 
    return false; 
} 

int main(){ 
    int grid[N][M] = { { 0, -1, -1, 0 }, 
                       { -1, -1, -1, -1 }, 
                       { 0, -1, -1, 0 } }; 
    if (Solve(grid)) 
        show_res(grid); 
    else 
        cout << "Not possible"; 
}

ইনপুট

{ { 0, -1, -1, 0 }, { -1, -1, -1, -1}, { 0, -1, -1, 0 }}

আউটপুট

 3 5 7 1 8 2 4 6