骑士周游回溯算法

其实周游就是说马在一个棋盘上以走斜日的方式走棋盘，不能走已经走过的，需要将这个棋盘走完，最后一步回归原点，不过我的这个没有回归原点，如果需要回归我的这个算法也只需要判断以下即可

1.判断当前是否已经到达终点

2.如果不是，列举出当前马可以走的八个方位

3.尝试第一个方位

4.如果第一个方位可以走，就回到第一步，进入下一个循环

5.如果不可以便回到2尝试下一步，知道尝试完八个方位

public class HorseChessBoardTest {
    public static void main(String[] args) {
        HorseChessBoard horseChessBoard = new HorseChessBoard(8);
        horseChessBoard.showChessBoard();
        System.out.println();
        System.out.println(horseChessBoard.goChessBoard(2,4));
        horseChessBoard.showChessBoard();


    }
}
class HorseChessBoard{
    private int count; //需要走的总步数
    private int step; //当前已经走的步数，根据这个和总部书判断是否已经完成所有步数
    private int row; //行数
    private int col; //列数，与行数相等，只是为了好分辨
    private int[][] chess; //棋盘，0代表未走的，数字代表是走的第几步
    //马站在一个位置可以踏的方向有八个，只需要用马的走遍和里面的每一个小数组相加即可，便于遍历
    private int[][] direction = {{-2,-1},{-1,-2},{-2,1},{-1,2},{1,2},{2,1},{1,-2},{2,-1}}; 

    //初始化工作
    public HorseChessBoard(int chess) {
        this.chess = new int[chess][chess];
        col = row = chess;
        count = chess*chess;
        step = 1;
    }
    public boolean goChessBoard(int x,int y){
        if(step == count && chess[x][y] == 0){//判断是否为最后一步，并且当前这一步是否合法，如果条件成立，代表走完
            chess[x][y] = step;
            return true;
        }
        boolean flag = false;
        for (int[] ints : direction) {//循环遍历八个方向
            //判断当前位置是否合法，以及下一步是否合法
            if(x > -1  && x < col && y > -1 && y < row && x + ints[0] > -1  && x + ints[0] < col && y + ints[1] > -1 && y + ints[1] < row && chess[x][y] == 0){
                chess[x][y] = step;
                step++;
                flag = goChessBoard(x + ints[0],y + ints[1]);//递归调用走下一步，并且返回结果
                if(!flag){//如果上一步不能走通进行回溯
                    chess[x][y] = 0;
                    step--;
                }else { //否则返回真
                    return true;
                }
            }
        }

        return flag;
    }
    public void showChessBoard(){ //显示棋盘
        for (int[] ints : chess) {
            for (int anInt : ints) {
                System.out.print( anInt+ "\t");
            }
            System.out.println();
        }
    }
}