八皇后问题（回溯法）

小灰灰 2022-06-05 12:20 207阅读 0赞

**问题描述**

![70][]

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上（与水平行轴成45°或135°），问有多少种摆放方案？

**思路**

从第一行第一列开始，

1）考虑当前第row行第col列这个位置，要判断当前位置是否可存放

2）若不可存放则考虑这一行的下一列，返回1）

3）若可存放，则记录。然后判断当前是否为最后一行，是则说明找到一种方案并输出

3）若不是最后一行，则考虑下一行，返回1），直到判断完所有的方案

仔细分析可知，要实现所有方案的判断，就应该需要回溯地一层一层地判断，这里借用递归的方法来实现回溯的过程。

具体判断位置和输出方案的做法见代码。

#include<iostream>
    using namespace std;
    
    static int QueenLocation[8] = { 0 };    //QueenLocation[i]=j 表示第i行皇后的位置在第j列
    static int gCount = 0;                  //记录所有方案数目
    
    void print()                            //输出一种可行方案
    {
        for (int row = 0; row < 8; row++)
        {
            for (int col = 0; col < QueenLocation[row]; col++)
                cout << "0";
                cout <<"#";
            for (col = QueenLocation[row] + 1; col < 8; col++)
                cout << "0";
            cout << endl;
        }
        cout << "==========================\n";
    }
    int check_pos_valid(int row, int col)   //检查该位置是否可存放
    {
        int location;
        for (int i = 0; i < row; i++)       //已存放的皇后对第row行第col列这个位置的影响
        {
            location = QueenLocation[i];
            if (col == location)
                return 0;                   //同列
            if ((i + location) == (row + col) ||
                (i - location) == (row - col))
                return 0;                   //同一斜线（135°或者45°）
                                            //注意，由于是递归地每一行考虑，不会出现同行的情况
        }
        return 1;                           //可存放
    }
    void eight_queen(int row)               //考虑第row行皇后的存放
    {
        for (int col = 0; col < 8; col++)   //考虑第row行第col列是否可存放
        {
            if (check_pos_valid(row, col))  //返回1表示该位置可存放
            {
                QueenLocation[row] = col;   //在第row行第col列置放一个皇后
                if (7 == row)               //找到一个完整的方案
                {
                    gCount++; print();      //记数并输出这个方案
                    QueenLocation[row] = 0;
                    return;                 //开始回溯
                }
                eight_queen(row + 1);       //递归地考虑下一行
                QueenLocation[row] = 0;     //初始化该值以不影响回溯时的判断
            }
        }
    }
    int main(int argc, char*argv[])
    {
        eight_queen(0);
        cout << "total=" << gCount << endl;
        return 0;
    }

本文借鉴于百度百科。

[70]: /images/20220605/12605d4724804b19b3078ec7106127c2.png