数据结构课程实践.doc

课程实践数据结构课程设计报告学校:哈尔滨理工大学学院：管理学院专业：信息管理与信息系统姓名：苏雅班级：信管112学号：1106040213N皇后问题一、设计要求与分析 1.设计要求在一个n*n的棋盘上放置n个皇后，要求放置的n个皇后不会互相吃掉；皇后棋子可以吃掉它所在的那一行、那一列，以及那两条对角线上的任何棋子。 2设计分析此问题由八皇后问题演变而来，是八皇后问题的升级版，你可以随意输入一个比4大的数字，本程序将自动求出相关的某皇后问题。回溯算法是尝试搜索算法中最为基本的一种算法，并采用了一种“走不通就掉头”的思想，当发现已不满足求解条件时，就“回溯”返回，尝试跌的路径。解决8皇后的算法有多种，其中加约束条件的枚举算法拥有最好的可读性，也能从中体会到回溯的思想，但是它职能解决皇后“个数为常量”的问题，却不能解决任意的n皇后问题，因此也不是典型的回溯算法模型。非递归算法可以说是典型的回溯算法模型但是对于回溯算法，更方便的是用递归控制方式实现，用这种方法可以解决任意的n皇后问题。算法思想同样实现用深度优先搜索，并在不满足约束条件时及时回溯二、算法求精这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第i个皇后占领了第j列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。/*-回溯法-*/ static： 避免命名有冲突/棋盘初始化时，空格的地方为+，放置皇后的地方为?static char Queen2020; static int a20; /数组ai：ai表示第i个皇后放置的列,i的范围：-8static int b40; /主对角线数组static int c40; /从对角线数组，根据程序的运行，去决定主从对角线是否放入皇后static int iQueenNum=0; /记录总的棋盘状态数static int Num=1;int n;void iQueen(int row); /参数i代表行void location() int row; /横行int cow; /纵行 for(row=0;rown;row+) arow=0; /列标记初始化，表示无列冲突 for(cow=0;cown;cow+) Queenrowcow=+; for(row=0;row2*n;row+) /主、从对角线标记初始化，表示没有冲突brow=crow=0; iQueen(0);void iQueen(int row) /row为当前处理的行 int cow; for(cow=0;cown;cow+) if(acow=0&brow-cow+n-1=0&crow+cow=0) /如果无冲突 Queenrowcow=?; /放皇后acow=1; /标记，下一次该列上不能放皇后 brow-cow+n-1=1; /标记，下一次该主对角线上不能放皇后 crow+cow=1; /标记，下一次该从对角线上不能放皇后if(rown-1) iQueen(row+1); /如果行还没有遍历(沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问)完，进入下一行else /否则输出 int row; /棋盘状态int cow；coutn个皇后摆放位置的第Num种情况为：endl; for(row=0;rown;row+) /棋盘的输出 for(cow=0;cown;cow+) coutsetw(2)Queenrowcow; coutendl; cout皇后位置坐标: ; /坐标的输出 for(row=0;rown;row+) for(cow=0;cown;cow+) if(Queenrowcow=?)cout(row+1,cow+1); coutendl;Num+;coutendl;n皇后问题解的情况N=1 X=(1)N=2 无解N=3 无解N=4 X1=(2,4,1,3);X2=(3,1,4,2)N=5 X1=(1,3,5,2,4);X2=(1,4,2,5,3);X3=(2,4,1,3,5);X4=(2,5,3,1,4)；X5=(3,1,4,2,5);X6=(3,5,2,4,1);X7=(4,1,3,5,2);X8=(4,2,5,3,1)；X9=(5,2,4,1,3);X10=(5,3,1,4,2)N=6 X1=(2,4,6,1,3,5);X2=(3,6,2,5,1,4);X3=(4,1,5,2,6,3);X4=(5,3,1,6,4,2)N=7 40个解N=8 92个解三、完整的算法实现#include/数据流输入/输出#include/参数化输入/输出#include/定义杂项函数及内存分配函数#include/定义输入/输出函数/*-回溯法-*/ static： 避免命名有冲突/棋盘初始化时，空格的地方为+，放置皇后的地方为?static char Queen2020; static int a20; /数组ai：ai表示第i个皇后放置的列,i的范围：-8static int b40; /主对角线数组static int c40; /从对角线数组，根据程序的运行，去决定主从对角线是否放入皇后static int iQueenNum=0; /记录总的棋盘状态数static int Num=1;int n;void iQueen(int row); /参数i代表行void location() int row; /横行int cow; /纵行 for(row=0;rown;row+) arow=0; /列标记初始化，表示无列冲突 for(cow=0;cown;cow+) Queenrowcow=+; for(row=0;row2*n;row+) /主、从对角线标记初始化，表示没有冲突brow=crow=0; iQueen(0);void iQueen(int row) /row为当前处理的行 int cow; for(cow=0;cown;cow+) if(acow=0&brow-cow+n-1=0&crow+cow=0) /如果无冲突 Queenrowcow=?; /放皇后acow=1; /标记，下一次该列上不能放皇后 brow-cow+n-1=1; /标记，下一次该主对角线上不能放皇后 crow+cow=1; /标记，下一次该从对角线上不能放皇后if(rown-1) iQueen(row+1); /如果行还没有遍历(沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问)完，进入下一行else /否则输出 int row; /棋盘状态int cow; coutn个皇后摆放位置的第Num种情况为：endl; for(row=0;rown;row+) /棋盘的输出 for(cow=0;cown;cow+) coutsetw(2)Queenrowcow; coutendl; cout皇后位置坐标: ; /坐标的输出 for(row=0;rown;row+) for(cow=0;cown;cow+) if(Queenrowcow=?)cout(row+1,cow+1); coutendl;Num+;coutendl;/如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重新标记Queenrowcow=+; acow=0; brow-cow+n-1=0; crow+cow=0; / if endsvoid show() /输出界面 system(cls);coutendl;coutt *n皇后问题实验设计* endl;coutt *endl;coutt * n皇后问题 * endl;coutt * * endl;coutt * * endl;coutt * 1. 回溯算法 0.退出 * endl;coutt * * endl;coutt * * endl;coutt * 请选择 1或者0 * endl; coutt * endl;coutt * endl;int main()/主函数 system(color 5E); for(;) A: show(); cout