如何使用java實(shí)現(xiàn)馬踏棋盤

這篇文章將為大家詳細(xì)講解有關(guān)如何使用java實(shí)現(xiàn)馬踏棋盤，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

具體內(nèi)容如下

• 馬踏棋盤算法也被稱為騎士周游問題

• 將馬隨機(jī)放在過期象棋的8x8棋盤的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)，要求每個(gè)方格只進(jìn)入一次，走遍棋盤上全部64個(gè)方格

騎士周游問題結(jié)局步驟和思路

1.創(chuàng)建棋盤chessBoard，是一個(gè)二維數(shù)組
2.將當(dāng)前位置設(shè)置為已個(gè)訪問，然后根據(jù)當(dāng)前位置，計(jì)算馬兒還能走那些位置，并放到一個(gè)集合中(ArrayList)，最多8個(gè)位置
3.變量ArrayList存放的所有位置，看看哪個(gè)可以走通
4.判斷馬兒是否完成了騎士周游問題

注意：馬兒不同的走法，會(huì)得到不同的結(jié)果，效率也會(huì)有影響

代碼實(shí)現(xiàn)

public class HorseChessBoard {

    private static int X;  //棋盤的列數(shù)
    private static int Y;  //棋盤的行數(shù)
    
    //創(chuàng)建數(shù)組標(biāo)記棋盤各個(gè)位置是否被訪問過
    private static boolean[] visited;
    //使用一個(gè)屬性標(biāo)記是否棋盤的所有位置都被訪問過，即是否成功
    private static boolean finish;  //如果為true表示成功
    
    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int row = 1;
        int col = 1; 
        int[][] chessboard =  new int[X][Y];
        visited = new boolean[X * Y];
        
        long start = System.currentTimeMillis();
        traversalChessboard(chessboard, row-1, col-1, 1);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "  ");
            }
            System.out.println();
        }
    }
    
    //其實(shí)周游問題
    public static void traversalChessboard(int[][] chessboard, int row, int col, int step) {
        
        if (finish) return;
        chessboard[row][col] = step;
        visited[row * X + col] = true;  //標(biāo)記該位置已經(jīng)訪問
        //獲取當(dāng)前位置可以走的下一個(gè)位置的集合
        List<Point> ps = next(new Point(col, row));
        sort(ps);
        
        //遍歷ps
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);  //取出下一個(gè)可以走的位置
            //判斷該點(diǎn)是否已經(jīng)訪問過
            if (!visited[p.y * X + p.x]) {
                traversalChessboard(chessboard, p.y, p.x, step+1);
            }
        }
        
        //1. 棋盤到目前位置任然未走完
        //2. 棋盤處于一個(gè)回溯過程
        if (step < X * Y && !finish) {
            chessboard[row][col] = 0;
            visited[row * X + col] = false;
        } else {
            finish = true;
        }
    }
    
    //根據(jù)當(dāng)前這一步的所有的下一步的選擇位置進(jìn)行非遞減排序
    public static void sort(List<Point> ps) {
        ps.sort(new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                //獲取o1,o2下一步所有個(gè)數(shù)
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }
    
    //Point:根據(jù)當(dāng)前位置(point對(duì)象)
    //根據(jù)當(dāng)前位置，計(jì)算馬兒還能走那些位置，并放到一個(gè)集合中(ArrayList)，最多8個(gè)位置
    public static List<Point> next(Point curPoint) {
        //創(chuàng)建list集合
        List<Point> ps = new ArrayList<>();
        //創(chuàng)建一個(gè)point
        Point p1 = new Point();
        if ((p1.x = curPoint.x-2) >= 0 && (p1.y = curPoint.y-1) >= 0) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x-1) >= 0 && (p1.y = curPoint.y-2) >= 0) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x+1) < X && (p1.y = curPoint.y-2) >= 0) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x+2) < X && (p1.y = curPoint.y-1) >= 0) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x+2) < X && (p1.y = curPoint.y+1) < Y) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x+1) < X && (p1.y = curPoint.y+2) < Y) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x-1) >= 0 && (p1.y = curPoint.y+2) < Y) {
            ps.add(new Point(p1));
        }
        
        if ((p1.x = curPoint.x-2) >= 0 && (p1.y = curPoint.y+1) < Y) {
            ps.add(new Point(p1));
        }
        
        return ps;
    }

}

關(guān)于“如何使用java實(shí)現(xiàn)馬踏棋盤”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。