八皇后问题（回溯法）-蒲公英云

八皇后问题（回溯法）

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

问题描述

在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;
}