• 注册
  • 关于作者
    企业认证:趣记站长
    关注 6 粉丝 4 喜欢 9 内容 992
    江西省·南昌市
    聊天 送礼
    • 查看作者
    • 八皇后问题的java实现

      /*

      * Created on 2003-3-28

      * n皇后问题算法。

      * 把棋盘看成一个坐标系,

      刘徽《九章算术》中的勾股数
      贪心算法在背包中的应用,五子棋的核心算法,关联规则挖掘算法综述,九连环游戏算法递归实现,八皇后问题的高效解法-递归版,拼图游戏的算法,人民币大小写转换算法,CRC循环校验的具体算法,上楼梯算法的java实现,解决排列组合问题的通用算法,杨辉三角形,水仙花数,刘徽《九章算术》中的勾股数,八皇后问题的java实现,图像分割中阈值的自动选取的研究及其算法实现,高精度乘法和阶乘,RSA算法介绍,黑洞数的验证,算法一词的由来,什么是算法
      算法

      以左下角为原点(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;

      }

      }

      刘徽《九章算术》中的勾股数
      贪心算法在背包中的应用,五子棋的核心算法,关联规则挖掘算法综述,九连环游戏算法递归实现,八皇后问题的高效解法-递归版,拼图游戏的算法,人民币大小写转换算法,CRC循环校验的具体算法,上楼梯算法的java实现,解决排列组合问题的通用算法,杨辉三角形,水仙花数,刘徽《九章算术》中的勾股数,八皇后问题的java实现,图像分割中阈值的自动选取的研究及其算法实现,高精度乘法和阶乘,RSA算法介绍,黑洞数的验证,算法一词的由来,什么是算法
      算法

    • 0
    • 0
    • 0
    • 84
    • 单栏布局 侧栏位置: