วาง K-Knights ให้ไม่โจมตีกันใน C++

ในปัญหานี้ เราได้รับค่าจำนวนเต็มสามค่า K, N, M งานของเราคือวาง K กวาด (knights) ในกระดานหมากรุก NxM ให้ไม่มีกวาดสองตัวโจมตีกัน มีกรณีที่มี 0 วิธีที่ถูกต้อง และกรณีที่มีหลายวิธีที่ถูกต้อง คุณต้องพิมพ์กรณีที่ถูกต้องทั้งหมด

Knight (กวาด) เป็นชิ้นหมากรุกที่เคลื่อนที่สองก้าวไปข้างหน้าแล้วหนึ่งก้าวซ้ายหรือขวา สามารถเคลื่อนที่ในทิศทางใดก็ได้บนกระดานหมากรุก

Attack (การโจมตี) คือตำแหน่งที่ชิ้นหนึ่งสามารถอยู่ในตำแหน่งเดียวกับชิ้นอื่นในโอกาสหนึ่งของการเคลื่อนที่ที่ถูกต้องของมัน

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

Input - M = 3, N = 3, K = 5

Output -

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

เพื่อแก้ปัญหานี้ เราจะเริ่มวางกวาดทีละตัวในแต่ละแถว คอลัมน์ต่อคอลัมน์ และตรวจสอบตำแหน่งที่โจมตีหลังการวางแต่ละครั้ง ในการวางกวาด เราจะตรวจสอบว่าปลอดภัยหรือไม่ หากปลอดภัย เราจะวางมันแล้วไปยังตำแหน่งถัดไป เราจะใช้ backtracking เพื่อให้ได้วิธีที่เป็นไปได้ทั้งหมด และสำหรับสิ่งนี้ เราจะสร้างบอร์ดใหม่หลังการวางกวาดแต่ละครั้งเพื่อ backtracking นี่คือวิธีที่เราจะได้โซลูชันที่เป็นไปได้ทั้งหมดโดยใช้ backtracking

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

#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