queen.java

使用回溯递归法实现的八皇后问题的算法源码

public  class Queen
 {
	private static int EXIST_QUEEN =1;
	private static int NO_QUEEN=0;
	private int [] table = new int [8];
	private int count = 0;
	
	public Queen() 
	{
		setPosition(0);
	}
	
	public void print()
	 {
		System.out.println("+ - + - + - + - + - + - + - + - +");
		for(int i = 0; i < 8; i++)
		 {
			switch(table[i]) 
			{
				case 0:
					System.out.println("| Q |   |   |   |   |   |   |   |");
					break;
				case 1:
					System.out.println("|   | Q |   |   |   |   |   |   |");
					break;
				case 2:
					System.out.println("|   |   | Q |   |   |   |   |   |");
					break;
				case 3:
					System.out.println("|   |   |   | Q |   |   |   |   |");
					break;
				case 4:
					System.out.println("|   |   |   |   | Q |   |   |   |");
					break;
				case 5:
					System.out.println("|   |   |   |   |   | Q |   |   |");
					break;
				case 6:
					System.out.println("|   |   |   |   |   |   | Q |   |");
					break;
				case 7:
					System.out.println("|   |   |   |   |   |   |   | Q |");
					break;
				default:
					break;
			}
			System.out.println("+ - + - + - + - + - + - + - + - +");
		}			
	} 
	
	public void setPosition(int n)  //n表示在第n行，table[n]表示列数	
	 {
		for(int i = 0; i < 8; i++)  //i表示在第i列上放置皇后
		 {
			table[n] = i;
			if(inUse(n) == NO_QUEEN)  //如果没有皇后在同一列或斜线上（因为是按行依次放置故不可能在同一行上，又因为是每一行是从左到右放置故不可能出现右斜线上有皇后）
			 {
				if(n == 7)        //棋盘满时输出方案
				{
					count++;
					System.out.println("第" + count + "种解:");
					print();
				}
				else  //一个棋盘未放满时继续放置
					setPosition(n + 1);	
			}	
		}
	} 
	
	public int inUse(int n)
	 {
		for(int i = 0; i < n; i++)
		{
			if(table[i] == table[n] || Math.abs(table[i] - table[n]) == Math.abs(i - n))
			       //当放置的皇后同一列上含有皇后或左斜线上含有皇后时，则返回1
				return EXIST_QUEEN;
		}
		return NO_QUEEN;
	} 

   public static void main(String args[]) 
	{
		new Queen();
	}
}