快捷導(dǎo)航

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

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

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

騎士周游問(wèn)題

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

解題思路

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

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

1、我們獲取當(dāng)前位置，可有走的下一個(gè)位置的集合
ArrayList ps = next(new Point(column, row));
2、我們需要對(duì)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的下一步的所有位置的個(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;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?});
}

馬踏棋盤算法代碼實(shí)現(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)記棋盤的位置是否被訪問(wèn)過(guò)
?? ?private static boolean finished;// 標(biāo)記棋盤的所有位置都被訪問(wèn)（是否成功）

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

?? ?}

?? ?/**
?? ? * @Method_Name:traversalChessboard
?? ? * @Description: 完成騎士周游問(wèn)題多的算法
?? ? * @param chessboard
?? ? * ? ? ? ? ? ?棋盤
?? ? * @param row
?? ? * ? ? ? ? ? ?馬兒當(dāng)前位置的行 從0開(kāi)始
?? ? * @param column
?? ? * ? ? ? ? ? ?馬兒當(dāng)前位置的列 從0開(kāi)始
?? ? * @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)記該位置已訪問(wèn)
?? ??? ?// 獲取當(dāng)前位置可以走的下一步
?? ??? ?ArrayList<Point> ps = next(new Point(column, row));
?? ??? ?// 對(duì)ps進(jìn)行非遞減排序，
?? ??? ?sort(ps);
?? ??? ?// 遍歷ps
?? ??? ?while (!ps.isEmpty()) {
?? ??? ??? ?Point p = ps.remove(0);// 取出下一個(gè)可以走的位置
?? ??? ??? ?// 判斷是否訪問(wèn)過(guò)
?? ??? ??? ?if (!visited[p.y * X + p.x]) {// 說(shuō)明還沒(méi)有訪問(wèn)過(guò)
?? ??? ??? ??? ?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: 計(jì)算馬兒還能走哪些位置，并放入到一個(gè)集合中（ArrayList）
?? ? * @param curPoint
?? ? * @return ArrayList<Point>
?? ? */
?? ?public static ArrayList<Point> next(Point curPoint) {
?? ??? ?// 創(chuàng)建有一個(gè)ArrayList
?? ??? ?ArrayList<Point> ps = new ArrayList<Point>();
?? ??? ?// 創(chuàng)建Point
?? ??? ?Point p1 = new Point();
?? ??? ?// 判斷馬兒可以走5這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走6這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走7這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走0這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走1這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走2這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走3這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走4這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?return ps;
?? ?}
?? ?// 根據(jù)當(dāng)前這個(gè)一步的所有的下一步的選擇位置，進(jìn)行非遞減排序
?? ?public static void sort(ArrayList<Point> ps) {
?? ??? ?ps.sort(new Comparator<Point>() {

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

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

您可能感興趣的文章: