文档章节

棋盘法的一个应用

l
 ljl160139
发布于 2017/07/03 16:54
字数 1103
阅读 50
收藏 0

                                 棋盘法的一个应用

    一道逻辑思维的数学题。题目是这样:不过下图的黑点,把所有的圆圈链接起来,不可斜着连,不可跳连。在琢磨很久以后发现不跳着链接是不会有答案的,下面用代码验证这道题。在验证过程中棋盘法每走一步是否可以演变为人工智能的某个节点,每个节点可以处理不同的逻辑。对人工智能神经节点最初步的思考

 

  0      1       2     3      4 

  5      6       7      8      9 

  10    11     12    13    14 

  15    16     17    18    19

  20    21    22     23    24 

   思路:使用棋盘方式解决问题,把每个圆圈当做一个棋,每个棋子的下一步有上下左右4个方向可以选择,有些棋子左边没有棋子,有些棋子右边没有棋子,有些棋子上边没有棋子,有些棋子下面没有棋子;棋子下一步的走法取决于上下左右是否有棋子,并且没有走过该棋子,如果不能走下一步则证明这次的连接流程已经走完。思路很简单,我们给每个棋子做一个编号(0-24),每个棋子下一步的优先顺序是左上右下(比如12号棋子下一步走的顺序为:12->11,12->7,12->13,12->17),下面从代码角度实现,使用java编写:

棋子类:棋子的周围有上下左右棋子,以及默认的黑点棋子标记,棋子的编号等属性

private int chessNo;
private boolean marked;  //黑点标记,不可连
private ChessPiece left;
private ChessPiece top;
private ChessPiece right;
private ChessPiece bottom;

生成棋子:

public static List<ChessPiece> getChesses() {
    List<ChessPiece> result = new ArrayList<>();
    for (int i = 0; i < COLUMNS * LINES; i++) {
        ChessPiece chessPiece = new ChessPiece();
        chessPiece.setChessNo(i);
        if (i == MARKED_CP) {   //标记的黑点棋子
            chessPiece.setMarked(true);
        }
        result.add(chessPiece);
    }
    return result;
}

生成棋盘:

public static List<ChessPiece> getChessBoard(List<ChessPiece> data) {
    for (int i = 0; i < data.size(); i++) {
        int left = i - 1;
        int top = i - COLUMNS;
        int right = i + 1;
        int bottom = i + COLUMNS;
        if (i % COLUMNS > 0) {
            data.get(i).setLeft(data.get(left));
        }
        if (i % COLUMNS != LINES - 1) {
            data.get(i).setRight(data.get(right));
        }
        if (top >= 0) {
            data.get(i).setTop(data.get(top));
        }
        if (bottom < data.size()) {
            data.get(i).setBottom(data.get(bottom));
        }
        System.out.println("chess--" + data.get(i).getChessNo() +
                "  left=" + (data.get(i).getLeft() == null ? "-" : data.get(i).getLeft().getChessNo() + "") +
                "  top=" + (data.get(i).getTop() == null ? "-" : data.get(i).getTop().getChessNo() + "") +
                "  right" + (data.get(i).getRight() == null ? "-" : data.get(i).getRight().getChessNo() + "") +
                "  bottom" + (data.get(i).getBottom() == null ? "-" : data.get(i).getBottom().getChessNo() + "")
        );
    }
    return data;
}

每个棋子可能是起始点,开始寻找路径:

public static void findPath(List<ChessPiece> data) {
    for (int i = 0; i < data.size(); i++) {
        if(!data.get(i).isMarked()){
            goNext(data.get(i), new ArrayList<>());
        }
    }

    Collections.sort(pathList, new Comparator<List<ChessPiece>>() {//做一把排序,将走的最多的步数排在最前面
        @Override
        public int compare(List<ChessPiece> o1, List<ChessPiece> o2) {
            return o2.size()-o1.size();
        }
    });


    for(int i=0;i<200;i++){
        String path = "";
        List<ChessPiece> list=pathList.get(i);
        for (int j = 0; j < list.size(); j++) {
            path += list.get(j).getChessNo() + "  ";
        }
        System.out.println(path);
    }
    System.out.println("pathList size---" + pathList.size());
}

棋子的走位:

private static void goNext(ChessPiece piece, List<ChessPiece> parentSteps) {
    List<ChessPiece> curSteps = new ArrayList<>();
    curSteps.addAll(parentSteps);
    if (null != piece) {
        curSteps.add(piece);
        boolean hasNext=false;
        if(null!=piece.getLeft()&&!curSteps.contains(piece.getLeft())&&!piece.getLeft().isMarked()){
            hasNext=true;
            goNext(piece.getLeft(), curSteps);
        }
        if(null!=piece.getTop()&&!curSteps.contains(piece.getTop())&&!piece.getTop().isMarked()){
            hasNext=true;
            goNext(piece.getTop(), curSteps);
        }
        if(null!=piece.getRight()&&!curSteps.contains(piece.getRight())&&!piece.getRight().isMarked()){
            hasNext=true;
            goNext(piece.getRight(), curSteps);
        }
        if(null!=piece.getBottom()&&!curSteps.contains(piece.getBottom())&&!piece.getBottom().isMarked()){
            hasNext=true;
            goNext(piece.getBottom(), curSteps);
        }
        if(!hasNext){
            pathList.add(curSteps);
        }
    }
}

最多只能走23步,总存在一个点连接不到,结果如下:

0  5  6  7  2  3  4  9  8  13  12  11  10  15  16  17  18  19  24  23  22  21  20    //左上右下顺序
0  5  6  7  2  3  4  9  8  13  12  11  10  15  16  21  22  17  18  23  24  19  14  
0  5  6  7  2  3  4  9  8  13  12  11  10  15  20  21  16  17  18  19  24  23  22  
0  5  6  7  2  3  4  9  8  13  12  11  10  15  20  21  16  17  18  23  24  19  14  
0  5  6  7  2  3  4  9  8  13  12  11  10  15  20  21  16  17  22  23  18  19  14  
0  5  6  7  2  3  4  9  8  13  12  11  10  15  20  21  16  17  22  23  18  19  24  
0  5  6  7  2  3  4  9  8  13  12  11  10  15  20  21  16  17  22  23  24  19  18  
0  5  6  7  2  3  4  9  8  13  12  11  10  15  20  21  16  17  22  23  24  19  14  
0  5  6  7  2  3  4  9  8  13  12  11  10  15  20  21  22  17  18  23  24  19  14  
0  5  6  7  2  3  4  9  8  13  12  11  10  15  20  21  22  23  24  19  18  17  16  

总结:这种棋盘的走法,实现方式还有很多;每个棋子是否可以有自己的走势方向,是否可以根据前面的走法来判断当前棋子的走法等等。

项目地址:https://github.com/ljl160139/ChessAtric

© 著作权归作者所有

l
粉丝 1
博文 5
码字总数 2363
作品 0
福州
私信 提问
java 实现棋盘覆盖问题

问题描述:在一个2k2k的棋盘中,有一个特殊方格,要求用L型骨牌覆盖满除特殊方格外的所有其他方格,且骨牌不得重叠.(骨牌可以旋转放置) 输入:棋盘的边长、特殊方格坐标 输出:骨牌放法.其...

silenceyawen
2016/03/31
670
0
棋盘游戏走完k步还能留在棋盘上的概率

Knight Probability in Chessboard 问题: On an x chessboard, a knight starts at the -th row and -th column and attempts to make exactly moves. The rows and columns are 0 indexed......

叶枫啦啦
2018/01/15
40
0
人工智能:博弈--人机中国象棋

为了应付某人的毕设,研究过一段时间的人机象棋,现来谈谈详细的算法思路和流程。 注:本文没有任何干货源码,写过二层遍历、基本评价函数与所谓“深度学习”算法下的人机象棋,棋力之弱小,...

执契
2018/11/10
0
0
分治策略

分治策略 本文包括 分治的基本概念 二分查找 快速排序 归并排序 找出伪币 棋盘覆盖 最大子数组 源码链接:https://github.com/edisonleolhl/DataStructure-Algorithm/tree/master/Divede-an...

廖少少
2017/09/14
0
0
N皇后问题的求解过程

无解 最初接触N皇后问题,对于N皇后问题所牵涉的回溯算法一概不知,大脑处于混沌状态。 穷举法 使用穷举法,先把N皇后在棋盘上的排布的所有情况都列举出来,通过递归程序实现,再定义一个判断...

关山月朦胧
2016/10/30
16
0

没有更多内容

加载失败,请刷新页面

加载更多

java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
35分钟前
4
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
4
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
13
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
13
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部