/*
* Created on 2003-3-28
* n皇后问题算法。
* 把棋盘看成一个坐标系，以左下角为原点（0,0)。坐标系的每个点为一个Point类。
* 每个皇后为一个皇后对象Queen。
* 判断一个点的坐标是否在，一个皇后控制的范围的函数为Queen.isUnderControl(point)。
*
*/
package bia.arithmetic;
import java.util.Date;
/**
* @author Administrator
*
* To change this generated comment go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
public class EightQueen {
Queen[] stack = new Queen[8];
int sp = 0;
int num = 0;
public EightQueen() {
num = 8;
stack = new Queen[num];
sp = 0;
}
public EightQueen(int num) {
this.num = num;
stack = new Queen[num];
sp = 0;
}
/**
* 打印皇后的坐标列表。
* @renzc
*
*/
public void list() {
System.out.println("Begin list the stack Point:");
for (int i = 0; i < sp; i++) {
stack[i].pos.println();
}
System.out.println("End list the stack Point:");
}
/**
* 主算法流程。
* @Administrator
*
*/
public void calc() {
sp = 0;
stack[sp++] = new Queen();
while (sp >= 0 && sp <= num - 1) {
Queen queen = getQueen(sp);
if (null == queen) {
boolean flag = true;
while (flag) {
--sp;
if (sp < 0)
break;
if (stack[sp].pos.y == num - 1) {
}
else {
stack[sp++].pos.y++;
flag = false;
for (int k = 0; k < sp - 1; k++) {
if (stack[k].isUnderControl(stack[sp - 1].pos)) {
flag = true;
break;
}
}
}
}
}
else {
stack[sp++] = queen;
}
}
}
public Queen getQueen(int x) {
boolean flag = true;
int y = 0;
while (flag) {
flag = false;
for (int i = 0; i < x; i++) {
if (stack[i].isUnderControl(new Point(x, y))) {
flag = true;
break;
}
}
if (flag && y <= num - 1) {
y++;
}
else if (y >= num) {
return null;
}
}
return new Queen(new Point(x, y));
}
public static void main(String[] args) {
EightQueen a = new EightQueen(20);
long start = new Date().getTime();
System.out.println("起始时间：[" + start + "]");
a.calc();
long end = new Date().getTime();
System.out.println("截止时间:[" + end + "]");
System.out.println("共耗时：[" + (end - start) + "]毫秒");
if (a.sp > 0) {
a.list();
}
else {
System.out.println("这个题目无解！");
}
}
}
class Point {
int x, y;
public void println() {
System.out.println("The Point is [x,y]=[" + x + "," + y + "]");
}
public Point() {
x = 0;
y = 0;
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
/**
* @return int
*/
public int getX() {
return x;
}
/**
* @return int
*/
public int getY() {
return y;
}
/**
* Sets the x.
* @param x The x to set
*/
public void setX(int x) {
this.x = x;
}
/**
* Sets the y.
* @param y The y to set
*/
public void setY(int y) {
this.y = y;
}
}
class Queen {
Point pos;
public Queen() {
pos = new Point();
}
public Queen(Point pos) {
this.pos = pos;
}
public boolean isUnderControl(Point point) {
boolean ret = true;
if (point.x != pos.x
&& point.y != pos.y
&& Math.abs(point.x - pos.x) != Math.abs(point.y - pos.y)
&& Math.abs(point.x + point.y) != Math.abs(pos.x + pos.y)) {
ret = false;
}
return ret;
}
} |