实现n皇后问题的多种解法

叁歲伎倆 2022-12-17 08:47 80阅读 0赞

一、问题定义  
将n个皇后放置在 n ∗ n n\*n n∗n的棋盘上，要求任意2个皇后，满足：  
①不在同一行  
②不在同一列  
③不在同一对角线

1.常规问题：求合法放置的方案总数以及输出每种方案(回溯法 + 全排列枚举(递归实现))  
2.另一类问题：前k行随机放置，后 n − k n-k n−k行用回溯法，求k为多少时，首次成功耗时最短。

二、常规问题1  
1.回溯法  
(1)思路  
①当前行为i，从j = 1 to n进行试探(i表示行号，j表示列号)

if ((!col.count(j)) && (!diag45.count(i + j)) && (!diag135.count(i - j)))

> col为列号的集合，!col.count(j)表示不在同一列  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center]  
> 如上图，可发现：  
> 同一45°对角线(逆时针方向)，i + j相同，比如：4 + 1 = 3 + 2  
> 故!diag45.count(i + j)表示不在同一45°对角线上；  
> 同一135°对角线(逆时针方向)，i - j相同，比如：1 - 1 = 2 - 2  
> 故!diag135.count(i - j)表示不在同一135°对角线上；

②如果当前行，找到合法位置，则放置皇后，处理下一行  
![在这里插入图片描述][20201023133208310.png_pic_center]

③如果当前行，未找到合法位置，则回退到上一行，处理下一列  
![在这里插入图片描述][20201023133219149.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center 1]  
(2)完整代码如下：

#include <cstdio>
    #include <set>
    #include <vector>
    using namespace std;
    //回溯法
    
    void Print(int N, vector<int> placeResult, int ans) {
        
        printf("第%d种放置方案：\n", ans);
        for(int i = 1; i <= N; i++) {
        
            for(int j = 1; j <= N; j++) {
        
                if(j == placeResult[i]) printf("√");
                else printf("×");
                if(j != N) printf(" ");
                else printf("\n");
            }
        }
        printf("\n");
    }
    
    int Erase(int &i, set<int> &col, set<int> &diag45, set<int> &diag135, vector<int> &placeResult) {
        
        i--;
        int k = placeResult[i];  //上一行皇后所在的列；
        placeResult[i] = 0;
        col.erase(k);
        diag45.erase(i + k);
        diag135.erase(i - k);
        return k + 1; //试探下一列；
    }
    
    void Backtracking(int N, int i, set<int> &col, set<int> &diag45, set<int> &diag135, vector<int> &placeResult, int &ans) {
        
        //回溯过程；
        int j = 1; //第1列；
        int startL = i;     
        while(i <= N && i >= startL) {
        
            while(j <= N) {
        
                //判断是否不同列，不在同一45°对角线，不在同一135°对角线
                if ((!col.count(j)) && (!diag45.count(i + j)) && (!diag135.count(i - j))){
        
                   //可放置皇后
                   placeResult[i] = j;
                   col.insert(j);
                   diag45.insert(i + j);
                   diag135.insert(i - j);
    
                   //处理下一行
                   i++;
                   j = 1;
                   break;
                }
                j++;
            }
    
            if(j > N) {
        
                //处理上一行
                j = Erase(i, col, diag45, diag135, placeResult);
            }
    
            //传统的N皇后问题，输出合法放置的方案个数以及每种方案详情
            if(i == N + 1) {
        
                //合法放置
                ans++;
                Print(N, placeResult, ans);
                j = Erase(i, col, diag45, diag135, placeResult);
            }
        }
    }
    
    int main() {
        
        //测试回溯法
        int N = 8, ans = 0;
        vector<int> placeResult(N + 1);
        set<int> col, diag45, diag135;
        col.clear(); diag45.clear(); diag135.clear();
    
        Backtracking(N, 1, col, diag45, diag135, placeResult, ans);
        printf("有%d种放置可能", ans);
        return 0;
    }

(3)运行结果(部分截图)：  
![在这里插入图片描述][20201023133454219.png_pic_left]  
2.全排列枚举(递归实现)  
(1)思路  
数组P\[n + 1\], 表示n个数(1~n)的全排列，则保证了任意2个皇后不同行也不同列。  
所以，只需验证任意2个皇后不在同一对角线上即可。  
(2)采用递归实现(减治的思想)，代码如下：

//FP: Full Permutation
    #include <cstdio>
    #include <vector>
    #include <cmath>
    using namespace std;
    
    void generateP(vector<int> &P, vector<bool> &isLegal, int n, int &ans, int index) {
        
        if(index == n + 1) {
        
            ans++;
            return;
        }
        //i表示列
        for (int i = 1; i <= n; i++) {
        
            if(!isLegal[i]) {
        
                //验证该列的合法性
                bool flag = true;
                for (int pre = 1; pre < index; pre++) {
        
                    if(abs(index - pre) == abs(i - P[pre])) {
        
                        flag = false;
                        break;
                    }
                }
                if(flag) {
        
                    //该列合法
                    P[index] = i;
                    isLegal[i] = true;
                    generateP(P, isLegal, n, ans, index + 1);
                    isLegal[i] = false;
                }
            }
        }
    }
    
    int main() {
        
        int n = 8;
        vector<int> p(n + 1);
        vector<bool> isLegal(n + 1);
        int ans = 0;
        generateP(p, isLegal, n, ans, 1);
        printf("有%d种放置可能\n", ans);
        return 0;
    }

(3)运行结果：  
![在这里插入图片描述][20201023140410347.png_pic_left]  
三、另一类问题  
(1)Las Vegas思想：前stepVegas行采用随机放置皇后，剩余行采用回溯法2

bool QueenLV(int N, set<int> &col, set<int> &diag45, set<int> &diag135, vector<int> &placeResult, int stepVegas) {
        
        int i = 1; //从第i行到第stepVegas行进行随机放置
        int LP = 0; //LP = Legal Place, 当前行可能放置的合法位置；
        srand((unsigned)time(0));
        bool result = false;
        while(i <= stepVegas) //随机放置的皇后数
        {
        
            LP = 0;
            vector<int> effectivePos;//记录当前行可以放置的皇后位置
            for (int j = 1; j <= N; j++) {
        
                if ((!col.count(j)) && (!diag45.count(i + j)) && (!diag135.count(i - j))) {
        
                    LP++;
                    effectivePos.push_back(j);
                }
            }
            if(LP > 0) {
        
                int pos = rand() % LP;
                int k = effectivePos[pos];
                //放置皇后
                placeResult[i] = k;
                Insert(i, col, diag45, diag135, placeResult);
            }
            else if(LP == 0) {
        
                return false;
            }
        }
        if(LP > 0 || stepVegas == 0) {
        
            result = Backtracking(N, i, col, diag45, diag135, placeResult);
        }
        return result;
    }

(2)完整代码3：

//实现n皇后问题的多种解法
    #include <cstdio>
    #include <set>
    #include <vector>
    #include <ctime>
    #include <random>
    using namespace std;
    //回溯法
    
    void Insert(int &i, set<int> &col, set<int> &diag45, set<int> &diag135, vector<int> &placeResult) {
        
        //placeResult[i] = k;
        int k = placeResult[i];
        col.insert(k);
        diag45.insert(i + k);
        diag135.insert(i - k);
        i++;
    }
    
    int Erase(int &i, set<int> &col, set<int> &diag45, set<int> &diag135, vector<int> &placeResult) {
        
        i--;
        int k = placeResult[i];  //上一行皇后所在的列；
        placeResult[i] = 0;
        col.erase(k);
        diag45.erase(i + k);
        diag135.erase(i - k);
        return k + 1; //试探下一列；
    }
    
    //回溯直到成功一次
    bool Backtracking(int N, int i, set<int> &col, set<int> &diag45, set<int> &diag135, vector<int> &placeResult) {
        
        //回溯过程；
        int j = 1; //第1列；
        int startL = i;      
        while(i <= N && i >= startL) {
        
            while(j <= N) {
        
                //判断是否不同列，不在同一45°对角线，不在同一135°对角线
                if ((!col.count(j)) && (!diag45.count(i + j)) && (!diag135.count(i - j))){
        
                   //可放置皇后
                   placeResult[i] = j;
                   Insert(i, col, diag45, diag135, placeResult);
                   //处理下一行
                   j = 1;
                   break;
                }
                j++;
            }
            if(j > N) {
        
                //回溯到上一行，试探下一列
                j = Erase(i, col, diag45, diag135, placeResult);
            }
        }
        //回溯结束条件
        bool success = false;
        if(i == N + 1)
            success = true;
        return success;
    }
    
    bool QueenLV(int N, set<int> &col, set<int> &diag45, set<int> &diag135, vector<int> &placeResult, int stepVegas) {
        
        int i = 1; //从第i行到第stepVegas行进行随机放置
        int LP = 0; //LP = Legal Place, 当前行可能放置的合法位置；
        srand((unsigned)time(0));
        bool result = false;
        while(i <= stepVegas) //随机放置的皇后数
        {
        
            LP = 0;
            vector<int> effectivePos;//记录当前行可以放置的皇后位置
            for (int j = 1; j <= N; j++) {
        
                if ((!col.count(j)) && (!diag45.count(i + j)) && (!diag135.count(i - j))) {
        
                    LP++;
                    effectivePos.push_back(j);
                }
            }
            if(LP > 0) {
        
                int pos = rand() % LP;
                int k = effectivePos[pos];
                //放置皇后
                placeResult[i] = k;
                Insert(i, col, diag45, diag135, placeResult);
            }
            else if(LP == 0) {
        
                return false;
            }
        }
        if(LP > 0 || stepVegas == 0) {
        
            result = Backtracking(N, i, col, diag45, diag135, placeResult);
        }
        return result;
    }
    
    int main() {
        
        for (int N = 12; N <= 20; N++) {
        
            vector<int> placeResult(N + 1);
            set<int> col, diag45, diag135;
            col.clear(); diag45.clear(); diag135.clear();
            clock_t start, finish;
            double duration = 0.0;
            for (int stepVegas = 0; stepVegas <= N; stepVegas++) {
        
                int failSum = 0; //首次成功前的失败总数
                //首次成功，试验10000次
                int loop1 = 10000;
                int loop2 = loop1;
                start = clock();
                while(loop1--) {
        
                    bool success = false;
                    while(!success) {
        
                        col.clear(); diag45.clear(); diag135.clear();
                        success = QueenLV(N, col, diag45, diag135, placeResult, stepVegas);
                        if(success == false)
                            failSum++;
                    }
                }
                finish = clock();
                //取平均
                duration = (double)(finish - start) / CLOCKS_PER_SEC;
                failSum /= loop2;
    
                //输出结果
                printf("当N = %d时：\n", N);
                printf("StepVegas = %d, 试验10000次取平均后，首次成功前的失败总数：%d, 首次成功所需的时间：%f\n", stepVegas, failSum, duration); 
            }
            printf("\n");
        }
            return 0;
    }

(3)运行结果(部分截图)：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center 2]  
结论：一般stepVegas略小于 N 2 \\frac\{N\}\{2\} 2N，效果较好。但这不意味着，stepVegas取其他值效果不好，比如上图中，取13 >  17 2 \\frac\{17\}\{2\} 217，效果反而最好。  
不过，随机放置前若干行，都比纯回溯方法要好。

四、扩展阅读

--------------------

1.  [验证N皇后合法方案总数][N] ↩︎
2.  [概率算法实现八皇后问题-cpp][-cpp] ↩︎
3.  [计算运行时间的写法：clock\_t][clock_t] ↩︎

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/4e2b1f2eb9cf4e38aa89e0a885c75132.png
[20201023133208310.png_pic_center]: /images/20221122/52f0c59f20704cecba7e34f239da150f.png
[20201023133219149.png_pic_center]: /images/20221122/e78102fb76474c11a8f28314557b6392.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221122/66fff948de4241059e01b30a697f3aa2.png
[20201023133454219.png_pic_left]: /images/20221122/9a2364718b844b2786badc4902f07ca9.png
[20201023140410347.png_pic_left]: /images/20221122/e594661d4f494dd58129d8f6e64e5e19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221122/f53b52123ed54a46995925bf06c3975c.png
[N]: https://blog.csdn.net/qinghezhen/article/details/17849837
[-cpp]: https://www.cnblogs.com/Alexkk/p/12778774.html
[clock_t]: https://blog.csdn.net/zx3517288/article/details/50553965/