快捷導(dǎo)航

java實現(xiàn)馬踏棋盤算法(騎士周游問題)

更新時間：2022年02月15日 16:07:15 作者：lu_long

這篇文章主要為大家詳細(xì)介紹了java實現(xiàn)馬踏棋盤算法，解決騎士周游問題，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

騎士周游問題

在8x8的國際棋盤上，按照馬走日的規(guī)則，驗證是否能夠走遍棋盤。

解題思路

1、創(chuàng)建棋盤 chessBoard，是一個二維數(shù)組。
2、將當(dāng)前位置設(shè)置為已經(jīng)訪問，然后根據(jù)當(dāng)前位置，計算馬兒還能走哪些位置，并放入到一個集合中（ArrayList），最多有8個位置，每走一步，就使用step+1。
3、遍歷ArrayList中存放的所有位置，看看哪個可以走通，如果走通，就繼續(xù)，走不通，就回溯。
4、判斷馬兒是否完成了任務(wù)，使用step和應(yīng)該走的步數(shù)比較，如果沒有達(dá)到數(shù)量，則表示沒有完成任務(wù)，將整個棋盤置0。
5、注意：馬兒不同的走法（策略），會得到不同的結(jié)果，效率也會有影響（優(yōu)化）。

使用貪心算法優(yōu)化

1、我們獲取當(dāng)前位置，可有走的下一個位置的集合
ArrayList ps = next(new Point(column, row));
2、我們需要對ps中所有的Point的下一步的所有集合的數(shù)目，進(jìn)行非遞減排序。

優(yōu)化代碼

public static void sort(ArrayList<Point> ps) {
?? ??? ?ps.sort(new Comparator<Point>() {
?? ??? ??? ?@Override
?? ??? ??? ?public int compare(Point o1, Point o2) {
?? ??? ??? ??? ?// 獲取o1的下一步的所有位置的個數(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;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?});
}

馬踏棋盤算法代碼實現(xiàn)

package com.horse;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;

public class HorseChessboard {
?? ?private static int X;// 棋盤的列數(shù)
?? ?private static int Y;// 棋盤的行數(shù)
?? ?private static boolean visited[]; // 標(biāo)記棋盤的位置是否被訪問過
?? ?private static boolean finished;// 標(biāo)記棋盤的所有位置都被訪問（是否成功）

?? ?public static void main(String[] args) {
?? ??? ?// 測試騎士周游算法
?? ??? ?X = 8;
?? ??? ?Y = 8;
?? ??? ?int row = 1;// 馬兒的初始位置行
?? ??? ?int column = 1;// 馬兒初始位置列
?? ??? ?// 創(chuàng)建棋盤
?? ??? ?int[][] chessboard = new int[X][Y];
?? ??? ?visited = new boolean[X * Y];
?? ??? ?// 測試一下耗時
?? ??? ?long start = System.currentTimeMillis();
?? ??? ?traversalChessboard(chessboard, row - 1, column - 1, 1);
?? ??? ?long end = System.currentTimeMillis();
?? ??? ?System.out.println("耗時" + (end - start) + "ms");
?? ??? ?// 輸出棋盤最后情況
?? ??? ?for (int[] rows : chessboard) {
?? ??? ??? ?for (int step : rows) {
?? ??? ??? ??? ?System.out.printf("%4d", step);
?? ??? ??? ?}
?? ??? ??? ?System.out.println();
?? ??? ?}

?? ?}

?? ?/**
?? ? * @Method_Name:traversalChessboard
?? ? * @Description: 完成騎士周游問題多的算法
?? ? * @param chessboard
?? ? * ? ? ? ? ? ?棋盤
?? ? * @param row
?? ? * ? ? ? ? ? ?馬兒當(dāng)前位置的行 從0開始
?? ? * @param column
?? ? * ? ? ? ? ? ?馬兒當(dāng)前位置的列 從0開始
?? ? * @param step
?? ? * ? ? ? ? ? ?void 是第幾步，初始位置是第1步
?? ? */
?? ?public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
?? ??? ?chessboard[row][column] = step;
?? ??? ?visited[row * X + column] = true;// 標(biāo)記該位置已訪問
?? ??? ?// 獲取當(dāng)前位置可以走的下一步
?? ??? ?ArrayList<Point> ps = next(new Point(column, row));
?? ??? ?// 對ps進(jìn)行非遞減排序，
?? ??? ?sort(ps);
?? ??? ?// 遍歷ps
?? ??? ?while (!ps.isEmpty()) {
?? ??? ??? ?Point p = ps.remove(0);// 取出下一個可以走的位置
?? ??? ??? ?// 判斷是否訪問過
?? ??? ??? ?if (!visited[p.y * X + p.x]) {// 說明還沒有訪問過
?? ??? ??? ??? ?traversalChessboard(chessboard, p.y, p.x, step + 1);
?? ??? ??? ?}
?? ??? ?}
?? ??? ?// 判斷是否完成
?? ??? ?if (step < X * Y && !finished) {
?? ??? ??? ?chessboard[row][column] = 0;
?? ??? ??? ?visited[row * X + column] = false;
?? ??? ?} else {
?? ??? ??? ?finished = true;
?? ??? ?}
?? ?}

?? ?/**
?? ? * @Method_Name:next
?? ? * @Description: 計算馬兒還能走哪些位置，并放入到一個集合中（ArrayList）
?? ? * @param curPoint
?? ? * @return ArrayList<Point>
?? ? */
?? ?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ù)當(dāng)前這個一步的所有的下一步的選擇位置，進(jìn)行非遞減排序
?? ?public static void sort(ArrayList<Point> ps) {
?? ??? ?ps.sort(new Comparator<Point>() {

?? ??? ??? ?@Override
?? ??? ??? ?public int compare(Point o1, Point o2) {
?? ??? ??? ??? ?// 獲取o1的下一步的所有位置的個數(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;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?});
?? ?}
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: