八皇后问题 ( C++ ) ( 递归 )-蒲公英云

八皇后问题 ( C++ ) ( 递归 )

梦里梦外; 2022-05-21 10:11 266阅读 0赞

#include<iostream>  //八皇后问题递归方法
using namespace std;
int ways = 0;
int a[8] = { -1,-1,-1,-1,-1,-1,-1,-1 };
bool check(int row, int col) {     // 在row行，col列可以放置皇后吗？
    for (int i = 0; i < row; i++)  // 判断同列、对角线是否有皇后冲突
        if (a[i] == col || row - i == col - a[i] || row - i == a[i] - col)
            return false;          // 返回0表示不能放，有冲突
    return true;
}
void place(int n) {
    if (n == 8) {                  // 递归函数的出口，从0到7行都已经放置完毕，
        ways++;                    // 并且都是正确的，所以当n=8的时候，方案数加1
        for (int i = 0; i < 8; i++)
            cout << a[i] << "  ";  // 输出结果
        cout << "\n-----------------------\n";
        return;
    }
    else {
        for (int i = 0; i < 8; i++)
            if (check(n, i)) {
                a[n] = i;          // 如果该行可以放的话，就放
                place(n + 1);      // 放好之后，放下一行
            }                      // 如果后几行全放完了，或者下一行没地方放，
                                   // 就返回这一层for循环，重新把这一行往下一列放，此处就是回溯
    }
}
int main() {
    place(0); cout << ways << endl;
    return 0;
}