backtrace_nqueen.java

此代码主要解决的是N皇后问题

  public class Backtrace_NQueen
  {
	  static int n;			//皇后个数
	  static int[] x;		//当前解
	  static long sum;		//当前已经找到的可行方案数
	  public static long nQueen(int nn)
	  {
		  n=nn;
		  sum=0;
		  x=new int[n+1];
		  for(int i=0;i<=n;i++) x[i]=0;
		  backtrace(1);
		  return sum;
		  }


		  private static boolean place(int k)
		  {
			  for(int j=1;j<k;j++)
			  if((Math.abs(k-j))==Math.abs(x[j]-x[k])||(x[j]==x[k]))
			  return false;
			  return true;
			  }

			  private static void backtrace(int t)
			  {
				  if(t>n)
				  {
					  sum++;
                   for(int i=1;i<=n;i++)
                   System.out.println("   "+x[i]);
                   System.out.println("it is the "+sum+"th:\n");
					  }
				  else
				  for(int i=1;i<=n;i++)
				  {
					  x[t]=i;
					  if(place(t)) backtrace(t+1);
					  }
				  }
	  }