骑士游历算法

一、具体问题

​ 在一个 n x n 的棋盘上，骑士在任一顶点按照 “日” 字开始游历，要求骑士游历棋盘的每一个顶点且每一个顶点只游历一次，输出骑士的游历路径。

二、回溯算法

这道题的解法类似于八皇后问题，这里我们采用回溯算法。

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

三、Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Solution {

    static final int[] xMove= {2,1,-1,-2,-2,-1,1,2};
    static final int[] yMove= {-1,-2,-2,-1,1,2,2,1};
    public final ArrayList<int[][]> ways = new ArrayList<>();

    public void solveKnightTravel() {
        int weight=0; 
        //权重值代表第几步走到该位置；
        int count=0; 
        //完全遍历的解数；
        int countFail=0; 
        //失败尝试次数
        int x = 0;
        int y = 0;
        System.out.println("初始位置：（"+(y+1)+"，"+(5-x)+"）");
        int[][] A=new int[5][5];
        ArrayList<Boolean> resList=new ArrayList<>();  
        //存储无法继续走时棋盘的状态（false或true，true代表遍历完成）
        knightJump(A,x,y,resList,weight);
        count=Collections.frequency(resList, true);
        countFail=Collections.frequency(resList, false);
        System.out.println("一共有"+count+"种不同的遍历方法");
        System.out.println("一共有"+countFail+"次失败的尝试");
    }

    public void knightJump(int[][] A, int row, int col,ArrayList<Boolean> resList,int weight){
        boolean sign=false;  
        //遍历完成标志
        if(!displacable(A,row,col)) {  
            //若该位置可走
            weight++;
            A[row][col]=weight;
            if(nowhereCanGo(A,row,col)) { 
                //走到无路可走时，绘出棋盘的状态图，并检测是否完成
                if(traverseCompleted(A)) {
                    sign= true;
                    printBoard(A);
                    getWay(A);
                    System.out.println("=======================");
                }
                resList.add(sign);
            }
            for(int k=0;k<8;k++) {    
                //走下一步
                int nextRow=row+xMove[k];
                int nextCol=col+yMove[k];
                if (nextRow<0 || nextRow>=A.length || nextCol<0 || nextCol>=A[0].length) {
                    continue;
                }
                knightJump(A,nextRow,nextCol,resList,weight);
            }
            A[row][col]=0; 
            //回溯的操作，来到这里说明该位置下一步不可走，于是将该位置置0并减少权重，也就是说上一步不选择走此处，而去尝试下一个位置
            weight--;
        }
    }

    public boolean nowhereCanGo(int[][] A, int row, int col) {   
        //检测该位置是否无处可走
        boolean res=true;
        for(int i=0;i<8;i++) {
            res=res&&displacable(A,row+xMove[i],col+yMove[i]);
        }
        return res;
    }

    public boolean displacable(int[][] A,int row,int col) {       
        //检测该位置能否放置
        if(!(row>=0&&row<A.length&&col>=0&&col<A[0].length&&A[row][col]==0))
            return true;
        else
            return false;
    }

    public void printBoard(int[][] A) {         
        //无法继续行走时画出棋盘
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A[0].length; j++) {
                if (A[i][j] < 10) {
                    System.out.print(" " + A[i][j]);
                } else
                    System.out.print(A[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public boolean traverseCompleted(int[][] A) {     
        //通过图总权重数判断是否完成了遍历
        int sum=0;
        for(int i=0;i<A.length;i++)
            for(int j=0;j<A[0].length;j++)
                sum+=A[i][j];
        if(sum==(1+A.length*A[0].length)*A.length*A[0].length/2)   //如果sum=1+2+...+N*M,则完成遍历
            return true;
        else
            return false;
    }

    public int[][] getWay(int[][] A){      
        //通过二维数组生成游历路径
        int[][] way = new int[25][2];
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A[i].length; j++) {
                way[A[i][j]-1][0] = i;
                way[A[i][j]-1][1] = j;
            }
        }
        ways.add(way);
        return way;
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        solution.solveKnightTravel();
        System.out.println(Arrays.deepToString(solution.ways.get(0)));
    }
}

四、运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
初始位置：（1，5）
 1 10  5 16 25 
 4 17  2 11  6 
 9 20 13 24 15 
18  3 22  7 12 
21  8 19 14 23 
=======================
...
 1  6 15 10 21 
14  9 20  5 16 
19  2  7 22 11 
 8 13 24 17  4 
25 18  3 12 23 
=======================
一共有304种不同的遍历方法
一共有625004次失败的尝试
[[0, 0], [1, 2], [3, 1], [1, 0], [0, 2], [1, 4], [3, 3], [4, 1], [2, 0], [0, 1], [1, 3], [3, 4], [2, 2], [4, 3], [2, 4], [0, 3], [1, 1], [3, 0], [4, 2], [2, 1], [4, 0], [3, 2], [4, 4], [2, 3], [0, 4]]

Process finished with exit code 0