数据结构应用回顾之递归(一) N皇后问题

 

问题： 求解N皇后问题的所有可能的解

 

package com.xx.dataStructure.stack;

//求解N皇后问题的所有解
public class Queen {
	
	private int solution = 0;
	
	private int n;
	
	public Queen(int n){
		assert(n > 0);
		this.n = n;
		this.solution = 0;
	}
	
	public static void main(String [] args){
		solveProblem(new Queen(1));
		solveProblem(new Queen(2));
		solveProblem(new Queen(3));
		solveProblem(new Queen(4));
		solveProblem(new Queen(5));
		solveProblem(new Queen(6));
		solveProblem(new Queen(7));
		solveProblem(new Queen(8));
	}
	
	public static void solveProblem(Queen queen){
		int [] queens = new int[queen.n];
		System.out.println(  queen.n + " 皇后问题.....");
		placeQueen(queens,1,queen);
	}
	
	//放置第n个Queen
	//N为总共要放的Queen个数
	public static void placeQueen(int [] queens,int n,Queen queen){
		for(int i = 0; i< queen.n ; i ++){
			if (canPlaceQueen(queens,n-1,i)) {
				queens[n-1] = i;
				if (n == queen.n){
					//output
					System.out.println("the " + ++queen.solution +" th solution");
					for(int i0 = 0; i0 < queen.n; i0++){
						for(int j0 = 0; j0 <queen.n ;++j0){
							if (j0 == queens[i0] ){
								System.out.print("Q ");
							}else {
								System.out.print("X ");
							}
						}
						System.out.println();
					}
					System.out.println();
					break;
				}else {
					placeQueen(queens,n+1,queen);
				}
			}
		}
	}
	
	//
	public static boolean canPlaceQueen(int [] queens,int placedQueenNum,int y){
		boolean result = true;
		for(int i = 0; i < placedQueenNum ; ++i ){
			//在同一列 
			if ( queens[i] == y){
				result = false;
				break;
			}
			//在对角线
			if (Math.abs(placedQueenNum - i) == Math.abs(queens[i] - y)) {
				result = false;
				break;
			}
		}
		return result;
	}
}

   程序输出

  

1 皇后问题.....
the 1 th solution
Q 

2 皇后问题.....
3 皇后问题.....
4 皇后问题.....
the 1 th solution
X Q X X 
X X X Q 
Q X X X 
X X Q X 

the 2 th solution
X X Q X 
Q X X X 
X X X Q 
X Q X X 

5 皇后问题.....
the 1 th solution
Q X X X X 
X X Q X X 
X X X X Q 
X Q X X X 
X X X Q X 

the 2 th solution
Q X X X X 
X X X Q X 
X Q X X X 
X X X X Q 
X X Q X X 

the 3 th solution
X Q X X X 
X X X Q X 
Q X X X X 
X X Q X X 
X X X X Q 

the 4 th solution
X Q X X X 
X X X X Q 
X X Q X X 
Q X X X X 
X X X Q X 

the 5 th solution
X X Q X X 
Q X X X X 
X X X Q X 
X Q X X X 
X X X X Q 

the 6 th solution
X X Q X X 
X X X X Q 
X Q X X X 
X X X Q X 
Q X X X X 

the 7 th solution
X X X Q X 
Q X X X X 
X X Q X X 
X X X X Q 
X Q X X X 

the 8 th solution
X X X Q X 
X Q X X X 
X X X X Q 
X X Q X X 
Q X X X X 

the 9 th solution
X X X X Q 
X Q X X X 
X X X Q X 
Q X X X X 
X X Q X X 

the 10 th solution
X X X X Q 
X X Q X X 
Q X X X X 
X X X Q X 
X Q X X X 

6 皇后问题.....
the 1 th solution
X Q X X X X 
X X X Q X X 
X X X X X Q 
Q X X X X X 
X X Q X X X 
X X X X Q X 

the 2 th solution
X X Q X X X 
X X X X X Q 
X Q X X X X 
X X X X Q X 
Q X X X X X 
X X X Q X X 

the 3 th solution
X X X Q X X 
Q X X X X X 
X X X X Q X 
X Q X X X X 
X X X X X Q 
X X Q X X X 

the 4 th solution
X X X X Q X 
X X Q X X X 
Q X X X X X 
X X X X X Q 
X X X Q X X 
X Q X X X X 

.........