回溯法求解 “n 皇后 问题”——Java 实现

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

回溯算法描述：

void Queue(int n)

   {

       for (i=1; i<=n; i++)    //初始化

          x[i]=0;

       k=1;

       while (k>=1)

       {

            x[k]=x[k]+1;     //在下一列放置第k个皇后

            while (x[k]<=n && !Place(k)) 

            x[k]=x[k]+1;     //搜索下一列

            if (x[k]<=n && k= =n) {   //得到一个解，输出

                 for (i=1; i<=n; i++)  

                     cout<<x[i];

                 return; } 

 

else if (x[k]<=n && k<n)

                        k=k+1;      //放置下一个皇后

                  else {      

                      x[k]=0;     //重置x[k]，回溯

                      k=k-1;

                  }  }

     }

     

     bool Place(int k)   //考察皇后k放置在x[k]列是否发生冲突

    {

         for (i=1; i<k; i++)   

             if (x[k]= =x[i] | | abs(k-i)= =abs(x[k]-x[i])) 

                 return false;

             return true; }

NQueen.java                   //回溯算法


import java.util.*;


public class NQueen
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  System.out.println("Please enter the number of queen you want(请输入你要求解的皇后的个数)");
  int n=in.nextInt();
  double startTime=System.currentTimeMillis();//startTime
  Queen(n);
  double endTime=System.currentTimeMillis();//endTime
  System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
 }
 /**
  *用回溯法设计函数Queen(n)求解
  */
 public static boolean Place(int x[],int k)//考察皇后k放置在x[k]列是否发生冲突
 {
  for(int i=1; i<k; i++)   
   if (x[k]==x[i]||Math.abs(k-i)==Math.abs(x[k]-x[i])) 
    return false;
   return true;
 }
 public static void Queen(int n)
 {
  int x[]=new int[n+1];
  for (int i=1; i<=n; i++)//初始化
   x[i]=0;
  int k=1;
  while (k>=1)
  {
   x[k]=x[k]+1;//在下一列放置第k个皇后
   while (x[k]<=n&&!Place(x,k)) 
    x[k]=x[k]+1;//搜索下一列
   if (x[k]<=n && k==n)
   {   //得到一个解，输出
       System.out.println("The answer is(得到的解是):");
    for (int i=1; i<=n; i++)  
    System.out.print("("+i+","+x[i]+")"+" ");
    System.out.println();
    return;
   } 
   else if (x[k]<=n && k<n)
    k=k+1;//放置下一个皇后
   else 
   {      
    x[k]=0;//重置x[k]，回溯
    k=k-1;
   }
  }
   }
}