算法设计与分析——幻方的解决——广度优先搜索

算法设计与分析——幻方的解决——广度优先搜索

引用

CSDN

1.

https://blog.csdn.net/Blackoutdragon/article/details/116464069

幻方是一种古老的数学游戏，要求将1到n²的数字填入n×n的矩阵中，使得每一行、每一列以及两条对角线上的数字之和都相等。本文将介绍如何使用广度优先搜索算法来解决幻方问题。

幻方的基本描述

通常幻方由1到n²的连续整数组成，其中n为正方形的行数或者列数。因此n阶幻方有n行n列，填充的数字是1到n²的连续整数。每行每列以及对角线的等于一个常数，其结果为：

以三阶幻方为例，其填充的数字是从1到9，每行每列和对角线等于15.

广度优先搜索算法

思路分析

• 使用队列去实现对于问题状态广度遍历，队列中保存的是对应问题的不同解的状态
• 使用什么去表示问题的解的不同的状态？每一次都申请一个一维矩阵，这会不会出现空间溢出？
• 既然暂时不知道，那就只能先试试看，每一次遍历都要将原来的问题状态的以为矩阵清空，然后其生成的子状态加入到队列中。

实现源码

在把所有能剪的枝都减了的情况下，只能跑出来三阶，到了四阶就出现了内存炸裂

#include<iostream>
#include<queue>
//确定文件的输入
#include<fstream>
using namespace std;
//定义问题的具体的阶数
int grade;
//幻方每一行或者每一列相等的目标
int target;
//定义一个目标函数保存最终的结果的一维数组指针
int* goal = NULL;
//判定是否符合当前的状态，是否已经在被使用
bool *use;
//在函数的外部声明一个全局变量，用来保存对应的参数
queue<int*> broad;
//打开文件的读写
ofstream fout("path.txt");
/*
    描述：输出问题状态，直接输出到文件流中
*/
void showFile(int* temp) {
    for (int i = 1; i <= (grade * grade); ++i)
    {
        fout << temp[i];
        if (temp[i] <= 9)	fout << "     ";
        else if (temp[i] <= 99) fout << "    ";
        else fout << "   ";
        if (i % grade == 0)	fout << endl;
    }
}
/*
    描述：输出问题状态，输出到控制台
*/
void show(int* temp) {
    for (int i = 1; i <= (grade * grade); ++i)
    {
        cout << temp[i];
        if (temp[i] <= 9)	cout << "     ";
        else if (temp[i] <= 99) cout << "    ";
        else cout << "   ";
        if (i % grade == 0)	cout << endl;
    }
}
/*
    描述：判定传入的问题状态是否合法，进而判定的进行剪枝
    参数：一维数组头指针
    返回：传入的问题状态是否符合对应的条件
*/
bool judge(int* temp) {
    //如果已经填好了行，就对行进行判定
    int sum = 0;
    //如果没有超过第一层，就不会遍历第一行
    for (int i = 1; i <= temp[0] / grade; i += grade)
    {
        sum = temp[i];
        for (int j = 1; j < grade; ++j)
        {
            sum += temp[i + j];
        }
        //判定是否相等
        if (sum != target) return false;
    }
    //如果已经填好了列，就对列进行判定
    if (temp[0] > grade * (grade - 1)) {
        for (int i = grade * (grade - 1) + 1; i <= temp[0]; ++i)
        {
            sum = temp[i];
            for (int j = i - grade; j > 0; j -= grade)
            {
                sum += temp[j];
            }
            //判定是否相等
            if (sum != target)	return false;
        }
    }
    //判定斜线累加是否等于target
    //由右上到左下的对角线
    if (temp[0] >= grade * (grade - 1) + 1) {
        sum = temp[grade * (grade - 1) + 1];
        //这里很容易出错，最后一行减去一个值是在第一行的第一个，没有出现换行的情况
        for (int i = grade * (grade - 2) + 2; i >= 2; i -= (grade - 1))
            sum += temp[i];
        //判定是否相等
        if (sum != target)
            return false;
    }
    //由左上角到右下角
    if (temp[0] == grade * grade) {
        sum = temp[grade * grade];
        for (int i = (grade * (grade - 1) - 1); i >= 1; i -= (grade + 1))
            sum += temp[i];
        //判定是否相等
        if (sum != target)
            return false;
    }
    return true;
}
void broadSearch() {
    int constNum = grade * grade + 1;
    //声明一个临时的数组指针，用来保存对应指针
    int* temp, * temp1;
    //应该加入第一层队列
    for (int i = 1 ;i <= constNum-1; ++i)
    {
        //编号是从1开始的，一直到最后一个
        //0号元素是保存当前问题状态的层数
        temp = new int[constNum];
        memset(temp, 0, sizeof(int) * (constNum));
        temp[1] = i;
        temp[0] = 1;
        broad.push(temp);
    }
    //开始进行遍历
    while (!broad.empty()) {
        bool flag = false;
        //返回队首的指针，获取队列中的第一个元素，即第一个问题状态
        temp = broad.front();
        broad.pop();
        
        //往下遍历一层，第一个元素问题层数增加
        temp[0]++;
        //初始化use数组，然后再逐个遍历其中的每一个元素，一遍下一步进行广度的递归
        memset(use, 1, sizeof(bool) * (constNum));
        for (int i = 1; i < temp[0]; ++i)
        {
            use[temp[i]] = false;
        }
        //开始遍历获取下一层问题状态的同一水平线的所有子集
        for (int i = 1; i < constNum; ++i)
        {
            //如果当前的元素没有使用，就添加
            if (use[i])
            {
                //如果当前的数字并没有使用的，就先填入原来得数组，并判定是否合法
                temp[temp[0]] = i;
                //fout << "第" << temp[0] << "层遍历：" << endl;
                //show(temp);
                if (judge(temp)) {
                    //fout << "当前这个是符合条件的" << endl;
                    //判定当前的数组是否已经到达目标状态
                    if (temp[0] == constNum-1)
                    {
                        goal = temp;
                        //获取目标直接跳出循环，删除对应原先申请的空间，直接退出
                        flag = true;
                        break;
                    }
                    //声明一个新的数组,并将原来的数组复制进去
                    temp1 = new int[constNum];
                    memcpy(temp1, temp, sizeof(int) * (constNum));
                    //将合法得问题状态，复制到对应得队列中
                    broad.emplace(temp1);
                }
            }
        }
        if (flag) break;
        //已经遍历完毕，直接退出，并删除原来的数组
        delete temp;
    }
    //遍历队列中的每一个元素，获取第一个目标的数组
    while (!broad.empty()) {
        //获取队列中的每一个申请的空间，然后删除即可
        temp = broad.front();
        broad.pop();
        delete temp;
    }
    return;
}
int main1(int argc, char const* argv[])
{
    fout << "test" << endl;
    
    //grade = 3;
    //target = grade * (grade * grade + 1) / 2;
    //int temp[10] = {9 ,4,9,2,3,5,7,8,1,6 };
    //cout << judge(temp) << endl;
    cout << "请输入幻方的阶数" << endl;
    fout << "请输入幻方的阶数" << endl;
    cin >> grade;
    fout << grade << endl;
    //生成的对应的一维数组记录的每一个数据得访问情况
    use = new bool[grade*grade+1];
    //更新计算的目标数值
    target = grade * (grade * grade + 1) / 2;
    broadSearch();
    //遍历其中最终的目标数组
    fout << "最终的结果是" << endl;
    //showFile(goal);
    show(goal);
    cin >> grade;
    
    fout.close();
    //声明一个一维数组，是初始状态的一维数组
    return 0;
}