Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में K-नाइट्स रखें ताकि वे एक-दूसरे पर हमला न करें


इस समस्या में, हमें तीन पूर्णांक मान K, N, M दिए गए हैं। हमारा कार्य NxM शतरंज बोर्ड पर K नाइट्स रखना है ताकि कोई दो नाइट्स एक-दूसरे पर हमला न करें। 0 वैध तरीकों के मामले हो सकते हैं और कई वैध तरीकों के मामले भी हो सकते हैं। आपको सभी वैध मामले प्रिंट करने होंगे।

नाइट शतरंज का एक मोहरा है जो दो चाल आगे और फिर एक चाल बाएं या दाएं चलता है। यह शतरंज बोर्ड पर किसी भी दिशा में चल सकता है।

हमला वह स्थिति है जब एक मोहरा अपने वैध चालों में एक चाल में दूसरे मोहरे की जगह पर पहुंच सकता है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट - 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 << "वे तरीके जिनमें " << k << " नाइट्स को " << m << "x" << n << " शतरंज बोर्ड में रखा जा सकता है :\n";
    placeKnights(k, 0, 0, board);
    return 0;
}

आउटपुट

वे तरीके जिनमें 5 नाइट्स को 3x3 शतरंज बोर्ड में रखा जा सकता है :
K A K A K A K A K A K A K K K A K A

यहां, हमने नाइट्स की स्थितियों को K से और उन स्थितियों को जहां वे हमला करते हैं A से चिह्नित किया है।

  1. - C++ में सरणी में उन सभी जोड़े (a, b) को खोजें जैसे कि a % b = k

    मान लीजिए हमारे पास एक सरणी A है, उस सरणी से हमें सभी जोड़े (a, b) प्राप्त करने हैं जैसे कि a%b = k। मान लीजिए सरणी A = [2, 3, 4, 5, 7], और k = 3, तो जोड़े हैं (7, 4), (3, 4), (3, 5), (3, 7)। इसे हल करने के लिए, हम सूची को पार करेंगे और जांचेंगे कि दी गई शर्त पूरी हो रही है या नहीं। उदाहरण #include

  1. - C++ में A में N अंक जोड़ें ताकि प्रत्येक जोड़ के बाद यह B से विभाज्य हो

    यहां हम देखेंगे कि N अंकों को A के साथ जोड़कर एक संख्या कैसे उत्पन्न की जाए, और प्रत्येक चरण में नए अंक जोड़ते समय यह दूसरी संख्या B से विभाज्य हो। मान लीजिए हम 4 अतिरिक्त अंक जोड़कर एक 5-अंकीय संख्या बनाने जा रहे हैं। हम 7 से विभाज्यता की जांच करेंगे। संख्या 8 से शुरू होगी। तो पहले यह 4 को जोड़ेगा

  1. पायथन में n रूक को व्यवस्थित करने के तरीकों की संख्या खोजने का प्रोग्राम ताकि वे एक-दूसरे पर हमला न कर सकें पायथन में n रूक को व्यवस्थित करने के तरीकों की संख्या खोजने का प्रोग्राम ताकि वे एक-दूसरे पर हमला न कर सकें

    मान लीजिए हमारे पास एक संख्या n है जो n x n आकार के शतरंज बोर्ड को दर्शाती है। हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम n रूक रख सकते हैं, ताकि वे एक-दूसरे पर हमला न कर सकें। यहां दो तरीकों को अलग माना जाएगा यदि एक तरीके में शतरंज बोर्ड का कोई सेल भरा है, और दूसरे तरीके में वह सेल खाली है। (हम ज