Đặt K con mã không tấn công nhau trên bàn cờ NxM trong C++

Trong bài toán này, chúng ta được cho ba giá trị nguyên K, N, M. Nhiệm vụ là đặt K con mã (knight) trên bàn cờ NxM sao cho không có hai con mã nào tấn công nhau. Có thể có trường hợp 0 cách hợp lệ và cũng có trường hợp nhiều cách hợp lệ. Bạn cần in ra tất cả các cách hợp lệ.

Mã (Knight) là quân cờ di chuyển hai ô theo một hướng và một ô vuông góc. Nó có thể di chuyển theo mọi hướng trên bàn cờ.

Tấn công (Attack) là vị trí khi một quân có thể đến ô của quân khác trong một nước đi hợp lệ.

Ví dụ minh họa:

Đầu vào - M = 3, N = 3, K = 5

Kết quả -

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

Để giải bài toán, chúng ta sẽ đặt các con mã lần lượt theo từng hàng, cột bởi cột. Và kiểm tra các vị trí bị tấn công sau mỗi lần đặt. Khi đặt mã, kiểm tra xem có an toàn không. Nếu an toàn, đặt nó và chuyển sang vị trí tiếp theo. Sử dụng backtracking (quay lui) để có được tất cả các cách có thể, tạo bàn cờ mới sau mỗi lần đặt để backtracking. Như vậy sẽ thu được tất cả các giải pháp bằng backtracking.

Chương trình minh họ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 << "Các cách đặt " << k << " con mã trên bàn cờ " << m << "x" << n << " là:\n"; 
    placeKnights(k, 0, 0, board); 
    return 0; 
}

Kết quả

Các cách đặt 5 con mã trên bàn cờ 3x3 là: K A K A K A K A K A K A K K K A K A

Ở đây, vị trí con mã được đánh dấu bằng K và vị trí bị tấn công bằng A.