/*
* 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;
}
}
八皇后问题的高效解法-递归版
//8 Queen 递归算法
//如果有一个Q 为 chess[i]=j;
//则不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置
class Queen8{
static final int QueenMax = 8;
static int oktimes = 0;
static int chess[] = new int[QueenMax];//每一个Queen的放置位置
public static void main(String args[]){
for (int i=0;i<QueenMax;i++)chess[i]=-1;
placequeen(0);
System.out.println("\n\n\n八皇后共有"+oktimes+"个解法 made by yifi 2003");
}
public static void placequeen(int num){ //num 为现在要放置的行数
int i=0;
boolean qsave[] = new boolean[QueenMax];
for(;i<QueenMax;i++) qsave[i]=true;
//下面先把安全位数组完成
i=0;//i 是现在要检查的数组值
while (i<num){
qsave[chess[i]]=false;
int k=num-i;
if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false;
if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false;
i++;
}
//下面历遍安全位
for(i=0;i<QueenMax;i++){
if (qsave[i]==false)continue;
if (num<QueenMax-1){
chess[num]=i;
placequeen(num+1);
}
else{ //num is last one
chess[num]=i;
oktimes++;
System.out.println("这是第"+oktimes+"个解法 如下:");
System.out.println("第n行: 1 2 3 4 5 6 7 8");
for (i=0;i<QueenMax;i++){
String row="第"+(i+1)+"行: ";
if (chess[i]==0);
else
for(int j=0;j<chess[i];j++) row+="--";
row+="++";
int j = chess[i];
while(j<QueenMax-1){row+="--";j++;}
System.out.println(row);
}
}
}
//历遍完成就停止
}
}
联系客服
