算法实验 八皇后问题

《算法实验 八皇后问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、姓名：+++学号：090610213班级：0904103实验题目：八皇后问题问题分析：要在8*8的国际象棋棋盘中放8个皇后，是任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。解决问题的关键为怎样取到8个位置，判断他们符合要求。数学模型：每一行中只能取到一个位置，这样问题的解空间就是8个皇后所在的列的序号。1）通过8重循环从每一行中取得一个位置，检验取到的检验8个位置不在同一列、同一对角线。2）按深度优先的思想，从第一个皇后开始搜索，确定一个位置后，在搜索第二个皇后的位置……；每前进一步检查是否满足约束条件，不满足时，用continu

2、e语句回溯到上一个皇后，继续尝试下一位置；满足约束条件时，开始搜索下一位置，知道找到问题解。约束条件：不在同一列的表达式xi!=xj不在同一对角线上的约束条件abs(xi-xj)!=abs(i-j)算法策略的选择：蛮力枚举法枚举回溯法程序流程图：算法的时间复杂度的分析：1）采用8重循环时间复杂度为8程序实现：1）voidCEightqueDlg::OnButton1(){//取自不同行的位置count=0;for(que[0]=0;que[0]<8;que[0]++)for(que[1]=0;que[1]<8;que[1]++)for(que[2]=0;que[2]

3、<8;que[2]++)for(que[3]=0;que[3]<8;que[3]++)for(que[4]=0;que[4]<8;que[4]++)for(que[5]=0;que[5]<8;que[5]++)for(que[6]=0;que[6]<8;que[6]++)for(que[7]=0;que[7]<8;que[7]++)Judge();CStringstr;str.Format("%d",count);MessageBox(str);}voidCEightqueDlg::Judge(){for(intt1=0;t1<8;t1++)//验证是否取自不同的列

4、for(intt2=t1+1;t2<8;t2++){if(que[t1]==que[t2])return;//存在处于同一列的位置则返}boolflag=false;//验证是否在不同的对角线上for(intj=0;j<7;j++){for(inti=1;i<8-j;i++){if(que[j]+i==que[i+j]

5、

6、que[j]-i==que[i+j]){flag=true;break;}}if(flag)break;}if(!flag){CStringa;a="";for(intk=0;k<8;k++){a.Format("%d",que[k]);out+=

7、a;}out+="";if(out.GetLength()%72==0)out+='';GetDlgItem(IDC_STATIC1)->SetWindowText(out);count++;}}2）voidCEight2Dlg::OnCancel(){inta[8];intcount=0CStringaa,bb;aa=bb="";for(a[0]=0;a[0]<8;a[0]++)for(a[1]=0;a[1]<8;a[1]++){if(check(a,1)==0)continue;for(a[2]=0;a[2]<8;a[2]++){if(check(a,2)=

8、=0)continue;for(a[3]=0;a[3]<8;a[3]++){if(check(a,3)==0)continue;for(a[4]=0;a[4]<8;a[4]++){if(check(a,4)==0)continue;for(a[5]=0;a[5]<8;a[5]++){if(check(a,5)==0)continue;for(a[6]=0;a[6]<8;a[6]++){if(check(a,6)==0)continue;for(a[7]=0;a[7]<8;a[7]++){if(check(a,7)==0)continue；else{for(inti=

9、0;i<8;i++){aa.Format("%d",a[i]);bb+=aa+"";}m_list.AddString(bb);bb="";count++;}}}}}}}}aa.Format("%d",count);MessageBox("总共有组合数："+aa);}intCEight2Dlg::check(inta[],intn){inti;for(i=0;i

10、

11、(a[i]==a[n]))return(0);return(1)；}结果输出：实验题目：动态规划最大盈利问题分析：5台机器3个工