C++-এ K-নাইট বসানো যাতে তারা একে অপরকে আক্রমণ না করতে পারে

এই সমস্যাতে, তিনটি পূর্ণসংখ্যা K, N, M দেওয়া আছে। আমাদের কাজ হলো NxM চেসবোর্ডে K সংখ্যক নাইট বসানো যাতে কোনো দুটি নাইট একে অপরকে আক্রমণ না করতে পারে। কেস ০ ভ্যালিড ভেতে পারে এবং একাধিক ভ্যালিড ভেতেও পারে। সব ভ্যালিড কেস প্রিন্ট করতে হবে।

নাইট হলো একটি চেস পিস যা দুটি ঘর আগে যাওয়ার পর এক ঘর বাম বা ডানে যেতে পারে। এটি চেসবোর্ডে যেকোনো দিকে যেতে পারে।

আক্রমণ হলো এমন পজিশন যেখানে একটি পিস এক চालেই অন্য পিসের জায়গায় যেতে পারে।

উদাহরণ:

ইনপুট - M = 3, N = 3, K = 5

আউটপুট -

K A K A K A K A K A K A K K K A K A

সমাধানের জন্য, আমরা প্রতিটি সারি, কলাম কলামে নাইট বসাব। প্রতিটি বসানোর পর আক্রমণ করা পজিশনগুলো চেক করব। নাইট বসানোর সময় চেক করব সেফ কিনা। যদি সেফ হয়, তবে বসিয়ে পরবর্তী পজিশনে যাব। ব্যাকট্র্যাকিং ব্যবহার করে সব সম্ভাব্য উপায় বের করব। প্রতিটি নাইট বসানোর পর ব্যাকট্র্যাকিং-এর জন্য নতুন বোর্ড তৈরি করব।

উদাহরণ

সমাধানের প্রোগ্রাম:

#include <iostream> 
using namespace std; 

int m, n, k, count = 0;

void displayPositions(char** board) {
    cout << endl;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++)
            cout << board[i][j] << "\t";
        cout << endl;
    }
}

void canattack(int i, int j, char a, char** board) {
    if ((i + 2) < m && (j - 1) >= 0) board[i + 2][j - 1] = a;
    if ((i - 2) >= 0 && (j - 1) >= 0) board[i - 2][j - 1] = a;
    if ((i + 2) < m && (j + 1) < n) board[i + 2][j + 1] = a;
    if ((i - 2) >= 0 && (j + 1) < n) board[i - 2][j + 1] = a;
    if ((i + 1) < m && (j + 2) < n) board[i + 1][j + 2] = a;
    if ((i - 1) >= 0 && (j + 2) < n) board[i - 1][j + 2] = a;
    if ((i + 1) < m && (j - 2) >= 0) board[i + 1][j - 2] = a;
    if ((i - 1) >= 0 && (j - 2) >= 0) board[i - 1][j - 2] = a;
}

bool canPlace(int i, int j, char** board) {
    if (board[i][j] == '_')
        return true;
    else
        return false;
}

void place(int i, int j, char k, char a, char** board, char** new_board) {
    for (int y = 0; y < m; y++)
        for (int z = 0; z < n; z++)
            new_board[y][z] = board[y][z];
    new_board[i][j] = k;
    canattack(i, j, a, new_board);
}

void placeKnights(int k, int sti, int stj, char** board) {
    if (k == 0) {
        displayPositions(board);
        count++;
    } else {
        for (int i = sti; i < m; i++) {
            for (int j = stj; j < n; j++) {
                if (canPlace(i, j, board)) {
                    char** new_board = new char*[m];
                    for (int x = 0; x < m; x++)
                        new_board[x] = new char[n];
                    place(i, j, 'K', 'A', board, new_board);
                    placeKnights(k - 1, i, j, new_board);
                }
            }
            stj = 0;
        }
    }
}

int main() {
    m = 3, n = 3, k = 5;
    char** board = new char*[m];
    for (int i = 0; i < m; i++)
        board[i] = new char[n];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = '_';
    cout << "The ways in which " << k << " knights can be placed in " << m << "x" << n << " chessboard are :\n";
    placeKnights(k, 0, 0, board);
    return 0;
}

আউটপুট

The ways in which 5 knights can be placed in 3x3 chessboard are : K A K A K A K A K A K A K K K A K A

এখানে, নাইটের পজিশন K এবং আক্রমণ করা পজিশন A দিয়ে চিহ্নিত করা হয়েছে।