//place（）方法負責從第i行開始擺放皇后
package?myqueen;
public?class?Queen
{
	private?final?int?size;//棋盤的大小，也表示皇后的數目
	private?int[]?location;//皇后在棋盤上的位置
	private?int[]?column;//皇后在棋盤上占據的列
	private?int[]?cross1;//皇后在棋盤上占據的某一條左低右高的對角線
	private?int[]?cross2;//皇后在棋盤上占據的某一條左高右低的對角線
	private?static?int?count;//解決方案的個數
	
	private?static?final?int?STATUS_OCCUPIED=1;//占據狀態
	private?static?final?int?STATUS_OCCUPY_CANCELED=0;//未占據狀態
	
	public?Queen（int?size）
	{
		this.size=size;
		location=new?int[size];
		column=new?int[size];
		cross1=new?int[2*size];
		cross2=new?int[2*size];
	}
	
	public?void?printLocation（）
	{
		System.out.println（“皇后在棋盤上的第“+count+“種擺放方式：“）;
		for（int?i=0;?i		{
			System.out.println（“行：“+i+“?列：“+location[i]）;
		}
	}
	
	/**判斷位置（i?j）是否被占據*/
	private?boolean?isOccupied（int?i?int?j）
	{
		return?（（column[j]?==?STATUS_OCCUPIED）
			||?（cross1[i+j]?==?STATUS_OCCUPIED）
			||?（cross2[i-j+size-1]?==?STATUS_OCCUPIED））;
	}
	
	/**如果參數flag為1，表示占據位置（i?j）
	?*?如果參數flag為0，表示取消占據位置（i?j）*/
	private?void?setStatus（int?i?int?j?int?flag）
	{
		column[j]?=?flag;//宣布占據或者取消占據第j列
		cross1[i+j]?=?flag;//宣布占據或者取消占據左低右高的對角線
		cross2[i-j+size-1]?=?flag;//宣布占據或者取消占據左高右低的對角線
	}
	
	/**從第i行開始擺放皇后*/
	public?void?place（int?i）
	{
		for（int?j=0;?j		{
			if（!isOccupied（i?j））//判斷該位置是否被占據
			{
				location[i]=j;//皇后占據第i行第j列
				setStatus（i?j?STATUS_OCCUPIED）;//宣布占據（i?j）位置
				if（i?				{
					place（i+1）;//遞歸擺放下一行的皇后
				}
				else
				{
					count++;//統計解決方案的個數
					printLocation（）;//完成任務，打印所有皇后的位置
				}
				setStatus（i?j?STATUS_OCCUPY_CANCELED）;
			}
		}
	}
	
	public?void?start（）
	{
		place（0）;
	}
	
	public?static?void?main（String[]?args）
	{
		new?Queen（8）.start（）;//通過修改參數實現不同個數的皇后擺放
	}
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????2121??2009-04-29?11:09??myqueen\Queen.java

?????文件???????1975??2009-04-29?11:09??myqueen\Queen.class

?????文件??????26624??2009-04-29?11:06??myqueen\八皇后問題算法分析.doc

?????文件??????32256??2009-04-29?11:04??myqueen\從第i行開始擺放皇后的流程圖.doc

?????目錄??????????0??2009-04-28?22:36??myqueen

-----------?---------??----------?-----??----

????????????????62976????????????????????5