八皇后问题:
在一个8×8国际象棋盘上,有8个皇后,每个皇后占一格;要求皇后间不会出现相互“攻击”的现象,即不能有两个皇后处在同一行、同一列或同一对角线上。问共有多少种不同的方法。
可推广到更一般的n皇后摆放问题。
首先是自己用笔来解一下相对简单的四皇后问题。
从第一行第一列开始,然后考虑下一行。当一行内没有符合条件的格子时,回到上一行,选择原来所选格的后面的格子。当找到一种放法后,把所选格变为考虑过的格,继续检查。直到第一行的所有格都被检查过为止。
我认为,程序中关键部分:
1.找到一行中符合条件的位置后,能往下一行继续判断
2.此行所有的格不能放之后,回到上一行,再检查
3.当找到一种符合条件的方法后,把此格变成已查过的,继续执行1、2。
4.第一行的所有格都检查过,执行结束。
数组标记:0表示此格可放子,1表示此格已放了子,2表示此格不可以放子,3表示此格已经考虑过了
这个问题,还可用其他方法解决,我这个方法和递归相似,均为回溯法的思想。
当n变大时,比如n=15时,共有2279184种方法,同时计算结果的时间也长了,此时,就要可考虑程序的效率问题了,我这个程序,没有考虑效率,所以,还有许多改进的地方。
public class FourQueuen {
private int row=8;//行列数
private int a[][]=new int[row][row];
//0表示此格可放子,1表示子此格已放了子,2表示此格不可以放子,3表示此格已经考虑过
private int sum=0;//计数
private boolean isEnd=false;//是否结束
private int i=0;
public static void main(String[] args) {
FourQueuenV1 fq=new FourQueuenV1();
fq.fourQ();
}
public void fourQ(){
while(isEnd==false){
oneAnswer();
haveChecked();
}
System.out.println("共有"+sum+"种放法");
}
//从第一行找到最后一行,找出一个答案
public void oneAnswer(){
while(i<row){
for(int j=0;j<row;j++){
if(a[i][j]==0){//此点可以放
a[i][j]=1;
notPut(i,j,2);
break; //接着放,下一行
}
if(j==row-1){//最后一个也没找到
i=revive(i);//回到上一行
if(isEnd==true){//第一行全部为3
break;
}
}
}//第一个for
if(isEnd==true){
break;
}
i++;
}//第二个for
if(isEnd!=true){
sum++;
}
}
//接着上一次的继续查找,即把最后一个1改为3
public void haveChecked(){
for(int j=0;j<row;j++){
if(a[row-1][j]==1){
a[row-1][j]=3;//把最后一行的一个1改为3
break;
}
}
//并且从最后一行开始判断
i=row-1;
}
//c行没地方后,回到上一层
public int revive(int c){
if(c>0){//若c=0,则不可能往上一行了,无解
c=c-1;//回到上一行
for(int j=0;j<row;j++){//遍历行,查找1
if(a[c][j]==1){
a[c][j]=3;//表示此格已检查过
//重新设置2和0
for(int p=c+1;p<row;p++){//3以下的行都变为0
for(int q=0;q<row;q++){
a[p][q]=0;
}
}
for(int p=0;p<=c;p++){//重新遍历此表格,到c行就可以了
for(int q=0;q<row;q++){
if(a[p][q]==1){
notPut(p,q,2);//再重新变为2
}
}
}//第二个for
break;//一行只可能有一个1
}// if(a[c][j]==1)
}
c=c-1;//因为i还要加1,所以再-1,才回到这一行
}else if(c==0){
isEnd=true;//第一行全部为3,整个查找结束
}
return c;
}
//此点的shu,xieRight,xieLeft改为num
public void notPut(int c,int d,int num){
shu(c,d,num);
xieRight(c,d,num);
xieLeft(c,d,num);
}
//判断是否能放
public void shu(int c,int d,int num){
for(int i=c+1;i<row;i++){
a[i][d]=num;
}
}
//向右下方
public void xieRight(int c,int d,int num){
for(int i=c+1,j=d+1;i<row&&j<row;i++,j++){//i,j同时+
a[i][j]=num;
}
}
//向左下方
public void xieLeft(int c,int d,int num){
for(int i=c+1,j=d-1;i<row&&j>=0;i++,j--){
a[i][j]=num;
}
}
}
分享到:
相关推荐
递 归 算 法 举 例——八皇后问题详解,和大家分享~
八皇后问题的C++算法,运行、调试成功! 数据结构的八皇后问题。
含八皇后问题的问题分析、算法描述、源代码及分析、运行结果等
帮助初学者解决一些C程序课本上的复杂编程问题。
c语言课设——八皇后
经典问题——八皇后解题方法 八皇后问题是1850年大数学家高斯提出来的,该问题在8*8的国际象棋棋盘上放置8个皇后,条件是做到没有一个皇后能“吃掉”任何其他皇后,即没有任何两个皇后被放置在棋盘的同一行或者同一...
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
重新使用c++简单地实现了回溯算法经典例子——八皇后问题,希望对大家有帮助
八皇后问题 c++ 八皇后问题 c++ 八皇后问题 c++
用最基本的结构编出了所有的排列。 还支持各种皇后的个数。
用递归解决八皇后问题的一段代码,专门写了较为详细的注释,本人原创,如有雷同,纯属巧合。
八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题
使用递归方法解决了n皇后问题,初学递归的朋友可以参考一下!
八皇后问题的MIPS实现,用MARS可跑出正确结果
作业代码,汇编写八皇后问题,自己写了一份,在网上找的也在里面
这是本人在学习过程中编写的一个小程序,主要是为了练习穷举法的使用,为了能够更好的理解穷举法,希望对算法感性的新手有所帮助
解决八皇后问题。利用mfc加了界面,输出结果放在一个文档中。
解决八皇后问题的源码,带有注释,由于数据结构即算法的学习,如有其他需要,请留言