queens.java

利用随机算法和回溯法实现8皇后问题

import java.io.*;
import java.util.*;
public class Queens {

	/**
	 * @param args
	 */
	int[] ok;
	int[] x;
	int[] y;
	int n;
	boolean good;
	java.util.Random myran;
	
	public Queens(int myn) {
		super();
		n = myn;
		ok = new int [n+1];
		x = new int [n+1];
		y = new int [n+1];
		good = false;
		myran = new java.util.Random();
	}

	public boolean place(int k){
		for(int j = 0; j <= k-1; ++j){
			if((Math.abs(k-j) == Math.abs(x[j]-x[k])) || (x[j] == x[k])){
				return false;
			}
		}
		return true;
	}
	
	public void backTrack(int t){
		if(t >= n){
			for(int i = 0; i < n; ++i){
				y[i] = x[i];
			}
			good = true;
		}
		else{
			for(int i = 0; i < n && (!good); ++i){
				x[t] = i ;
				if(place(t)){
					
					backTrack(t+1);
				}
			}			
		}
	}
	
	public boolean queensLvb(boolean success,int stopLv){
		good = false;
		int k = 0;
		int count;
		while(k < stopLv){
			count = 0;
			for(int i = 0; i < n; i++){
				x[k] = i;
				if(place(k)){	
					count++;
					ok[count] = i;
				}
			}
			if(count == 0){
				success = false;
				return false;
			}
			
			int rannum = myran.nextInt(count);			
			if(rannum == 0){
				++rannum;
			}
			x[k] = ok[rannum];
			k++;
		}
		backTrack(stopLv);
		return good;
	}
	
	public int repeatQueensLvb(int stopLv){
		boolean success = false;
		int number = 0;
		while(!success){
			success = queensLvb(success,stopLv);
			number++;
		}
		return number;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int number = 0;
		int mytimes = 10000;
		double d1 = 0.0;
		double dt = 0.0;
		int k = 8;
		Queens myQueen = new Queens(k);
		for(int m = k; m >= 0; --m){
			number = 0;
			d1 = 0.0;
			dt = 0.0;
			for(int times = 0; times <=mytimes; ++times){
				number = myQueen.repeatQueensLvb(m);
				d1 = 1.0 / number;
				dt += d1;
			}
			dt = dt / mytimes;
			for(int i = 0; i < k; ++i){
				for(int j = 0; j < k; j++){
					if( myQueen.x[i] == j){
						System.out.print('Q');
						System.out.print('|');
					}
					else{				
						System.out.print('A');
						System.out.print('|');
					}
				}
				System.out.println();			
			}
			
			System.out.println(dt);
			System.out.println("-------------------------------------	"  + m );
		}
	}

}