还剩7页未读,继续阅读
文本内容:
——课程实践数据结构课程设计报告学校:哈尔滨理工大学学院管理学院专业信息管理与信息系统姓名苏雅班级信管11——2学号1106040213N皇后问题
一、设计要求与分析.设计要求1在一个的棋盘上放置个皇后,要求放置的个皇后不会互相n*n nn吃掉;皇后棋子可以吃掉它所在的那一行、那一列,以及那两条对角线上的任何棋子设计分析2此问题由八皇后问题演变而来,是八皇后问题的升级版,你可以随意输入一个比大的数字,本程序将自动求出相关的某皇后问题回溯4算法是尝试搜索算法中最为基本的一种算法,并采用了一种“走不通就掉头”的思想,当发现已不满足求解条件时,就“回溯”返回,尝试跌的路径解决皇后的算法有多种,其中加约束条件的枚举算法拥有最8好的可读性,也能从中体味到回溯的思想,但是它职能解决皇后“个数为常量”的问题,却不能解决任意的皇后问题,因此也不是典型的回n溯算法模型非递归算法可以说是典型的回溯算法模型但是对于回溯算法,更方便的是用递归控制方式实现,用这种方法可以解决任意的皇n后问题算法思想同样实现用深度优先搜索,并在不满足约束条件时及时回溯
二、算法求精这个问题包括了行,歹两条对角线;J,列规定每一列放一个皇后,不会造成列上的冲突;行当第行被某个皇后占领后,则同一行上的所有空格都不能再放皇后,i要把以为下标的标记置为被占领状态;i对角线对角线有两个方向在这我把这两条对角线称为主对角线和从对角线在同一对角线上的所有点设下标为⑶,要末是常数,i+j要末是常数因此,当第个皇后占领了第列后,要同时把以、i-j ij i+j川为下标的标记置为被占领状态r-------------------------回溯法--------------------------*/避免命名有冲突//static〃棋盘初始化时,空格的地方为+,放置皇后的地方为?static charQueen
[20]
[20];〃数组表示第个皇后放置的列的范围static inta
[20];a[i]a[i]i,i—8〃主对角线数组static intb
[40];〃从对角线数组,根据程序的运行,去决定主从对角线是static intc
[40];否放入皇后〃记录总的棋盘状态数static intiQueenNum=O;static intNum=l;int n;〃参数代表行void iQueenfint row;ivoid location〃横行int row;〃纵行int cow;forrow=0;row n;row++〃列标记初始化,表示无列冲突a[row]=0;forcow=0;cown;cow++Queen[row][cow]=,+,;}〃主、从对角线标记初始化,表示没有fo r row=0;row2*n;row++冲突b[row]=c[row]=0;iQueenO;;〃为当前处理的行void iQueenint row rowint cow;forcow=0;cown;cow++〃如果无冲ifa[cow]==0b[row-cow+n-l]==0c[row+cow]==0突〃放皇后Queen[row][cow]=;〃标记,下一次该列上不能放皇后a[cow]=l;〃标记,下一次该主对角线上不能放皇b[row-cow+n-l]=l;后〃标记,下一次该从对角线上不c[row+cow]=l;能放皇后ifrown-l〃如果行还没有遍历沿着某iQueenrow+l;条搜索路线,挨次对树中每一个结点均做一次且仅做一次访问完,进入下一行〃否则输出else〃棋盘状态int row;;int cow个皇后摆放位置的第种情况为coutn«endl;〃棋盘的输出forrow=0;row n;row++forcow=0;cown;cow++cout«setw2«Queen[row][cow];cout«endl;皇后位置坐标“”;〃坐标的输出cout”forrow=0;rown;row++forcow=0;cown;cow++ifQueen[row][cow]==,1cout«endl;Num++;cout«endl;}皇后问题解的情况nN=1X=l无解N=2无解N=3;N=4Xl=2,44,3X2=3,1,47;N=5Xl=l,3,5,2,4;X2=l,4,2,5,3;X3=24,l,3,5;X4=25,3,l,4//;;;X5=3,1,425X6=3,5,241X7=4,l,3,5,2;X8=4,2,5,3,l;X9=5,2A1,3X1O=5,3,1A2N=6Xl=2,4,6l,3,5;X2=3,6,25,l,4;X3=4,l,52,63;X4=5,3,l,6/////4,2个解N=740个解N=892
三、完整的算法实现〃数据流输入/输出#includeiostream.h〃参数化输入/输出#includeiomanip.h〃定义杂项函数及内存分配函数#includestdlib.h〃定义输入/输出函数#includestdio.h/*------------------------回溯法--------------------------*/避免命名有冲突//static〃棋盘初始化时,空格的地方为+,放置皇后的地方为?static charQueen
[20]
[20];〃数组表示第个皇后放置的列,的范围static inta
[20];a[i]a[i]i i—8〃主对角线数组static intb
[40];〃从对角线数组,根据程序的运行,去决定主从对角static intc
[40];线是否放入皇后〃记录总的棋盘状态数static intiQueenNum=O;static intNum=l;int n;〃参数代表行void iQueenintrow;ivoid location〃横行introw;〃纵行int cow;forrow=0;rown;row++〃列标记初始化,表示无列冲突a[row]=0;forcow=0;cown;cow++Queen[row][cow]=,+,;、i、一〃主、从对角线标记初始化,表示fo rrow=0;row2*n;row++没有冲突b[row]=c[row]=0;iQueenO;;}_为当前处理的行void iQueenintrow//rowint cow;forcow=0;cown;cow++{〃如果无冲ifa[cow]==0b[row-cow+n-l]==0c[row+cow]==0突Queen[row][cow]=,1;〃放皇后〃标记,下一次该列上不能放皇后a[cow]=l;〃标记,下一次该主对角线上不b[row-cow+n-l]=l;能放皇后〃标记,下一次该从对角线上不能放皇后c[row+cow]=l;ifrown-l〃如果行还没有遍历沿着某iQueenrow+l;条搜索路线,挨次对树中每一个结点均做一次且仅做一次访问完,进入下一行〃否则输出else〃棋盘状态introw;intcow;个皇后摆放位置的第种情况为:coutvvnvv Numv«endl;f orro〃棋盘的输出w=0;ro wn;ro w++forcow=0;cown;cow++cout«setw2«Queen[row][cow];cout«endl;皇后位置坐标““”;〃坐标的输出COUt”forrow=0;rown;row++forcow=0;cown;cow++{,ifQueen[row][cow]==,f cout«,,,;«row+l«,,,«cow+l«,,Ncout«endl;Num++;cout«endl;〃如果前次的皇后放置导致后面的放置无论如何都不能满足要求,则回溯,重新标记Queen[row][cow]=,+,;a[cow]=0;b[row-cow+n-l]=0;c[row+cow]=0;}//if ends〃输出界面void show;{systemcls”cout«endl;coutl,\t,,«M**************n问^当佥-计***********M«endl;cout«,,\t,l«,1cout«,,\t,,«,1n皇后问题it«endl;cout«\t««endl;itcout«,,\t,,«ii«endl;cout«,,\t,,«
1.回溯算法
0.退出II木木”*力”》***»»*”***本A»***”endl;«endl;IIIIcout«,,\t,,«II«endl;IIcout«,,\t,,«II请选择1或者o«endl;IIcout«\t««endl;IIM«endl;■cout«\t«*****************************************,,«endl;〃主函数int main{systemHcolor5EH;for;;{A:show;cout«endl;int number;cin»number;switchnumber case0:exit0;case1:system,lclsM;输入皇后个数个数大于cout”4cin»n;location;system—pause;goto A;default:选择错误,请重新作出选择!“〈〈coukv”endl;systemCpause11;goto A;}return0;
四、结果截图■C:\Uws\Adm屈stratorXDes ktopVl电后向室程序设计自我设计\N皇后可皇后|可超立登设计皇后问题**n・«W M回溯算法.退出««
1.gw w*请选择或者*1以的棋盘为例10*10个皇后摆放位置的第加种情况为1•2♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦皇后位置坐标1,10X2,5X3,7X4,4X5,1X6,3X
7.9X8,6X9,810,2个皇后摆放位置的第种情况为.1703♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦••••••・•皇后位置坐标1,10X
2.5X3,7X4,4X
5.16,8,28,99,610,3个皇后摆放位置的笫种情况为1«17M♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦皇后位置坐标,乂》⑶《》《」》《》《九・》《》
11.2*6155-26337316-3个皇后摆放位置的第种情况为,♦♦♦♦♦♦♦♦♦1”5♦♦♦♦♦♦♦♦♦。