首页 | 社区 | 博客 | 招聘 | 文章 | 新闻 | 下载 | 读书 | 代码
亲,您未登录哦! 登录 | 注册

八皇后问题的高效解法-递归版

打印文章

分享到:
//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<QueenMax;i++)chess[i]=-1;
    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<QueenMax;i++) qsave[i]=true;
    
    //下面先把安全位数组完成
    i=0;//i 是现在要检查的数组值
    while (i<num){
      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<QueenMax;i++){
      if (qsave[i]==false)continue;
      if (num<QueenMax-1){
        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<QueenMax;i++){
       String row="第"+(i+1)+"行:  ";
       if (chess[i]==0);
       else
        for(int j=0;j<chess[i];j++) row+="--";
        row+="++";
        int j = chess[i];
        while(j<QueenMax-1){row+="--";j++;}
       System.out.println(row);
      }
      }
    }
  //历遍完成就停止
  }
}

本栏文章均来自于互联网,版权归原作者和各发布网站所有,本站收集这些文章仅供学习参考之用。任何人都不能将这些文章用于商业或者其他目的。( Pfan.cn )

编程爱好者论坛

本栏最新文章