`
橡树心
  • 浏览: 46349 次
  • 性别: Icon_minigender_1
  • 来自: 济南
社区版块
存档分类
最新评论

骑士走棋盘(Knight tour)

阅读更多
问题说明:

骑士游戏,在十八世纪倍受数学家与拼图迷的注意,骑士的走法为西洋棋的走发,骑士可以由任何一个位置出发,它要如何走完所有的位置。
public class Knight {
    public boolean travel(int startX, 
                          int startY, int[][] board) {
        // 对应骑士可以走的八个方向
        int[] ktmove1 = {-2, -1, 1, 2, 2, 1, -1, -2};
        int[] ktmove2 = {1, 2, 2, 1, -1, -2, -2, -1};
        
        // 下一个出路的位置         int[] nexti = new int[board.length];
        int[] nextj = new int[board.length];
        
        // 记录出路的个数
        int[] exists = new int[board.length];
        
        int x = startX;
        int y = startY;
        
        board[x][y] = 1;
        
        for(int m = 2; m <= Math.pow(board.length, 2); m++) {
            for(int k = 0; k < board.length; k++) {
                exists[k] = 0;
            }
            
            int count = 0;
            // 试探八个方向
            for(int k = 0; k < board.length; k++) {
                int tmpi = x + ktmove1[k];
                int tmpj = y + ktmove2[k];
                
                // 如果是边界,不可以走
                if(tmpi < 0 || tmpj < 0 || 
                   tmpi > 7 || tmpj > 7) {
                    continue;
                }
                
                // 如果这个方向可以走,记录下来
                if(board[tmpi][tmpj] == 0) {
                    nexti[count] = tmpi;
                    nextj[count] = tmpj;
                    // 可走的方向加一个
                    count++;
                }
            }
            
            int min = -1;
            if(count == 0) {
                return false;
            }
            else if(count == 1) {
                min = 0;
            }
            else {
                // 找出下个位置的出路数
                for(int l = 0; l < count; l++) {
                    for(int k = 0; k < board.length; k++) {
                        int tmpi = nexti[l] + ktmove1[k];
                        int tmpj = nextj[l] + ktmove2[k];

                        if(tmpi < 0 || tmpj < 0 || 
                           tmpi > 7 || tmpj > 7) {
                            continue;
                        }

                        if(board[tmpi][tmpj] == 0)
                            exists[l]++;
                    }
                }

                int tmp = exists[0];
                min = 0;

                // 从可走的方向寻找最少出路的方向
                for(int l = 1; l < count; l++) {
                    if(exists[l] < tmp) {
                        tmp = exists[l];
                        min = l;
                    }
                }
            }
            
            // 走最少出路的方向
            x = nexti[min];
            y = nextj[min];
            board[x][y] = m;
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        int[][] board = new int[8][8];
        Knight knight = new Knight();
        
        if(knight.travel(
                Integer.parseInt(args[0]), 
                Integer.parseInt(args[1]), board)) {
            System.out.println("走棋完成!");
        }
        else {
            System.out.println("走棋失败!");
        }
        
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(board[i][j] < 10) {
                    System.out.print(" " + board[i][j]);
                }
                else {
                    System.out.print(board[i][j]);
                }
                System.out.print(" ");
            }
            System.out.println();
        }
    }
}

分享到:
评论

相关推荐

    C经典算法之骑士走棋盘

    骑士旅游(Knight tour)在十八世纪初倍受数学家与拼图迷的注意,它什么时候被提出已不可考,骑士的走法为西洋棋的走法,骑士可以由任一个位置出发,它要如何走完[所有的位置?

    qishi.rar_knight_knight tour_骑士巡游

    国际象棋游戏一个经典的例子就是骑士巡游(knight s tour)问题,这个问题要求从棋盘上任意给定的方格开始移动骑士,相继地到达所有的64个方格,进入每个方格一次且仅进入一次。通常情况下,我们用如下方法表示一个...

    C# 骑士走棋盘

    可以算做非常经典的算法了,骑士的走法,基本上可以使用递回来解决,但是纯綷的递回在维度大时相当没有效率,比较聪明的解法由J.C. Warnsdorff在1823年提出,简单的说,先将最难的位置走完,接下来的路就宽广了,...

    骑士漫游堆栈遍历棋盘

    骑士漫游,运用堆栈采用回溯法遍历棋盘所有位置,没有重复路线。

    骑士周游列国问题

    骑士周游列国问题(Knight’s Tour Problem)又称跳马问题,马踏棋盘问题,或骑士漫游问题。在一张国际象棋棋盘上(8*8方格),骑士(knight,马)位于任意一个位置。问如何才能让骑士不重不漏的经过棋盘上的每个格...

    马踏棋盘 骑士走方格

    国际象棋遍历:国际象棋的马或者骑士,在棋盘上面走日子,任意输入起始位置,输出遍历矩阵

    递归算法实现骑士遍历棋盘问题

    用递归算法是实现骑士遍历棋盘问题!!c++语言实现

    马走棋盘的实现

    马走棋盘的实现。用递归实现的。通过递归实现了马走棋盘

    Knight Moves

    Your task is to write a program to calculate the minimum number of moves移动次数 needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov. ...

    数据结构课程设计—骑士漫游(马踏棋盘)

    问题描述:将马随机放在国际象棋的 8X8 棋盘中的某个方格中,马按走棋规则进行移动。要求每个方格上只进入一次,走遍棋盘上全部 64 个方格。编制递归程序,求出马的行走路线 ,并按求出的行走路线,将数字 1,2,…,...

    骑士周游列国回溯递归解法

    在一张国际象棋棋盘上(8*8方格),骑士(knight,马)位于任意一个位置。问如何才能让骑士不重不漏的经过棋盘上的每个格?本问题中已知骑士位置(m,n),其中0=,n,要求给出骑士行走路径,路径可用8*8矩阵输出,其中...

    数据结构实习2.4马踏棋盘/骑士游历/马的周游/Knight

    实习 2.4 马踏棋盘 C++编写, DEV_C++ 编译器下运行通过 PS: 启发式搜索,非递归实现. 应付作业,实用价值一点点... 同时赚资源分 PS PS: 比较经典的题目,不是太过无聊,不过一般都是递归搞定就OK了,理解栈的意义就...

    国际象棋马走棋盘问题

    国际象棋马走棋盘:在棋盘中任意选择一个位置,找出一条遍历棋盘的路径.

    国际象棋中的马走棋盘问题

    国际象棋马走棋盘:选择棋盘上的某个位置,找出一条遍历路径.

    马踏棋盘又名骑士漫游问题

    问题描述:将马随机放在国际象棋的 8X8 棋盘中的某个方格中 马按走棋规则进行移动 要求每个方格上只进入一次 走遍棋盘上全部 64 个方格 编制递归程序 求出马的行走路线 并按求出的行走路线 将数字 1 2 … 64 依次填入...

    JAVA实现骑士巡游(马踏棋盘)

    JAVA实现骑士巡游(马踏棋盘) 8X8格 输入起始X轴Y轴坐标

    关于马走日棋盘搜索算法

    实现马走日的搜索算法,VC++6.0 和window XP系统下调试通过的

    马走棋盘 c++代码

    一个简单的数据结构问题,马走遍整个棋盘的C++小程序代码

    马走日棋盘算法.doc

    马走日棋盘算法.doc

    骑士游历问题

    骑士游历问题,算法设计与分析,骑士游历问题

Global site tag (gtag.js) - Google Analytics