马踏棋盘(骑士周游问题)

问题描述

关于马踏棋盘的基本过程:国际象棋的棋盘为 8*8 的方格棋盘。现将"马"放在任意指定的方格中,按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次,最终使得"马"走遍棋盘的64个方格。

实现(没有优化)

import java.util.Arrays;

public class horse {
    private final int[][] load = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
    private int[][] chessBoard;
    private boolean[][] check;

    public horse() {
        this.chessBoard = new int[8][8];
        this.check = new boolean[8][8];
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                check[i][j] = false;
            }
        }
    }

    public boolean horseTrav(int x, int y, int count) {
        chessBoard[x][y] = count;
        check[x][y] = true;

        if (count == 64) {
            printChessBoard();
            return true;
        }

        for (int i = 0; i < 8; i++) {
            int nextX = x + load[i][0];
            int nextY = y + load[i][1];
            if (judgeNext(nextX, nextY)) {
                count++;
                boolean flag = horseTrav(nextX, nextY, count);
                if (!flag) {
                    check[nextX][nextY] = false;
                    count--;
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean judgeNext(int x, int y) {
        if (x >= 8 || x < 0 || y >= 8 || y < 0 || check[x][y]) {
            return false;
        }
        return true;
    }

    private void printChessBoard() {
        for (int[] arr : chessBoard) {
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        horse h = new horse();
        long start = System.currentTimeMillis();
        h.horseTrav(0, 0, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时:" + (end - start) + "ms");
    }
}

结果

捕获.PNG

贪心优化后

代码:

public class horse {
    private final int[][] load = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};  //马下一步的方向
    private int[][] chessBoard;

    public horse() {
        this.chessBoard = new int[8][8];
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                chessBoard[i][j] = 0;
            }
        }
    }

    public void horseTrav(int x, int y, int count) {

        //64个格子都走过,退出,打印棋盘
        if (count == 64) {
            printChessBoard();
            return;
        }

        //判断当前位置是否能走
        if (!judgeNext(x, y)) {
            return;
        }

        count++;
        chessBoard[x][y] = count;

        /**
         * 贪心算法,记录下一个可走位置的可走步数,将步数最少的可走位置作为下一步的位置
         * 网上的解释是:“选择最难走的路,才能走的远”
         * 这边个人理解为,有些位置的下一步很少,如果不先遍历它的话以后可能会很难遍历到它。
         * 甚至极端一点的情况是,如果现在不遍历它,以后都遍历不到了。遍历不成功的时候只能回溯,一直回溯到此刻的点,然后选了这个点以后才能完成,这就浪费了大量的时间。
         */
        int[] next = {-1, -1, -1, -1, -1, -1, -1, -1};
        for (int i = 0; i < 8; i++) {
            int x_next = x + load[i][0];
            int y_next = y + load[i][1];
            if (judgeNext(x_next, y_next)) {
                next[i]++;
                for (int j = 0; j < 8; j++) {
                    int m_next_next = x_next + load[j][0];
                    int n_next_next = y_next + load[j][1];
                    if (judgeNext(m_next_next, n_next_next))
                        next[i]++;
                }
            }
        }

        int direct = 0; //记录下一步的方向
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 8; i++) {
            if(next[i] != -1 && next[i] < min){
                min = next[i];
                direct = i;
            }
        }

        int nextX = x + load[direct][0];
        int nextY = y + load[direct][1];

        //递归,进行下一步
        horseTrav(nextX, nextY, count);

        //回溯,对应位置标记为0
        chessBoard[x][y] = 0;

    }

    private boolean judgeNext(int x, int y) {
        if (x >= 8 || x < 0 || y >= 8 || y < 0 || chessBoard[x][y] != 0) {
            return false;
        }
        return true;
    }

    private void printChessBoard() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(String.format("%2d",chessBoard[i][j]) + " ");
            }
            System.out.println(String.format("%2d",chessBoard[i][7]));
        }
    }

    public static void main(String[] args) {
        horse h = new horse();
        System.out.println("\t  递归+贪心优化");
        long start = System.currentTimeMillis();
        h.horseTrav(0, 0, 0);
        long end = System.currentTimeMillis();
        System.out.println();
        System.out.println("共耗时:" + (end - start) + "ms");

    }
}

结果
马踏棋盘递归贪心优化.PNG

# 算法  递归  回溯   

本文由 罗罗 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.lwjppz.cn /archives/20190810105020
最后更新于:2020-02-09 11:54:44

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×