练习——八皇后问题
八皇后问题:
在一个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){//第一行全部为3break;}}}//第一个forif(isEnd==true){break;}i++;}//第二个forif(isEnd!=true){sum++;}}//接着上一次的继续查找，即把最后一个1改为3public void haveChecked(){for(int j=0;j<row;j++){if(a[row-1][j]==1){a[row-1][j]=3;//把最后一行的一个1改为3break;}}//并且从最后一行开始判断i=row-1;}//c行没地方后，回到上一层public int revive(int c){if(c>0){//若c=0，则不可能往上一行了，无解 c=c-1;//回到上一行for(int j=0;j<row;j++){//遍历行，查找1if(a[c][j]==1){a[c][j]=3;//表示此格已检查过//重新设置2和0for(int p=c+1;p<row;p++){//3以下的行都变为0for(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}}}//第二个forbreak;//一行只可能有一个1}// if(a[c][j]==1)}c=c-1;//因为i还要加1，所以再-1，才回到这一行}else if(c==0){isEnd=true;//第一行全部为3，整个查找结束}return c;}//此点的shu,xieRight,xieLeft改为numpublic 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;}}}