public class Queen {
private final int size; //棋盘的大小,也表示皇后的数目
private int[] location; //皇后在棋盘的每行上的列的位置
private int[] colsOccupied; //皇后在棋盘上占据的列
private int[] cross1Occupied; //皇后在棋盘上占据的正对角线
private int[] cross2Occupied; //皇后在棋盘上占据的反对角线
private static int count; //解决方案的个数
static int n=0;
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];
colsOccupied=new int[size];
cross1Occupied=new int[2*size];
cross2Occupied=new int[2*size];
} public void printLocation(){
System.out.println("以下是皇后在棋盘上的第"+count+"种摆放位置");
for(int i=0;i<size;i++)
System.out.println("行:"+i+" 列:"+location[i]);
}
/** 判断位置(i,j)是否被占领 */
private boolean isOccupied(int i,int j){
return (colsOccupied[j]==1)
|| (cross1Occupied[i-j+size-1]==1)
|| (cross2Occupied[i+j]==1);
}
/** 如果参数flag为1,表示占领位置(i,j);
* 如果参数flag为0,表示取消占领位置(i,j)
*/
private void setStatus(int i,int j,int flag){
colsOccupied[j]=flag; //宣布占领或取消占领第j列
cross1Occupied[i-j+size-1]=flag; //宣布占领或取消占领正对角线
cross2Occupied[i+j]=flag; //宣布占领或取消占领反对角线
}
/** 从第i行开始摆放皇后 */
public void place(int i){
for(int j=0;j<size;j++) //在第i行,分别尝试把皇后放在每一列上
if(!isOccupied(i,j)){ //判断该位置是否被占据
location[i]=j; //摆放皇后,在第i行把皇后放在第j列
setStatus(i,j,STATUS_OCCUPIED); //宣布占领(i,j)位置
if( i<size-1){
place(i+1);
// System.out.println(i+" "+j);
}//如果所有皇后没有摆完,递归摆放下一行的皇后
else {
count++; //统计解决方案的个数
printLocation(); //完成任务,打印所有皇后的位置
if(count>0)
break;
}
//回溯,撤销占领位置(i,j)
setStatus(i,j,STATUS_OCCUPY_CANCELED); ////////这里是怎样回溯/////
System.out.println(n);
if(n==110 //111是4 7 ,110是1 4 ,在第4行发生改变
){
System.out.println(i+" "+j);
}
n++;
}
}
public void start(){
place(0); //从第0行开始放置皇后
}
public static void main(String args[]){
new Queen(8).start();
}
}
private final int size; //棋盘的大小,也表示皇后的数目
private int[] location; //皇后在棋盘的每行上的列的位置
private int[] colsOccupied; //皇后在棋盘上占据的列
private int[] cross1Occupied; //皇后在棋盘上占据的正对角线
private int[] cross2Occupied; //皇后在棋盘上占据的反对角线
private static int count; //解决方案的个数
static int n=0;
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];
colsOccupied=new int[size];
cross1Occupied=new int[2*size];
cross2Occupied=new int[2*size];
} public void printLocation(){
System.out.println("以下是皇后在棋盘上的第"+count+"种摆放位置");
for(int i=0;i<size;i++)
System.out.println("行:"+i+" 列:"+location[i]);
}
/** 判断位置(i,j)是否被占领 */
private boolean isOccupied(int i,int j){
return (colsOccupied[j]==1)
|| (cross1Occupied[i-j+size-1]==1)
|| (cross2Occupied[i+j]==1);
}
/** 如果参数flag为1,表示占领位置(i,j);
* 如果参数flag为0,表示取消占领位置(i,j)
*/
private void setStatus(int i,int j,int flag){
colsOccupied[j]=flag; //宣布占领或取消占领第j列
cross1Occupied[i-j+size-1]=flag; //宣布占领或取消占领正对角线
cross2Occupied[i+j]=flag; //宣布占领或取消占领反对角线
}
/** 从第i行开始摆放皇后 */
public void place(int i){
for(int j=0;j<size;j++) //在第i行,分别尝试把皇后放在每一列上
if(!isOccupied(i,j)){ //判断该位置是否被占据
location[i]=j; //摆放皇后,在第i行把皇后放在第j列
setStatus(i,j,STATUS_OCCUPIED); //宣布占领(i,j)位置
if( i<size-1){
place(i+1);
// System.out.println(i+" "+j);
}//如果所有皇后没有摆完,递归摆放下一行的皇后
else {
count++; //统计解决方案的个数
printLocation(); //完成任务,打印所有皇后的位置
if(count>0)
break;
}
//回溯,撤销占领位置(i,j)
setStatus(i,j,STATUS_OCCUPY_CANCELED); ////////这里是怎样回溯/////
System.out.println(n);
if(n==110 //111是4 7 ,110是1 4 ,在第4行发生改变
){
System.out.println(i+" "+j);
}
n++;
}
}
public void start(){
place(0); //从第0行开始放置皇后
}
public static void main(String args[]){
new Queen(8).start();
}
}
解决方案 »
免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货