8皇后问题的解法

冷不防 2022-05-09 17:52 125阅读 0赞

# 传统办法-回溯法 #

#include<iostream>
    #include<math.h>
    using namespace std;
    
    int n=8;
    int total=0;
    int *c=new int(n);
    
    bool is_ok(int row){
        for(int j=0;j!=row;j++){
            if(c[row]==c[j] || row-c[row]==j-c[j] || row+c[row]==j+c[j])
                return false;
        }
        return true;
    }
    
    void queen(int row){
        if(row==n)
            total++;
        else
            for(int col=0;col!=n;col++){
                c[row]=col;
                if(is_ok(row))
                    queen(row+1);
            }       
    }
    
    int main(){
        queen(0);
        cout<<total<<endl;
        return 1;
    }

# 新版方法 #

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    using  namespace std;
    
    
    void  N_Queue(vector<int> colum_index, vector<vector<int>>& result, int start);
    
    int main()
    {
        int n;
        cin >> n;
        vector<int> colum_index;
        for (int i = 0; i < n; ++i) {
            colum_index.push_back(i);
        }
        vector<vector<int>> res;
        N_Queue(colum_index, res, 0);
        cout << res.size() << endl;
        return 0;
    }
    
    void  N_Queue(vector<int> colum_index, vector<vector<int>>& result, int start)
    {
        if (start == colum_index.size() - 1)
        {
            bool res = true;
            for (int i = 0; i < colum_index.size(); i++)
            {
                for (int j = i + 1; j < colum_index.size(); ++j) {
                    if (i - j == colum_index[i] - colum_index[j] || i - j == colum_index[j] - colum_index[i])
                    {
                        res = false;
                        break;
                    }
                }
                if (!res)
                {
                    break;
                }
            }
            if (res)
            {
                result.push_back(colum_index);
            }
        } else{
            for (int i = start; i < colum_index.size(); i++)
            {
                swap(colum_index[i], colum_index[start]);
                N_Queue(colum_index, result, start + 1);
                swap(colum_index[i], colum_index[start]);
            }
        }
    }

# 参考 #

[回溯法][Link 1]  
[排列法][Link 2]

[Link 1]: https://www.cnblogs.com/bigmoyan/p/4521683.html
[Link 2]: https://blog.csdn.net/qq_34784753/article/details/80058521