Cara menggunakan algoritma Eight Queens Problem dalam C++

Cara menggunakan algoritma masalah lapan ratu dalam C++

Masalah lapan ratu adalah masalah algoritma klasik yang memerlukan meletakkan lapan ratu pada papan catur 8x8 supaya tiada dua ratu boleh menyerang antara satu sama lain, iaitu mana-mana dua Ratu tidak boleh berada dalam baris, lajur atau pepenjuru yang sama. Terdapat banyak algoritma untuk menyelesaikan Masalah Eight Queens, salah satu kaedah yang biasa digunakan ialah menggunakan algoritma backtracking. Artikel ini akan memperkenalkan cara menggunakan bahasa C++ untuk melaksanakan algoritma Masalah Lapan Ratu dan memberikan contoh kod khusus.

Pertama, kita perlu mentakrifkan papan catur 8x8, yang diwakili oleh tatasusunan dua dimensi. Setiap elemen tatasusunan boleh mewakili grid papan catur, 1 bermakna terdapat ratu pada grid, 0 bermakna tiada ratu.

Seterusnya, kami mentakrifkan fungsi rekursif untuk melalui setiap baris papan dan cuba meletakkan ratu. Langkah-langkah khusus adalah seperti berikut:

1. Jika anda telah melintasi barisan terakhir papan catur, ini bermakna anda telah menemui penyelesaian, simpan keadaan papan catur semasa, dan kembali.
2. Lintas setiap grid dalam baris semasa dan cuba letakkan ratu.
3. Jika grid semasa tidak memenuhi syarat untuk meletakkan ratu (iaitu, ia bercanggah dengan ratu yang telah diletakkan), grid semasa akan dilangkau dan grid seterusnya akan terus dilalui.
4. Jika grid semasa memenuhi syarat untuk meletakkan ratu, letakkan ratu pada grid dan tandakan grid sebagai diduduki.
5. Panggil fungsi secara rekursif dan lintasi baris seterusnya.
6. Jika hasil panggilan rekursif kembali benar, bermakna penyelesaian telah ditemui, maka penyelesaian akan disimpan dan benar akan dikembalikan.
7. Jika hasil panggilan rekursif kembali palsu, ini bermakna penempatan grid semasa tidak memenuhi keperluan penyelesaian, kemudian alih keluar ratu pada grid dan kembali ke langkah sebelumnya.

Berdasarkan idea di atas, kita boleh melaksanakan kod berikut:

#include <iostream>
#include <vector>

using namespace std;

const int n = 8;  // 棋盘大小

// 棋盘
int chessboard[n][n];

// 保存解法的容器
vector<vector<int>> solutions;

// 检查当前格子上是否可以放置皇后
bool isValid(int row, int col) {
    // 检查同一列上是否有皇后
    for (int i = 0; i < row; i++) {
        if (chessboard[i][col] == 1)
            return false;
    }
    
    // 检查左上对角线上是否有皇后
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 1)
            return false;
    }
    
    // 检查右上对角线上是否有皇后
    for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 1)
            return false;
    }
    
    return true;
}

// 解决八皇后问题的递归函数
bool solveNQueens(int row) {
    // 如果已经遍历到最后一行，表示找到了一种解法，将当前棋盘状态保存下来
    if (row == n) {
        vector<int> solution;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (chessboard[i][j] == 1)
                    solution.push_back(j);
            }
        }
        solutions.push_back(solution);
        return true;
    }

    // 遍历当前行的每一个格子，尝试放置皇后
    for (int col = 0; col < n; col++) {
        // 如果当前格子满足放置皇后的条件，标记该格子为已占用
        if (isValid(row, col)) {
            chessboard[row][col] = 1;

            // 递归调用函数，遍历下一行
            solveNQueens(row + 1);

            // 如果递归调用的结果返回false，表示当前格子的放置方式不满足解法要求，回溯到上一步
            chessboard[row][col] = 0;
        }
    }

    return false;
}

// 打印解法
void printSolutions() {
    for (auto solution : solutions) {
        cout << "Solution:" << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == solution[i])
                    cout << "Q ";
                else
                    cout << ". ";
            }
            cout << endl;
        }
        cout << endl;
    }
}

int main() {
    solveNQueens(0);
    printSolutions();
    return 0;
}

Jalankan program ini dan semua penyelesaian akan dikeluarkan. Setiap penyelesaian dipaparkan dalam bentuk papan dam, di mana Q mewakili ratu dan . Dengan algoritma ini, kami boleh mencari semua penyelesaian kepada Masalah Lapan Ratu.

Saya harap artikel ini akan membantu anda memahami cara menggunakan algoritma Eight Queens Problem dalam C++. Melaksanakan algoritma ini memerlukan penggunaan idea rekursi dan penjejakan ke belakang Selagi anda mengikut langkah yang betul, anda boleh mencari penyelesaian kepada Masalah Lapan Ratu.

Atas ialah kandungan terperinci Cara menggunakan algoritma Eight Queens Problem dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!