当前位置:首页 > 开发语言/框架 > C++

经典算法-8皇后有关问题的C++实现

优良自学吧提供经典算法-8皇后有关问题的C++实现,经典算法---8皇后问题的C++实现其实8皇后问题,很好理解,8X8的棋盘上面,放8只皇后,使他们之间不会相互攻击,具体的定义,渊源可以查看百度百科八皇后问题 本科时候学数据结构的时候就接触过这个经典算法,不过当时没怎么听明白,或者说知道是个回溯的思想,却不知道

经典算法---8皇后问题的C++实现

其实8皇后问题,很好理解,8X8的棋盘上面,放8只皇后,使他们之间不会相互攻击,具体的定义,渊源可以查看百度百科八皇后问题

本科时候学数据结构的时候就接触过这个经典算法,不过当时没怎么听明白,或者说知道是个回溯的思想,却不知道该怎么实现,原谅我只是个小白。今天上振动力学的时候,闲着没事突然想到了这个问题,顺手写下了伪代码,到实验室调试一下,基本就出来了。

调试过程中遇到了两个bug,在代码中已经注明了(这里标记下,方便自己以后能方便找到重点)
1.退出条件中有个等号
2.需要恢复现场

另外
1.算法相对应的数据结构实际上是一个1维数组,存储每行所选取的列标号。
2.其实我们将其写成了N皇后问题,也就是说通过修改 构造参数,我们可以实现 其他n个皇后问题的求解。
3.网上看到有用二维数组实现的,就顺便拿过来了
算法学习笔记之三:八皇后问题(递归、回溯)
4.还看到一篇和我用的方法相似的,也拿过来
经典算法(1)——8皇后问题求解(回溯法)
感觉虽然有很多注释,不过还是不太容易看明白,不过话说大家看我的代码兴许也是这样吧。23333333333333

运行结果图:
运行结果图

代码如下:

// ----------------------【NQueen.h】-------------------
#pragma once
class CNQueen
{
public:
    CNQueen();
    CNQueen(int num);
    ~CNQueen();

public:
    void SolveResult();

private:
    bool IsOK(int row, int col);
    void output();
    bool init(int num);
    void TraceBack(int CurRow);

private:
    int m_num;
    int * m_RowSelect;

    int m_solution_num;
};

// ------------------------【NQueen.cpp】----------------------------
#include "NQueen.h"
#include <cstdio>
#include <string>


bool CNQueen::init(int num)
{
    m_solution_num = 0;

    m_RowSelect = new int[m_num];
    memset(m_RowSelect, 0, sizeof(m_RowSelect));

    return true;
}

CNQueen::CNQueen(int num) :m_num(num)
{
    init(m_num);
}


CNQueen::~CNQueen()
{
    if (m_RowSelect)
        delete [] m_RowSelect;
}

// ---------------------------------【回溯求解】----------------------------
void CNQueen::TraceBack(int CurRow)
{
    // 这里需要有个 等号操作,我说怎么死活没结果
    if (CurRow >= m_num)
    {
        m_solution_num++;
        output();       
        return;
    }

    for (int j = 0; j != m_num; j++)
    {
        m_RowSelect[CurRow] = j;
        if (IsOK(CurRow, j))
        {
            CurRow++;
            TraceBack(CurRow);  
            CurRow--;               // 恢复现场
        }           
    }


}

// ---------------------------------【剪枝函数】----------------------------
bool CNQueen::IsOK(int row, int col)
{
    for (int k = 0; k != row; k++)
    {
        if (col == m_RowSelect[k])    // 列
            return false;

        if (row - k == col - m_RowSelect[k])  // 斜线
            return false;

        if (row - k == m_RowSelect[k] - col)
            return false;
    }

    return true;
}

// ---------------------------------【显示 解的分布 】----------------------------
void CNQueen::output()
{   
    FILE * fd = NULL;

    if (m_solution_num == 1)
    {
        fd = fopen("output.txt", "wt");
        fprintf(fd, "-----------------------------%d皇后问题求解-----------------------------------\n",
            m_num);
    }
    else
        fd = fopen("output.txt", "at+");


    fprintf(fd, "找到第%d组可行解\n", m_solution_num);
    for (int i = 0; i != m_num; i++)
    {
        for (int j = 0; j != m_num; j++)
        {
            if (m_RowSelect[i] == j)
                fprintf(fd, "\tQ");
            else
                fprintf(fd, "\t*");
        }
        fprintf(fd, "\n");
    }
    fclose(fd);
    //system("pause");
}

// ---------------------------------【求解 并显示在屏幕上】----------------------------
void CNQueen::SolveResult()
{
    TraceBack(0);

    if (m_solution_num == 0)
        fprintf(stdout, "无解\n");
    else
        fprintf(stdout, "找到%d组解,放在output.txt文件中\n", m_solution_num);
}
// ---------------------------------【八皇后问题 main.cpp】----------------------------
//  @   author          :       zhyh2010
//  @   date            :       20150519
//  @   description     :       主要基于回溯的思想, C++ 实现
//  @   version         :       1.0
// ---------------------------------【八皇后问题 end】----------------------------

#include "NQueen.h"
#include <windows.h>

int main(int arg, char ** argv)
{
    CNQueen instance(2);
    instance.SolveResult();
    system("pause");
    return 0;
}

(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢