java怎么實(shí)現(xiàn)馬踏棋盤(pán)算法

本篇內(nèi)容介紹了“java怎么實(shí)現(xiàn)馬踏棋盤(pán)算法”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

馬踏棋盤(pán)或騎士周游問(wèn)題

1、馬踏棋盤(pán)算法也被稱為騎士周游問(wèn)題
2、將馬隨機(jī)放在國(guó)際象棋的 8×8 棋盤(pán) Board[0～7][0～7]的某個(gè)方格中，馬按走棋規(guī)則(馬走日字)進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤(pán)上全部 64 個(gè)方格

思路

會(huì)使用到深度優(yōu)先思想和類(lèi)似迷宮問(wèn)題的尋路策略問(wèn)題，和八皇后問(wèn)題也有相似。

1、用一個(gè)二維數(shù)組建立整張棋盤(pán)。用另外一個(gè)二維數(shù)組保存棋盤(pán)的每一個(gè)位置是否走過(guò)
2、馬在棋盤(pán)上有一個(gè)初始位置，將這個(gè)位置設(shè)為已走過(guò)，并將步數(shù)設(shè)為1.
3、獲得在這個(gè)位置上，馬下一步能走的位置集合。
4、遍歷集合里的所有位置，如果那個(gè)位置沒(méi)走過(guò)，下一步（步數(shù)+1）就走它（遞歸）
5、設(shè)置遞歸結(jié)束的標(biāo)志.用一個(gè)布爾變量標(biāo)志游戲是否成功。當(dāng)游戲成功時(shí)，步數(shù)應(yīng)該等于棋盤(pán)格子數(shù)。假如某一次，馬走完了所有能走的下一步位置，步數(shù)還小于棋盤(pán)格子數(shù)并且還沒(méi)成功，說(shuō)明這個(gè)位置不能成功的完成游戲，就把這個(gè)位置恢復(fù)原樣（棋盤(pán)設(shè)為0，設(shè)為未走過(guò)），接下來(lái)的遞歸會(huì)重新去尋找合適的路。如果步數(shù)等于棋盤(pán)總格子數(shù)，說(shuō)明游戲成功，把標(biāo)志的布爾變量設(shè)為true，這樣在層層返回時(shí)就不會(huì)再進(jìn)入上面的條件，遞歸就會(huì)逐漸結(jié)束而不會(huì)深入下去。

涉及到的方法：

根據(jù)此時(shí)的位置，判斷馬接下來(lái)能走的位置集合。
x的值代表列而y的值代表行
馬是按照日字走的，所有當(dāng)它在中間時(shí)最多有8種位置可以走，一 一判斷那個(gè)位置是否超過(guò)棋盤(pán)邊界。
每種可能都是if，而不是if-else if，因?yàn)橐@得所有的可能性，而不是找出一個(gè)
假如list時(shí)一定要新建一個(gè)坐標(biāo)，不能使用同一個(gè)，不然值就會(huì)互相影響

/**
     * 根據(jù)現(xiàn)在的坐標(biāo)返回可以走的坐標(biāo) x列y行
     *
     * @param current
     * @return
     */
    public static ArrayList<Point> findWay(Point current) {
        ArrayList<Point> res = new ArrayList<>();
        //可以走的坐標(biāo)
        Point p = new Point();
        //5
        if ((p.x = current.x - 2) >= 0 && (p.y = current.y - 1) >= 0) {
            res.add(new Point(p));
        }
        //6
        if ((p.x = current.x - 1) >= 0 && (p.y = current.y - 2) >= 0) {
            res.add(new Point(p));
        }
        //7
        if ((p.x = current.x + 1) < X && (p.y = current.y - 2) >= 0) {
            res.add(new Point(p));
        }
        //0
        if ((p.x = current.x + 2) < X && (p.y = current.y - 1) >= 0) {
            res.add(new Point(p));
        }
        //1
        if ((p.x = current.x + 2) < X && (p.y = current.y + 1) < Y) {
            res.add(new Point(p));
        }
        //2
        if ((p.x = current.x + 1) < X && (p.y = current.y + 2) < Y) {
            res.add(new Point(p));
        }
        //3
        if ((p.x = current.x - 1) >= 0 && (p.y = current.y + 2) < Y) {
            res.add(new Point(p));
        }
        //4
        if ((p.x = current.x - 2) >= 0 && (p.y = current.y + 1) < Y) {
            res.add(new Point(p));
        }
        return res;
    }

馬塔棋盤(pán)

不能單純以step < X * Y來(lái)判斷是否完成游戲，因?yàn)檫f歸回溯時(shí)步數(shù)也會(huì)回溯，所以要設(shè)置一個(gè)變量

 /**
     * 馬踏棋盤(pán)算法
     *
     * @param chess 棋盤(pán)
     * @param row   坐標(biāo)行
     * @param col   坐標(biāo)列
     * @param step  步數(shù)
     */
    public static void traversalChessboard(int[][] chess, int row, int col, int step) {
        //先走一步
        chess[row][col] = step;
        visit[row][col] = true;
        //下一步能走的地
        ArrayList<Point> way = findWay(new Point(col, row));
        while (!way.isEmpty()) {
            //取出一個(gè)能走的地方
            Point point = way.remove(0);
            //走下一步
            if (!visit[point.y][point.x]) {
                traversalChessboard(chess, point.y, point.x, step + 1);
            }

        }
        //判斷是否完成游戲，如果沒(méi)完成就要回溯
        if (step < X * Y && !finshed) {
            chess[row][col] = 0;
            visit[row][col] = false;
        }else {
            finshed=true;
        }
    }

優(yōu)化

這樣計(jì)算效率比較低，算法比較慢。實(shí)際上當(dāng)我們獲得下一步可以走的位置數(shù)組時(shí)是按照固定的56701234順序排列的，但是這樣效率不高，我們?cè)诳紤]到走下一步時(shí)，應(yīng)該先走對(duì)應(yīng)下一步的可能性最少的那一步，比如如果7的下一步有3種可能，而5的下一步有6種可能，那先7后5的效率會(huì)更高。

所以我們可以使用貪心算法對(duì)獲得的這個(gè)步數(shù)集合根據(jù)他們下一步的可能性進(jìn)行由小到大的排序。

/**
     * 貪心算法優(yōu)化
     * @param ps
     */
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                int way1 = findWay(o1).size();
                int way2 = findWay(o2).size();
                if(way1<way2){
                    return -1;
                }else if(way1==way2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
}

對(duì)Comparetor.compare(o1, o2)方法的返回值，如果返回的值小于零，則不交換兩個(gè)o1和o2的位置；如果返回的值大于零，則交換o1和o2的位置。 注意，不論在compare(o1, o2)中是如何實(shí)現(xiàn)的（第一種實(shí)現(xiàn)方式是 o1-02, 第二種實(shí)現(xiàn)方式是 o2 - o1），都遵循上述原則，即返回值小于零，則交換o1和o2的位置；返回值大于零，則不交換o1和o2的位置。 所以，如果采用第一種實(shí)現(xiàn)方式，即 o1 - o2, 那么將是升序排序。因?yàn)樵谠寂判蛑衞1在o2的前邊，如果o1小于o2，那么o1 - o2小于零，即返回值是小于零，但是小于零是不會(huì)交換o1和o2的位置的，所以o1依然排在o2的前邊，是升序；如果o1大于o2，那么o1 - o2大于零，即返回值是大于零，大于零是要交換o1和o2的位置的，所以要改變?cè)寂判蛑衞1和o2的位置，那么依然是升序

最終代碼

package algorithm;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 馬踏棋盤(pán)算法
 */
public class HorseChessboard {
    static int X;//列
    static int Y;//行
    static boolean[][] visit;
    static boolean finshed;

    public static void main(String[] args) {
        X = 8;
        Y = 8;
        visit = new boolean[X][Y];
        finshed = false;
        int[][] chess = new int[X][Y];
        long s = System.currentTimeMillis();

        traversalChessboard(chess, 2, 0, 1);
        long e=System.currentTimeMillis();
        System.out.println(e-s);

        for (int i = 0; i < chess.length; i++) {
            System.out.println(Arrays.toString(chess[i]));
        }

    }

    /**
     * 馬踏棋盤(pán)算法
     *
     * @param chess 棋盤(pán)
     * @param row   坐標(biāo)行
     * @param col   坐標(biāo)列
     * @param step  步數(shù)
     */
    public static void traversalChessboard(int[][] chess, int row, int col, int step) {
        //先走一步
        chess[row][col] = step;
        visit[row][col] = true;
        //下一步能走的地
        ArrayList<Point> way = findWay(new Point(col, row));
        sort(way);
        while (!way.isEmpty()) {
            //取出一個(gè)能走的地方
            Point point = way.remove(0);
            //走下一步
            if (!visit[point.y][point.x]) {
                traversalChessboard(chess, point.y, point.x, step + 1);
            }

        }
        if (step < X * Y && !finshed) {
            chess[row][col] = 0;
            visit[row][col] = false;
        }else {
            finshed=true;
        }
    }

    /**
     * 根據(jù)現(xiàn)在的坐標(biāo)返回可以走的坐標(biāo) x列y行
     *
     * @param current
     * @return
     */
    public static ArrayList<Point> findWay(Point current) {
        ArrayList<Point> res = new ArrayList<>();
        //可以走的坐標(biāo)
        Point p = new Point();
        //5
        if ((p.x = current.x - 2) >= 0 && (p.y = current.y - 1) >= 0) {
            res.add(new Point(p));
        }
        //6
        if ((p.x = current.x - 1) >= 0 && (p.y = current.y - 2) >= 0) {
            res.add(new Point(p));
        }
        //7
        if ((p.x = current.x + 1) < X && (p.y = current.y - 2) >= 0) {
            res.add(new Point(p));
        }
        //0
        if ((p.x = current.x + 2) < X && (p.y = current.y - 1) >= 0) {
            res.add(new Point(p));
        }
        //1
        if ((p.x = current.x + 2) < X && (p.y = current.y + 1) < Y) {
            res.add(new Point(p));
        }
        //2
        if ((p.x = current.x + 1) < X && (p.y = current.y + 2) < Y) {
            res.add(new Point(p));
        }
        //3
        if ((p.x = current.x - 1) >= 0 && (p.y = current.y + 2) < Y) {
            res.add(new Point(p));
        }
        //4
        if ((p.x = current.x - 2) >= 0 && (p.y = current.y + 1) < Y) {
            res.add(new Point(p));
        }
        return res;
    }

    /**
     * 貪心算法優(yōu)化
     * @param ps
     */
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                int way1 = findWay(o1).size();
                int way2 = findWay(o2).size();
                if(way1<way2){
                    return -1;
                }else if(way1==way2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
    }
}

“java怎么實(shí)現(xiàn)馬踏棋盤(pán)算法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！