文档章节

中国象棋程序的设计与实现(六)--N皇后问题的算法设计与实现(源码+注释+截图)

FansUnion
 FansUnion
发布于 2015/05/03 01:30
字数 1476
阅读 14
收藏 0
八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。
该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。
计算机发明后,有多种方法可以解决此问题。

 

2010年,在写完中国象棋的核心模块后,当时添加了一个扩展应用模块,N皇后问题。

效果图

算法源码

下面是控制台程序的源码。

/**
 * 项目名称: FansChineseChess
 * 版本号:2.0
 * 名字:雷文
 * 博客: http://FansUnion.cn
 * CSDN:http://blog.csdn.net/FansUnion
 * 邮箱: leiwen@FansUnion.cn
 * QQ:240-370-818
 * 版权所有: 2011-2013,leiwen
 */
package cn.fansunion.chinesechess.ext.empress;

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

/**
 * 求N皇后的所有合法布局
 *
 * 3个约束条件:任何2个棋子都不能占居棋盘上的同一行、或者同一列、或者同一对角线。
 *
 * 棋盘状态的变化情况,可以看作一个N叉树。
 *
 * 求所有合法布局的过程,即为在3个约束条件下先根遍历状态树的过程。
 *
 * 遍历中访问结点的操作为,判断棋谱上是否已经得到一个完整的布局,如果是,则输出该布局;
 *
 * 否则依次先根遍历满足约束条件的各棵子树,即首先判断该子树根的布局是否合法,若合法,则
 *
 * 先根遍历该子树,否则减去该子树分支。
 *
 * @author leiwen@fansunion.cn,http://FansUnion.cn,
 *         http://blog.csdn.net/FansUnion
 * @since 2.0
 */
public class EmpressModel {

    /**
     * 皇后的个数
     */
    private int num;
    /**
     * 棋盘数据结构
     */
    private int[][] array;
    /**
     * 棋盘中的布局集合,每一种布局采用简写形式
     */
    private List<ArrayList<Point>> lists = new ArrayList<ArrayList<Point>>();
    /**
     * 棋盘中的布局集合,每一种布局采用完整形式
     */
    private List<int[][]> advancedLists = new ArrayList 

    public EmpressModel(int n) {
        this.num = n;
        array = new int[n + 1][n + 1];// 默认为0
    }

    // 初始化所有的布局
    public void initAllLayout() {
        trial(1);
        sort();
        initAdvancedLists();
    }

    /**
     * 进入本函数时,在n*n棋盘前j-1列已经放置了满足3个条件的j-1个棋子
     *
     * 现在从第j列起,继续为后续棋子选择合适的位置
     *
     * 选择列优先,是为了保证在GUI显示布局的变化,看起来是,每一行的棋子都是从左向右移动的。
     *
     * 行优先时,每列棋子,从上向下移动。
     *
     * @param j
     */
    private void trial(int j) {
        // 进入本函数时,在n*n棋盘前j-1列已经放置了满足3个条件的j-1个棋子
        // 现在从第i行起,继续为后续棋子选择合适的位置
        if (j > num) {
            // 求得一个合法布局,保存起来
            saveCurrentLayout();
        } else {
            for (int i = 1; i <= num; i++) {
                // 在第i行第j列放置一个棋子
                array[i][j] = 1;
                if (isLegal(i, j)) {
                    trial(j + 1);
                }
                // 移走第i行第j列的棋子
                array[i][j] = 0;
            }
        }
    }

    /**
     * 判断当前布局是否合法
     *
     * @return
     */
    private boolean isLegal(int row, int col) {

        for (int i = 1; i < array.length; i++) {
            int sumI = 0;// 第i行之和
            int sumJ = 0;// 第i列之和
            for (int j = 1; j < array[i].length; j++) {
                sumI += array[i][j];
                sumJ += array[j][i];
            }
            if (sumI >= 2 || sumJ >= 2) {
                return false;
            }
            sumI = 0;
            sumJ = 0;

        }

        // 左上到右下的对角线是否有棋子
        int i = row - 1;
        for (int j = col - 1; j >= 1; j--) {
            if (i >= 1 && array[i][j] == 1) {
                return false;
            }
            i--;
        }

        // 左下到右上的对角线是否有棋子
        i = row + 1;
        for (int j = col - 1; j >= 1; j--) {
            if (i <= this.num && array[i][j] == 1) {
                return false;
            }
            i++;
        }

        return true;
    }

    /**
     * 保存当前的布局
     */
    private void saveCurrentLayout() {
        ArrayList<Point> list = new ArrayList<Point>();
        for (int i = 1; i < array.length; i++) {
            for (int j = 1; j < array[i].length; j++) {
                if (array[i][j] == 1) {
                    list.add(new Point(i, j));
                }
            }
        }
        lists.add(list);
    }

    /**
     * 打印所有的布局(最简形式)
     */
    public void printBasicLayout() {
        int size = lists.size();
        for (int i = 0; i < size; i++) {
            ArrayList<Point> arrayList = lists.get(i);
            int size2 = arrayList.size();
            System.out.println("第" + i + "种布局!");
            for (int j = 0; j < size2; j++) {
                Point point = arrayList.get(j);
                System.out.print("(" + (int) point.getX() + ","
                        + (int) point.getY() + ")\t");
            }
            System.out.println();
        }
        System.out.println();
    }

    /**
     * 打印所有的布局(高级形式)
     */
    public void printAddvancedLayout() {
        int size = advancedLists.size();
        for (int i = 0; i < size; i++) {
            int[][] arr = advancedLists.get(i);
            System.out.println("第" + i + "种布局!");
            for (int j = 1; j <= num; j++) {
                for (int k = 1; k <= num; k++) {
                    System.out.print(arr[j][k] + "\t");
                }
                System.out.println();
            }
            System.out.println();
        }
        System.out.println();
    }

    /**
     * 排序是为了,减少抖动,即每次变换布局时,近可能少地换棋子 (每次切换到下一个布局时,棋子的变换尽可能少,视觉上棋子在有规律的移动)
     */
    public void sort() {
        sortEveryList();
    }

    private void sortEveryList() {
        /*
         * System.out.println("冒泡排序之前:"); printAllLayout();
         */
        int size = lists.size();
        // 对lists中的每个链表,按照点的纵坐标排序
        for (int q = 0; q < size; q++) {

            ArrayList<Point> arraylist = lists.get(q);

            int size2 = arraylist.size();
            // 冒泡排序
            for (int r = 1; r < size2; r++) {
                // 纵坐标从小到大
                for (int s = 0; s < size2 - r; s++) {
                    Point first = arraylist.get(s);
                    double m = first.getY();

                    Point second = arraylist.get(s + 1);
                    double n = second.getY();

                    if (m > n) {
                        arraylist.set(s + 1, first);
                        arraylist.set(s, second);
                    }

                }
            }
        }

    }

    private void initAdvancedLists() {
        int size = lists.size();
        for (int index = 0; index < size; index++) {
            ArrayList<Point> list = lists.get(index);
            int[][] arr = new int[num + 1][num + 1];

            int len = list.size();
            for (int i = 0; i < len; i++) {
                int x = (int) list.get(i).getY();
                int y = (int) list.get(i).getX();
                arr[x][y] = 1;
            }

            advancedLists.add(arr);
        }
    }

    public int[][] getArray() {
        return array;
    }

    public int getNum() {
        return num;
    }

    public List<ArrayList<Point>> getLists() {
        return lists;
    }

    public List<int[][]> getAdvancedLists() {
        return advancedLists;
    }

    public static void main(String[] args) {
        EmpressModel em4 = new EmpressModel(4);
        em4.initAllLayout();
        em4.printBasicLayout();
        // 初始化高级保存需要的布局
        //em4.initAdvancedLists();
        em4.printAddvancedLayout();

    }

}


 

设计思想

算法(模型)和界面相分离。

算法构造数据,界面展示数据。

展示分2种:中国象棋棋盘中和控制台中。

源码出处

本算法源码摘自 http://blog.csdn.net/fansunion/article/details/11787413

中国象棋程序-源码,扩展应用模块--N皇后

原文参见:http://FansUnion.cn/articles/2684

© 著作权归作者所有

FansUnion
粉丝 60
博文 858
码字总数 825464
作品 0
丰台
高级程序员
私信 提问
小朋友学经典算法(14):回溯法和八皇后问题

一、回溯法 回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不...

海天一树X
2018/10/09
0
0
hdu 2553 n皇后问题

N皇后问题Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 21779 Accepted Submission(s): 9744 Problem Description 在N*N的方格......

singular__point
2017/03/08
0
0
回溯算法思想与八皇后问题解的个数

八皇后问题: 在88的国际象棋棋盘上,皇后是威力较大的棋子,它可以攻击到与自己同行、同列以及同一斜线上的棋子,如下图,所有橙色格子上的棋子,都可能会被皇后攻击: 而八皇后问题就是在8...

silenceyawen
2018/03/04
24
0
递归算法及经典递归例子代码实现

一、什么叫做递归? 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法; 递归函数就是直接或间接调用自身的函数,也就是自身调用自己; 二、一般什么时候使用递归? 递归时常用...

ikownyou
2017/03/24
0
0
考研复试系列——第四节 深度优先搜索

考研复试系列——第四节 深度优先搜索 前言 dfs:if(判断条件) //在这里进行递归的退出return;for(遍历内容) //进行遍历,例如图中访问每一个满足某一条件的节点{if(判断是否访问过以及其他题...

cassiepython
2017/03/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

数据库

数据库架构 数据库架构可以分为存储文件系统和程序实例两大块,而程序实例根据不同的功能又可以分为如下小模块。 1550644570798 索引模块 常见的问题有: 为什么要使用索引 什么样的信息能成...

一只小青蛙
今天
5
0
PHP常用经典算法实现

<? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){ if ( $low <= $high){ $mid = int......

半缘修道半缘君丶
昨天
5
0
GIL 已经被杀死了么?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/8KvQemz0SWq2hw-2aBPv2Q 花下猫语: Python 中最广为人诟病的一点,大概就是它的 GIL 了。...

豌豆花下猫
昨天
6
0
git commit message form

commit message一般包括3部分:Header、Body、Footer。 <type>(<scope>):<subject>blank line<body>blank line<footer> header是必需的,body、footer可以省略。 header中type、subject......

ninjaFrog
昨天
5
0
聊聊Elasticsearch的CircuitBreakerService

序 本文主要研究一下Elasticsearch的CircuitBreakerService CircuitBreakerService elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/indices/breaker/CircuitBreakerService.ja......

go4it
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部