1、概述：马踏棋盘问题也称为骑士周游问题，这是算法设计分析比较经典的问题之一。

2、 题目要求：这里是以国际象棋的棋盘8*8的方格棋盘，现在将“马”放在任意指定的方格的方格中，按照马走棋盘的规则将马进行移动。并且要求每个方格只能进入一次，最终让“马”走遍64个方格。

3、：编写代码： 要求使用1~64来标注马移动的路径。棋盘下图所示

要解这个算法需要用到的知识点：回溯法、深度优先搜索、递归、哈马尔顿算法。。。

4、代码段 

package com.yuanfeng.test;

/**
 * @ClassName ChessAlgorithm
 * @Description T0D0
 * @Author yuanfeng
 * @Date 2019/7/21 10:59
 * @Version 1.0
 **/
public class ChessAlgorithm {

    private static int X = 8;
    private static int Y = 8;
    private static int[][] chess = new int[X][Y];//定义一个棋盘
    private static int x2;
    private static int y2;
    /*
    *
     * @Author yuanfeng
     * @Description //TODO 找到基于xy位置的下一个可走的位置
     * @Date 11:02 2019/7/21
     * @Param []
     * @return int
     **/
    public static int nextXY(int x1,int y1,int count) {
        x2 = x1;
        y2 = y1;
        switch (count) {
            //首先x轴右边移动两格肯定不能超过总的X-1的下标
            // 并且并且向上走y是必须满足大于等于0的
            // 不能超出棋盘最小的y坐标
            // 最后还需要判断这个棋盘位置是否被走过，下面同理
            case 0:
                if ((x2 + 2 <=X - 1) && (y2 - 1 >= 0) && chess[x2 + 2][y2 - 1] == 0) {
                    x2 = x2+2;
                    y2 = y2-1;
                    return 1;
                }
                break;

            case 1:
                if (x2 + 2 <= X - 1 && y2 + 1 <= Y - 1 && chess[x2 + 2][y2 + 1] == 0) {
                    x2 = x2+2;
                    y2 = y2+1;
                    return 1;
                }
                break;
            case 2:
                if (x2 + 1 <= X - 1 && y2 - 2 >= 0 && chess[x2 + 1][y2 - 2] == 0) {
                    x2 = x2+1;
                    y2 = y2-2;
                    return 1;
                }
                break;
            case 3:
                if (x2 + 1 <= X - 1 && y2 + 2 <= Y - 1 && chess[x2 + 1][y2 + 2] == 0) {
                    x2 = x2+1;
                    y2 = y2+2;
                    return 1;
                }
                break;
            case 4:
                if (x2 - 2 >= 0 && y2 - 1 >= 0 && chess[x2 - 2][y2 - 1] == 0) {
                    x2 =x2-2;
                    y2 = y2-1;
                    return 1;
                }
                break;
            case 5:
                if (x2 - 2 >= 0 && y2 + 1 <= Y - 1 && chess[x2 - 2][y2 + 1] == 0) {
                    x2 = x2-2;
                    y2 = y2+1;
                    return 1;
                }
                break;
            case 6:
                if (x2 - 1 >= 0 && y2 - 2 >= 0 && chess[x2 - 1][y2 - 2] == 0) {
                    x2 = x2-1;
                    y2 = y2-2;
                    return 1;
                }
                break;
            case 7:
                if (x2 - 1 >= 0 && y2 + 2 <= Y - 1 && chess[x2 - 1][y2 + 2] == 0) {
                    x2 = x2-1;
                    y2 = y2+2;
                    return 1;
                }
                break;

            default:
                break;
        }
        return 0;
    }

    /*
    *
     * @Author yuanfeng
     * @Description //TODO 深度优先遍历棋盘
     * (a,b)为位置坐标
     * tag是标记变量，每走一步tag+1
     * @Date 11:22 2019/7/21
     * @Param [a, b, tag]
     * @return void
     **/
    public static int travesalChessBoard(int a, int b, int tag){

        int x1 = a;
        int y1 = b;
        int flag = 0,count = 0;
        chess[a][b] = tag;
        if(X*Y == tag ){
            //打印棋盘
            printChess();
            return 1;
        }
        flag =  nextXY(x1,y1,count);

        while (flag == 0 && count < 7){
            count++;
            flag =  nextXY(x1,y1,count);
        }
        //找到马的下一个可走的坐标（x1,y1），如果找到flage = 1,否则为0
        while (flag == 1){
            if(travesalChessBoard(x1,y1,tag+1) == 1){
                return 1;
            }
            x1 = a;
            y1 = b;
            count++;
            flag =  nextXY(x1,y1,count);

            while (flag == 0 && count < 7){
                count++;
                flag = nextXY(x1,y1,count);
            }
            //继续找到马的下一步可走的坐标（x2,y2），找到flage=1
            if(flag == 0){
                chess[a][b] = 0;
            }
        }
        return 0;
    }
    //打印
    public static void printChess(){
        int i = 0;
        int j = 0;
        for (i = 0;i<X;i++){
            for (j = 0;j<Y;j++){
                System.out.print("\t"+chess[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int i,j;
        long startTime = System.currentTimeMillis();

        for (i = 0;i < X;i++) {
            for (j = 0; j < Y; j++) {
                chess[i][j] = 0;
            }
        }
        if(travesalChessBoard(2,2,1) == 0){
            System.out.println("抱歉 骑士周游失败！");
        }
        long stopTime = System.currentTimeMillis();
        System.out.println("本次计算时间耗时:"+((stopTime-startTime)/1000)+"秒");
    }

}