递归调用（为什么会StackOverflowError）——八皇后算法

为什么我的这个算法有时会StackOverflowError，代码如下

package algorithm;

public class EightQueen {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		EightQueen self = new EightQueen();
		for(int i=12;i<13;i++){
			self.queen(i);
		}
	}
	
	public void queen(int n){
		System.out.println("======== "+n+" ========");
		int[][] grid = new int[n][n];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				grid[i][j] = 0;
			}
		}
		init(grid,0,0,false,n);

		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(grid[i][j]==1){
					System.out.print(" + ");
				}else{
					System.out.print(" - ");
				}
			}
			System.out.println();
		}
	}
	
	public void init(int[][] grid,int horizontal,int vertical,boolean isBack,int size){
		if(isBack){
			if(horizontal==28&&vertical==16){
				System.out.println();
			}
			grid[horizontal][vertical] = 0;
			vertical++;
		}
		if(vertical>=size){
			horizontal--;
			if(horizontal<0){
				System.out.println("No result!");
				return ;
			}
			for(int i=0;i<size;i++){
				if(grid[horizontal][i]==1){
					init(grid,horizontal,i,true,size);
					return ;
				}
			}
		}
		for(int i=0;i<horizontal;i++){
			for(int j=0;j<size;j++){
				if(grid[i][j]==1&&!isFree(horizontal,vertical,i,j)){
					init(grid,horizontal,vertical,true,size);
					return ;
				}
			}
		}
		grid[horizontal][vertical] = 1;
		System.out.println(horizontal+":"+vertical);
		if(++horizontal>=size){
			return ;
		}
		init(grid,horizontal,0,false,size);
		return ;
	}
	
	private boolean isFree(int x,int y,int holdX,int holdY){
		if(x==holdX||y==holdY){//同一横排或竖排
			return false;
		}
		int slant1 = (x-holdX)-(y-holdY);
		int slant2 = (x-holdX)+(y-holdY);
		if(slant1==0||slant2==0){//两条斜线
			return false;
		}
		return true;
	}

}

评论

1 楼 airpeng 2011-11-17  

下面这个确MS很好用

package algorithm;

public class Queen_Java {

	int QUEEN_COUNT = 20; // 是多少皇后
	static final int EMPTY = 0;
	int[][] count = new int[QUEEN_COUNT][QUEEN_COUNT];
	int[] QueenIndex = new int[QUEEN_COUNT];
	int resultCount = 0;
	long time = System.currentTimeMillis();

	public void putQueenIndex(int row) {
		for (int col = 0; col < QUEEN_COUNT; col++) {
			if (count[row][col] == EMPTY) {
				for (int iRow = row + 1; iRow < QUEEN_COUNT; iRow++) {
					count[iRow][col]++;
					if ((col - iRow + row) >= 0) {
						count[iRow][col - iRow + row]++;
					}
					if ((col + iRow - row) < QUEEN_COUNT) {
						count[iRow][col + iRow - row]++;
					}
				}
				QueenIndex[row] = col;
				if (row == QUEEN_COUNT - 1) {
					print(++resultCount);
				} else {
					putQueenIndex(row + 1);
				}
				for (int iRow = row + 1; iRow < QUEEN_COUNT; iRow++) {
					count[iRow][col]--;
					if ((col - iRow + row) >= 0) {
						count[iRow][col - iRow + row]--;
					}
					if ((col + iRow - row) < QUEEN_COUNT) {
						count[iRow][col + iRow - row]--;
					}
				}
			}
		}
		if (row == 0) {
			System.out.println(QUEEN_COUNT + "皇后共有 " + resultCount + " 个解\n"
					+ (System.currentTimeMillis() - time) + "毫秒");
		}
	}

	public void print(int n) {
		System.out.println(QUEEN_COUNT + "皇后的第 " + n + " 个解：");
		for (int i = 0; i < QUEEN_COUNT; i++) {
			for (int j = 0; j < QUEEN_COUNT; j++) {
				System.out.print(QueenIndex[i] == j ? " * " : " - ");
			}
			System.out.println();
		}
		System.out.println();
	}

	public static void main(String[] args) {
		new Queen_Java().putQueenIndex(0);
	}
}