人工智能八皇后问题.doc-资料库

juanaryaza-4383988-4744302543320366925.doc.pdf-第1页.png

第1页 / 共15页

juanaryaza-4383988-4744302543320366925.doc.pdf-第2页.png

第2页 / 共15页

juanaryaza-4383988-4744302543320366925.doc.pdf-第3页.png

第3页 / 共15页

juanaryaza-4383988-4744302543320366925.doc.pdf-第4页.png

第4页 / 共15页

juanaryaza-4383988-4744302543320366925.doc.pdf-第5页.png

第5页 / 共15页

juanaryaza-4383988-4744302543320366925.doc.pdf-第6页.png

第6页 / 共15页

juanaryaza-4383988-4744302543320366925.doc.pdf-第7页.png

第7页 / 共15页

juanaryaza-4383988-4744302543320366925.doc.pdf-第8页.png

第8页 / 共15页

人工智能课程报告报告名称：八皇后问题班级：学号：姓指导老师：名

目录 1、需求分析 …………………………………… 1 2、设计（思想结构描述） ………………………… 1 3、实现过程 …………………………………… 4 4、测试 …………………………………………… 9 5、感想总结 …………………………………… 13

一、需求分析八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯 1850 年提出。在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在 8*8 的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。关于棋盘的绘制，因为棋盘的规格（n*n）是不确定的，显然不能根据规格的大小来确定棋盘的面积，所以我们首先划分出一个指定区域，用来绘制棋盘，这个正方形区域的边长大小为一个整型常量 board，单位为像素，这样就能轻易的计算出每个棋子格的大小，即我们自定义的单位长度，cell=board/n；在此有衍生出另外一个问题，board 不可能被所有的 n 整除，这样得到的 cell 可能会是一个无理数，在 C++语言中，处理浮点型数据时不能存储无理数，所以最好的方法是让 cell 为一个整数，这里使用一个技巧，board = board - board % n;这就将取整后的余数去掉了，在 Dialog 中，board%n 是很小的区域，不会引起视觉冲突；关于棋子的摆放，在绘制完棋盘之后，我们同样也获取了每个棋子位的坐标，落子的过程其实就是一个贴图的过程，在指定坐标的位置使用绘图函数绘出棋子，同样，取出棋子也是擦去棋子的图形。根据程序的设计要求，需要设计一个八皇后问题的演示程序，程序需要具备以下功能：能够快速查找并显示八皇后的布局方式有多少种正确方法；能够逐个查看每种布局的结果；能够逐步演示棋子在棋盘上的的行走过程，直到出现正确的结果；能够很方便的改变皇后个数即棋盘规格。要实现指定的功能，存在以下几个待解决的问题；根据指定的规格，即皇后个数，来画出相应规格的棋盘；能够在指定的位置摆放棋子和收回棋子；制定落子的顺序和规则，避免重复和遗漏；标记每步落子后不能落子的区域，即已有棋子的同行、同列和同一斜线上的位置。二、设计（思想结构描述）根据问题分析提供的解决方案，实现棋盘绘制和棋子摆放清除功能，可以选择的存储结构为线性存储结构，逻辑结构为图形结构，并构造一种新的数据结构 Queen Panel，定义在这个数据结构上的功能有，按提供的规格绘制棋盘，按指定的位置绘制棋子和清除棋子。实现主窗口和棋子摆放规则，可以选用线性存数结构和图形逻辑结构构造一个新的数据结构，定义在其上的功能为根据回溯法的规则改变*queen 中皇后位置，并将其传递给 Queen Panel 的对象，使其按要求实现棋子的摆放，直到出现正确的放置方法。 1

算法描述如下： A、数据初始化。 B、从 i 行开始摆放第 i 个皇后（因为这样便可以符合每一横行只有一个皇后的要求），先测试当前位置（i，j）是否等于 false（未被占领）。如果是，摆放第 1 个皇后，并宣布占领（竖列、斜列一起设置 mk[j]=true、rk[n+i-j]=true、lk[i+j]=true），记录该皇后的位置 queen[i]=j，并摆放棋子，接着进行递归；如果不是，测试下一个位置（i，j+1），但是如果当 i<=8， m=8 时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。 C、使用数组实现回溯法的思想。 D、当 i=8，j>=8 时，结束。如图 1 所示，从第 1 行开始，先将棋子摆在位置（1,1）上，然后依次每行的纵坐标为 3， 5，2，4，在第 5 行之后，由图 2 可以看出，已经没有地方可以继续落子了，这个时候，就要开始回溯了，由图 3 的树形就够可以看出，下面会取回第五行的棋子，并重新摆在 8 位置；依次下去，知道摆满 8 个棋子；图 3 显示的是一次完整的走棋过程，得到一种正确的放置方法：（1，1）,（2，5）,（3，8）,（4，6）,（5，3）,（6，7）,（7，2）,（8，4）。图 1 棋子摆放顺序示意图图 2 当前棋盘状态图 2

图 3 棋子摆放的树形示意图 3

三、实现过程 1）、流程图 4

2）、详细设计 class QueenPanel 继承自 MFC 标准类 CStatic，CStatic 类提供了一个 Windows 静态控件的性能。一个静态控件用来显示一个文本字符串，框，矩形，图标，光标，位图，或增强的图元文件。这里用来实现绘制棋盘的基础。一个静态控件不接收输入，也不提供输出；但是，如果它是用 SS_NOTIFY 风格创建的，则它可以通知其父有关设备点击的消息。衍生的成员变量 n 用来记录皇后的个数，因为 n 不确定，这里使用动态数组 int *queen 记录皇后在每行的位置，成员函数 DrawBoard（CDC *pDC, int size, int cell），用于绘制棋盘，OnPaint() 用于按位置绘制棋子，辅助成员函数 SetSize(int size)、SetQueen(int *newq)、 SetQueen(int row, int col)等用于初始化相应成员变量。（代码如下） class QueenPanel : public CStatic { // Construction public: QueenPanel(); QueenPanel(int size); // Attributes public: // Operations public: // Overrides // ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(QueenPanel) //}}AFX_VIRTUAL // Implementation public: virtual ~QueenPanel(); void SetSize(int size); void SetQueen(int *newq); void SetQueen(int row, int col); // Generated message map functions protected: //{{AFX_MSG(QueenPanel) afx_msg void OnPaint(); //}}AFX_MSG DECLARE_MESSAGE_MAP() private: void DrawBoard(CDC *pDC, int size, int cell); int *queen; int n; HANDLE queen_mutex; }; 5

class CEightQueenDlg 继承自类 MFC 的标准基类 CDialog，CDialog 类是在屏幕上显示的对话框基类。CEightQueenDlg 是本程序的对话框类，用于实现主对话框界面的实现，包括棋盘的初始化，界面中各按钮的功能，是程序的核心所在。成员变量*rk，*lk 和*mk 分别用与存储右上左下和左上右下斜线以及列中是否能够填棋子的标记，canceling、running、pausing 分别用于存储退出、开始、继续按钮是否被按下的标记；n 用于存储皇后个数，count 用于存储正确摆放结果的数目，*queen 记录每行的皇后位置；step、 no_int 分别记录暂停状态和连续状态；m_step、m_no_int 分别记录暂停和连续键是否被按下； pause_event 和 this_mutex 是两个事件对象，用于多线程操作； afx_msg void OnSysCommand(UINT nID, LPARAM lParam)、 afx_msg void OnPaint()、afx_msg HCURSOR OnQueryDragIcon()、 afx_msg void OnPause()、afx_msg void OnContinue()、afx_msg void OnClose()、afx_msg void OnStepBy()、afx_msg void OnAbout()、afx_msg void OnStop()、afx_msg void OnAuto()、afx_msg void OnNoInt()为一组消息映射函数，分别实现各按钮功能。（代码如下) class CEightQueenDlg : public CDialog { // Construction public: OnStart() 、 afx_msg void void UpdateUI(); CEightQueenDlg(CWnd* pParent = NULL); // standard constructor void WINAPI Go(); virtual void OnOK(); virtual void OnCancel(); // Dialog Data //{{AFX_DATA(CEightQueenDlg) enum { IDD = IDD_EIGHTQUEEN_DIALOG }; QueenPanel m_panel; //}}AFX_DATA // ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CEightQueenDlg) protected: virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support //}}AFX_VIRTUAL // Implementation protected: HICON m_hIcon; // Generated message map functions //{{AFX_MSG(CEightQueenDlg) virtual BOOL OnInitDialog(); afx_msg void OnSysCommand(UINT nID, LPARAM lParam); afx_msg void OnPaint(); afx_msg HCURSOR OnQueryDragIcon(); 6

资料库

人工智能八皇后问题.doc

相关推荐

课程资源

热门标签

最新资料