我学习了《数据结构》课程中的回溯法后，然后就开始写代码来解决骑士游历问题！首先，我用的就是最简单的暴力回溯法，然后第二种方法就是使用预见性策略来优化提高效率。然后代码如下：

import java.util.*;

/**
 * Created by clearbug on 2018/2/26.
 */
public class Solution {

    class TwoIntMap {
        private int next;
        private int nextAvailable;

        public TwoIntMap(int next, int nextAvailable) {
            this.next = next;
            this.nextAvailable = nextAvailable;
        }

        public int getNext() {
            return next;
        }

        public void setNext(int next) {
            this.next = next;
        }

        public int getNextAvailable() {
            return nextAvailable;
        }

        public void setNextAvailable(int nextAvailable) {
            this.nextAvailable = nextAvailable;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();

        for (int i = 5; i < 9; i++) {
            System.out.println(i + "================================================================================");
            long startTime = System.currentTimeMillis();
            List<String> res = s.traverse(i, 0, 0);
            for (String line : res) {
                System.out.println(line);
            }
            long endTime = System.currentTimeMillis();
            System.out.println("traverse 运行耗时：" + (endTime - startTime) + " ms");

            long startTime2 = System.currentTimeMillis();
            List<String> res2 = s.traverse2(i, 0, 0);
            for (String line : res2) {
                System.out.println(line);
            }
            long endTime2 = System.currentTimeMillis();
            System.out.println("traverse2 运行耗时：" + (endTime2 - startTime2) + " ms");
        }
    }

    public List<String> traverse(int N, int sr, int sc) {
        int[][] board = new int[N][N];
        board[sr][sc] = 1;

        List<String> res = new ArrayList<>();
        dfs(board, sr, sc, res);
        return res;
    }

    public List<String> traverse2(int N, int sr, int sc) {
        int[][] board = new int[N][N];
        board[sr][sc] = 1;

        List<String> res = new ArrayList<>();
        dfs2(board, sr, sc, res);
        return res;
    }

    private boolean dfs(int[][] board, int sr, int sc, List<String> res) {
        if (check(board)) {
            for (int i = 0; i < board.length; i++) {
                res.add(Arrays.toString(board[i]));
            }
            return true;
        }

        int[] dr = {2, 2, -2, -2, 1, 1, -1, -1};
        int[] dc = {1, -1, 1, -1, 2, -2, 2, -2};

        for (int i = 0; i < 8; i++) {
            int[][] newBoard = deepthCopy(board);
            int cr = sr + dr[i];
            int cc = sc + dc[i];
            if (cr >= 0 && cr < board.length && cc >= 0 && cc < board.length && board[cr][cc] == 0) {
                newBoard[cr][cc] = newBoard[sr][sc] + 1;
                if (dfs(newBoard, cr, cc, res)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean dfs2(int[][] board, int sr, int sc, List<String> res) {
        if (check(board)) {
            for (int i = 0; i < board.length; i++) {
                res.add(Arrays.toString(board[i]));
            }
            return true;
        }

        int[] dr = {2, 2, -2, -2, 1, 1, -1, -1};
        int[] dc = {1, -1, 1, -1, 2, -2, 2, -2};

        List<TwoIntMap> twoIntMaps = new ArrayList<>();

        for (int i = 0; i < 8; i++) {
            int[][] newBoard = deepthCopy(board);
            int cr = sr + dr[i];
            int cc = sc + dc[i];
            if (cr >= 0 && cr < board.length && cc >= 0 && cc < board.length && board[cr][cc] == 0) {
                newBoard[cr][cc] = newBoard[sr][sc] + 1;
                twoIntMaps.add(new TwoIntMap(i, nextStepAvailableDirection(newBoard, cr, cc)));
            }
        }

        twoIntMaps.sort(Comparator.comparingInt(TwoIntMap::getNextAvailable));
        for (TwoIntMap twoIntMap : twoIntMaps) {
            int[][] newBoard = deepthCopy(board);
            int cr = sr + dr[twoIntMap.getNext()];
            int cc = sc + dc[twoIntMap.getNext()];
            newBoard[cr][cc] = newBoard[sr][sc] + 1;
            if (dfs2(newBoard, cr, cc, res)) {
                return true;
            }

        }

        return false;
    }

    private int[][] deepthCopy(int[][] board) {
        int[][] res = new int[board.length][board.length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                res[i][j] = board[i][j];
            }
        }
        return res;
    }

    private boolean check(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private int nextStepAvailableDirection(int[][] board, int sr, int sc) {
        int res = 0;

        int[] dr = {2, 2, -2, -2, 1, 1, -1, -1};
        int[] dc = {1, -1, 1, -1, 2, -2, 2, -2};

        for (int i = 0; i < 8; i++) {
            int cr = sr + dr[i];
            int cc = sc + dc[i];
            if (cr >= 0 && cr < board.length && cc >= 0 && cc < board.length && board[cr][cc] == 0) {
                res++;
            }
        }

        return res;
    }

}

然后我在 for 循环里面通过设置不同的棋盘大小来测试两种实现的耗费时间，运行结果如下：

5================================================================================
[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]
traverse 运行耗时：221 ms
[1, 22, 11, 16, 7]
[12, 17, 8, 21, 10]
[25, 2, 23, 6, 15]
[18, 13, 4, 9, 20]
[3, 24, 19, 14, 5]
traverse2 运行耗时：55 ms
6================================================================================
[1, 12, 21, 28, 7, 10]
[22, 29, 8, 11, 20, 27]
[13, 2, 23, 4, 9, 6]
[30, 35, 32, 17, 26, 19]
[33, 14, 3, 24, 5, 16]
[36, 31, 34, 15, 18, 25]
traverse 运行耗时：6634 ms
[1, 10, 31, 20, 7, 12]
[32, 19, 8, 11, 30, 21]
[9, 2, 25, 36, 13, 6]
[18, 33, 16, 27, 22, 29]
[3, 26, 35, 24, 5, 14]
[34, 17, 4, 15, 28, 23]
traverse2 运行耗时：1 ms
7================================================================================
[1, 28, 37, 40, 25, 30, 9]
[38, 41, 26, 29, 10, 35, 24]
[27, 2, 39, 36, 23, 8, 31]
[42, 19, 44, 17, 32, 11, 34]
[45, 48, 3, 22, 5, 14, 7]
[20, 43, 18, 47, 16, 33, 12]
[49, 46, 21, 4, 13, 6, 15]
traverse 运行耗时：470 ms
[1, 30, 11, 46, 27, 32, 9]
[12, 45, 28, 31, 10, 37, 26]
[29, 2, 49, 38, 47, 8, 33]
[42, 13, 44, 19, 34, 25, 36]
[3, 16, 41, 48, 39, 22, 7]
[14, 43, 18, 5, 20, 35, 24]
[17, 4, 15, 40, 23, 6, 21]
traverse2 运行耗时：1 ms
8================================================================================

现在的问题是，当 i = 8 时，第一种暴力回溯实现方法运行了几天了都没运算出结果来。所以我想问下是因为我的实现有问题吗（但是从输出上看 i= 5, 6, 7 时是正常输出的）？还是说当 i = 8 时，暴力回溯方法所要遍历的路径太多，真的是需要好久好久才能完成呢？