//用lasvegas算法實現八皇后問題，一般要多次運行才能成功一次
import java.util.Random;
import java.math.*;
public class QueensLV
{
   static  int[] col;			//col[i]=k表示第i行放到第j列
  	static int[] d45;			//i-j
  	static 	int[] d135;			//i+j
	static int[] tryplace;
	static int n;
	static int a=0;
	public static int nLVQ(int nn)
	{
		n=nn;
		col=new int[n];
		d45=new int[n];
		d135=new int[n];
		tryplace=new int[n];
		for(int p=0;p<n;p++)
		{
			col[p]=tryplace[p]=0;
			d45[p]=d135[p]=1122;   //任意指定一個比較大的數字
			}
	     int k=1,nb,j=0;
		do
		{
			    nb=0;                        //安全位置
			for(int i=1;i<=n;i++)
			{     int ii=i-k;
			     int   iii=i+k;//i代表列

				if((isin(i,col,8)!=false))
				if((isin(ii,d45,8)!=false))
				if((isin(iii,d135,8)!=false))
				{
						nb++;
						if(uniform(1,nb)==1)
						j=i;
					}
				}
			if(nb>0)
			{
				tryplace[k-1]=j;
				col[k-1]=j;
				d45[k-1]=j-k;
				d135[k-1]=j+k;
				k++;
				   a++;
				}
			}while(nb!=0&&k<=n);
			if(nb>0)
			{
				System.out.println("success\n");
				for(int l=1;l<=n;l++)
				System.out.println(tryplace[l-1]);
				System.out.println("the number of the nodes is "+a);
				return 1;
				/*System.out.println("successcolcol\n");
								for(int l=1;l<=8;l++)
				System.out.println(col[l-1]);
				System.out.println("successd454545\n");
								for(int l=1;l<=8;l++)
				System.out.println(d45[l-1]);
				System.out.println("success123535\n");
								for(int l=1;l<=8;l++)
				System.out.println(d135[l-1]);*/
			}
			else
			{

			//System.out.println("failed!\n");
			return 0;
		}
		}

			private static  boolean isin(int i,int[] m,int k)  //判斷i是否在m[]中
			{
			for(int j=1;j<=k;j++)
			{
				if(m[j-1]==i)
				{
					return false;

				}

				}
				return true;
			}
		private static int uniform(int i,int j)   //從i到j中的一個任意整數
			{
              int k;
              Random r=new Random();
				 k=r.nextInt(j+1);
				 while(k==0)
				 {
					 k=r.nextInt(j+1); //返回從0（包括）到j+1(不包括)的一個整數
					 }
				  //System.out.println("uniform k is "+k+"\n");
					return k;
				}
	}