算法分析

				八皇后问题的高效解法-递归版 
				（加入日期:2003-9-2 点击数:4434）
				【对此文发表评论】 【编程爱好者论坛】 【保存文章至硬盘】 【打印文章】 
				 
				//8 Queen 递归算法
				//如果有一个Q 为 chess[i]=j;
				//则不安全的地方是 k行  j位置,j+k-i位置,j-k+i位置
				
				class Queen8{
				
				
				  static final int QueenMax = 8;
				  static int oktimes = 0;
				  static int chess[] = new int[QueenMax];//每一个Queen的放置位置
				
				
				  public static void main(String args[]){
				    for (int i=0;i				    placequeen(0);
				    System.out.println("\n\n\n八皇后共有"+oktimes+"个解法    made by yifi 2003");
				  }
				
				
				  public static void placequeen(int num){ //num 为现在要放置的行数
				    int i=0;
				    boolean qsave[] = new boolean[QueenMax];
				    for(;i				    
				    //下面先把安全位数组完成
				    i=0;//i 是现在要检查的数组值
				    while (i				      qsave[chess[i]]=false;
				      int k=num-i;
				      if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false;
				      if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false;
				      i++;
				    }
				    //下面历遍安全位
				    for(i=0;i				      if (qsave[i]==false)continue;
				      if (num				        chess[num]=i;
				        placequeen(num+1);
				      }
				      else{ //num is last one
				      chess[num]=i;
				      oktimes++;
				      System.out.println("这是第"+oktimes+"个解法 如下:");
				      System.out.println("第n行:  1 2 3 4 5 6 7 8");
				      
				      for (i=0;i				       String row="第"+(i+1)+"行:  ";
				       if (chess[i]==0);
				       else 
				        for(int j=0;j				        row+="++";
				        int j = chess[i];
				        while(j				       System.out.println(row);
				      }
				      }
				    }
				  //历遍完成就停止
				  }
				}
				
				本栏文章均来自于互联网，版权归原作者和各发布网站所有，本站收集这些文章仅供学习参考之用。任何人都不能将这些文章用于商业或者其他目的。( ProgramFan.Com )