八皇后問題的java實現:CSDN論壇,CSDN開發高手,CSDN技術社區八皇后問題的java實現 










                  八皇后問題的java實現
                     瀏覽選項： 大中小  顏色 默認 灰度 橄欖色 綠色 藍色 褐色 紅色   





                              /*
                               * 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;
                               }
                              }






                    






            Copyright &copy; 2004 www.CSDN.com.cn All Rights Reserved