算法分析

				八皇后问题的java实现 
				（加入日期:2003-4-26 点击数:2628）
				【对此文发表评论】 【编程爱好者论坛】 【保存文章至硬盘】 【打印文章】 
				 
				/*
				* 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 				   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 				    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;
				}
				}
				
				本栏文章均来自于互联网，版权归原作者和各发布网站所有，本站收集这些文章仅供学习参考之用。任何人都不能将这些文章用于商业或者其他目的。( ProgramFan.Com )