穷举法和回溯法求解八皇后

八皇后是数学家高斯提出的趣题，即在国际象棋中8*8的方格的棋盘上如何放置8个皇后，使得8个皇后任何2个不能互相攻击（即不能同一纵列，不能统一横排，不能在45度斜线上）。
以下是我自己用java写的 穷举法和回溯法求八皇后。

//穷举法列出八皇后的可能性
//yuyong 2012-4-1
public class QjfBhh {

	public static void main(String[] args) {
		List<Integer> results = new ArrayList<Integer>();
		int count = 0;

		long from=System.currentTimeMillis();
		
		for (int start = 12345678; start <= 87654321; start += 9) {
			if (calculate(String.valueOf(start))) {
					results.add(start);
					count++;
			}
		}
		
		long end=System.currentTimeMillis();

		for (Integer value : results) {
			System.out.println(value);
		}
		
		System.out.println("共 "+count+" 个,共耗时 "+(end-from)+" 毫秒");
	}

	private static boolean calculate(String str){
		for(int i=0;i<str.length();i++){
			if(str.charAt(i)=='0'||str.charAt(i)=='9')
				return false;
			for(int j=0;j<i;j++){
				if(str.charAt(i)==str.charAt(j))
					return false;
				if(Math.abs((i-j))==Math.abs((str.charAt(i)-str.charAt(j))))
					return false;
			}
		}
		
		return true;
	}

}

因为不能统一横排或者纵排，所以8位数字中1到8肯定各出现一次，不可以重复。所以范围规定于[12345678,87654321] 并且穷举的步长为9，因为数字1-8各出现一次，所以，8位数字肯定为9的倍数.

//回溯法求解八皇后
//yuyong 2012-4-1
public static void main(String[] args) {
		List<String> results = new ArrayList<String>();
		long from=System.currentTimeMillis();
		List<Integer>indexs=new ArrayList<Integer>();
		for(int i=0;i<=7;i++)
			indexs.add(-1);
		int current=-1;
		while(true){
                        //第一个皇后也无法满足条件时
			if(current==-1&&(indexs.get(0)==7))
				break;
			current++;

			//当前皇后已经无法满足条件时
			if(indexs.get(current)==7){
				indexs.set(current, -1);
				current=current-2;
				continue;
			}
			
			indexs.set(current, indexs.get(current)+1);
			
			for(int j=0;j<current;j++){
				if((indexs.get(current)==indexs.get(j))||(Math.abs((current-j))==Math.abs((indexs.get(current)-indexs.get(j))))){
					if(indexs.get(current)==7){
						indexs.set(current, -1);
						current=current-2;
						break;
					}else{
						current=current-1;
						break;
					}
				}
			}
			
			//8个皇后均满足条件时
			if(current==7){
				results.add(indexs.toString());
				current=current-1;
			}
			
		}
		
		long end=System.currentTimeMillis();
		for (String value : results) {
			System.out.println(value);
		}
		
		System.out.println("共 "+results.size()+" 个,共耗时 "+(end-from)+" 毫秒");
	}

回溯法求解八皇后，思路是，当前位的皇后数字都无法满足条件时，就回溯到上一个皇后位置，上一个皇后，达到满足条件时，继续下一个皇后的列举判断。直到第一个皇后都无法满足条件为止。

评论

1 楼 abcd0553 2012-04-12  

YCY，过劲蛮