(C++)八皇后问题

一、实验目的、内容

在8行8列的棋盘上放置8个皇后，使任一个皇后都不能吃掉其他的7个皇后，并将结果以某种方式显示出来。

二、实验程序设计及结构

1.需求分析

采用回溯算法。

变量

数组linenum(unsigned char[8])表示特定列的皇后要放的行位置，a(unsigned char)的第i位表示第i行上已经有皇后，b(unsigned short)的第i位表示第i条主对角线上已经有皇后，c(unsigned short)的第i位表示第i条副对角线上已经有皇后；c(char)表示用户的选择。

函数

递归函数void solve(unsigned char r, bool& f)，递归算法void f1()，非递归算法void f2()，主函数int main()。

2.设计结构或流程图

递归

1. 根据r判断要处理的linenum位置并用p标记。
2. p从1到8寻找可放置的位置。
3. 若放置成功则++r并寻找下一位；否则返回寻找上一个皇后的下一个可行位置。
4. 不断递归直至r等于8并输出。

非递归

与递归类似，将形参r改为循环变量，将标记p改为指针用于操作数组。

三、设计过程

#include <iostream>
using namespace std;
unsigned char linenum[8], a;
// 若用bool数组会造成内存空间浪费，采用无符号整型及位运算来节省空间
unsigned short b, c;
void solve(unsigned char r, bool &f)
{
    unsigned char &p = linenum[r - 1];
    p = 1;
    while (a >> p - 1 & 1 || b >> r + p - 2 & 1 || c >> r - p + 7 & 1) // 循环条件为是否不可放置
    F:
        if (++p > 8)
        {
            f = false;
            return;
        }
    a += 1 << p - 1;
    b += 1u << r + p - 2;
    c += 1u << r - p + 7;
    f = true;
    if (r < 8)
        solve(r + 1, f); // 如果当前方案不可行，回溯到上一步
    // 递归后仍然没有放置皇后，进入循环寻找下一个位置
    if (!f)
    {
        a -= 1 << p - 1;
        b -= 1u << r + p - 2;
        c -= 1u << r - p + 7;
        goto F;
    }
}
// 递归
void f1()
{
    // 若用-1(各位数全是1)初始化，就需要在solve函数中用非运算，效率较低
    a = b = c = 0;
    bool f;
    solve(1, f);
    for (signed char i = 0; i < 8; ++i)
    {
        for (signed char j = 0; j < 8; ++j)
            if (linenum[j] == i + 1) // 该位置有皇后
                cout << "Q ";
            else
                cout << "+ ";
        cout << endl;
    }
}
// 非递归，过程类似于递归
void f2()
{
    a = b = c = 0;
    unsigned char *p = linenum - 1, r = 1;
    do // 把递归改为一重循环
    {
        *++p = 1;
        while (a >> *p - 1 & 1 || b >> r + *p - 2 & 1 || c >> r - *p + 7 & 1)
            while (++*p > 8)
            {
                a -= 1 << *--p - 1;
                b -= 1u << --r + *p - 2;
                c -= 1u << r - *p + 7;
            }
        a += 1 << *p - 1;
        b += 1u << r + *p - 2;
        c += 1u << r - *p + 7;
    } while (++r < 9);
    for (signed char i = 0; i < 8; ++i)
    {
        for (r = 0; r < 8; ++r)
            if (linenum[r] == i + 1)
                cout << "Q ";
            else
                cout << "+ ";
        cout << endl;
    }
}
int main()
{
    char c;
F:
    cout << "请选择计算方式:\nA.递归\tB.非递归\n";
    cin >> c;
    switch (c)
    {
    case 'A':
        f1();
        break;
    case 'B':
        f2();
        break;
    default:
        cout << "输入错误!\n请重新输入!\n";
        goto F;
    }
    system("pause");
    return 0;
}

四、测试分析

递归

非递归

五、设计的特点和结果

采用了回溯算法，较穷举法大大提高了效率。由于递归效率较低，故又写了非递归的程序。

结果：输出了八皇后问题的第一种情况。