馬踏棋盤算法介紹和游戲演示

馬踏棋盤算法也被稱為騎士周游問題
將馬隨機放在國際象棋的8×8棋盤Board[0～7][0～7]的某個方格中，馬按走棋規(guī)則(馬走日字)進行移動。要求每個方格只進入一次，走遍棋盤上全部64個方格
游戲演示: http://www.4399.com/flash/146267_2.htm

游戲

游戲

馬踏棋盤游戲代碼實現(xiàn)

馬踏棋盤問題(騎士周游問題)實際上是圖的深度優(yōu)先搜索(DFS)的應(yīng)用。

如果使用回溯（就是深度優(yōu)先搜索）來解決，假如馬兒踏了53個點，如圖：走到了第53個，坐標（1,0），發(fā)現(xiàn)已經(jīng)走到盡頭，沒辦法，那就只能回退了，查看其他的路徑，就在棋盤上不停的回溯…… ，思路分析+代碼實現(xiàn)

分析第一種方式的問題，并使用貪心算法（greedyalgorithm）進行優(yōu)化。解決馬踏棋盤問題.
使用前面的游戲來驗證算法是否正確。

騎士周游

騎士周游問題的解決步驟和思路

1. 創(chuàng)建棋盤 chessBoard , 是一個二維數(shù)組
2. 將當前位置設(shè)置為已經(jīng)訪問，然后根據(jù)當前位置，計算馬兒還能走哪些位置，并放入到一個集合中(ArrayList), 最多有8個位置， 每走一步，就使用step+1
3. 遍歷ArrayList中存放的所有位置，看看哪個可以走通 , 如果走通，就繼續(xù)，走不通，就回溯.
4. 判斷馬兒是否完成了任務(wù)，使用 step 和應(yīng)該走的步數(shù)比較 ， 如果沒有達到數(shù)量，則表示沒有完成任務(wù)，將整個棋盤置0

注意：馬兒不同的走法（策略），會得到不同的結(jié)果，效率也會有影響(優(yōu)化)

//創(chuàng)建一個Point
Point p1 = new Point();
if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) {
ps.add(new Point(p1));
}

使用貪心算法對原來的算法優(yōu)化

1. 我們獲取當前位置，可以走的下一個位置的集合
   //獲取當前位置可以走的下一個位置的集合
   ArrayList<Point> ps = next(new Point(column, row));
2. 我們需要對 ps 中所有的Point 的下一步的所有集合的數(shù)目，進行非遞減排序,就ok ,
   9， 7， 6， 5， 3， 2 ， 1 //遞減排序
   1, 2, 3, 4,5,6, 10, //遞增排序

1, 2, 2, 2, 3,3, 4, 5, 6 // 非遞減
9， 7， 6，6, 6, 5，5, 3， 2 ， 1 //非遞增

代碼實現(xiàn)

package cn.icanci.algorithm.horse;


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

/**
 * @Author: icanci
 * @ProjectName: AlgorithmAndDataStructure
 * @PackageName: cn.icanci.algorithm.horse
 * @Date: Created in 2020/3/20 15:25
 * @ClassAction: 騎士周游問題
 */
public class HorseChessboard {

    private static int X; // 棋盤的列數(shù)
    private static int Y; // 棋盤的行數(shù)
    //創(chuàng)建一個數(shù)組，標記棋盤的各個位置是否被訪問過
    private static boolean visited[];
    //使用一個屬性，標記是否棋盤的所有位置都被訪問
    private static boolean finished; // 如果為true,表示成功

    public static void main(String[] args) {
        System.out.println("騎士周游算法，開始運行");
        //測試騎士周游算法是否正確
        X = 8;
        Y = 8;
        int row = 1; //馬兒初始位置的行，從1開始編號
        int column = 1; //馬兒初始位置的列，從1開始編號
        //創(chuàng)建棋盤
        int[][] chessboard = new int[X][Y];
        visited = new boolean[X * Y];//初始值都是false
        //測試一下耗時
        long start = System.currentTimeMillis();
        traversalChessboard(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗時: " + (end - start) + " 毫秒");

        //輸出棋盤的最后情況
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 完成騎士周游問題的算法
     *
     * @param chessboard 棋盤
     * @param row        馬兒當前的位置的行 從0開始
     * @param column     馬兒當前的位置的列  從0開始
     * @param step       是第幾步 ,初始位置就是第1步
     */
    public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;
        //row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36
        visited[row * X + column] = true; //標記該位置已經(jīng)訪問
        //獲取當前位置可以走的下一個位置的集合
        ArrayList<Point> ps = next(new Point(column, row));
        //對ps進行排序,排序的規(guī)則就是對ps的所有的Point對象的下一步的位置的數(shù)目，進行非遞減排序
        sort(ps);
        //遍歷 ps
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);//取出下一個可以走的位置
            //判斷該點是否已經(jīng)訪問過
            if (!visited[p.y * X + p.x]) {//說明還沒有訪問過
                traversalChessboard(chessboard, p.y, p.x, step + 1);
            }
        }
        //判斷馬兒是否完成了任務(wù)，使用   step 和應(yīng)該走的步數(shù)比較 ，
        //如果沒有達到數(shù)量，則表示沒有完成任務(wù)，將整個棋盤置0
        //說明: step < X * Y  成立的情況有兩種
        //1. 棋盤到目前位置,仍然沒有走完
        //2. 棋盤處于一個回溯過程
        if (step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }

    }

    /**
     * 功能： 根據(jù)當前位置(Point對象)，計算馬兒還能走哪些位置(Point)，并放入到一個集合中(ArrayList), 最多有8個位置
     *
     * @param curPoint
     * @return
     */
    public static ArrayList<Point> next(Point curPoint) {
        //創(chuàng)建一個ArrayList
        ArrayList<Point> ps = new ArrayList<Point>();
        //創(chuàng)建一個Point
        Point p1 = new Point();
        //表示馬兒可以走5這個位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //判斷馬兒可以走6這個位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //判斷馬兒可以走7這個位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //判斷馬兒可以走0這個位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //判斷馬兒可以走1這個位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //判斷馬兒可以走2這個位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //判斷馬兒可以走3這個位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //判斷馬兒可以走4這個位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

    //根據(jù)當前這個一步的所有的下一步的選擇位置，進行非遞減排序, 減少回溯的次數(shù)
    public static void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                // TODO Auto-generated method stub
                //獲取到o1的下一步的所有位置個數(shù)
                int count1 = next(o1).size();
                //獲取到o2的下一步的所有位置個數(shù)
                int count2 = next(o2).size();
                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }
}

測試

騎士周游算法，開始運行
共耗時: 28 毫秒
1   16  37  32  3   18  47  22  
38  31  2   17  48  21  4   19  
15  36  49  54  33  64  23  46  
30  39  60  35  50  53  20  5   
61  14  55  52  63  34  45  24  
40  29  62  59  56  51  6   9   
13  58  27  42  11  8   25  44  
28  41  12  57  26  43  10  7