1.马踏棋盘算法介绍:
马踏棋盘算法也被称为骑士周游问题
将马随机放在国际象棋的 8×8 棋盘 Board[0~7][0~7]的某个方格中,马按走棋规则(马走日字)进行移动。要求每个方格只进入一次,走遍棋盘上全部 64 个方格
2.马踏棋盘算法应用实现
- 马踏棋盘问题实际上是图的深度优先搜索(DFS)的应用。
- 如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了 53 个点,如图:走到了第 53 个,坐标(1,0),发现已经走到尽头,没办法,那就只能回退了,查看其他的路径,就在棋盘上不停的回溯……
3.代码实现:
package algorithm;
import java.awt.*;
import java.util.ArrayList;
/**
* @author WuChenGuang
*/
public class HorseChessboard {
private static int X;
private static int Y;
/**
* 判断是否已经访问过
*/
private static boolean[] visited;
/**
* 表示棋盘中所有的位置是否都被标记了
*/
private static boolean finished;
public static void main(String[] args) {
// 描述棋盘
X = 8;
Y = 8;
int row = 1;
int column = 1;
int[][] chessBoard = new int[X][Y];
visited = new boolean[X * Y];
long start = System.currentTimeMillis();
chessboard(chessBoard, row - 1, column - 1, 1);
long end = System.currentTimeMillis();
System.out.println(end - start);
}
public static void chessboard(int[][] chessBoard, int row, int column, int step) {
chessBoard[row][column] = step;
visited[row * X + column] = true;
// 没跳一步,都要计算当前所在的位置下一步要跳的位置数量,可以存储在集合中去
ArrayList<Point> ps = next(new Point(column, row));
// 预判未来要跳的次数,减少回溯
sort(ps);
while (!ps.isEmpty()) {
Point nextPoint = ps.remove(0);
if (!visited[nextPoint.y * X + nextPoint.x]) {
chessboard(chessBoard, nextPoint.y, nextPoint.x, step + 1);
}
}
// 计算当前已经走的次数是否已经走完,完成任务 step<x*y,
if (step < X * Y && !finished) {
chessBoard[row][column] = 0;
visited[row * X + column] = false;
} else {
finished = true;
}
}
/**
* @param curPoint 当前所在的位置
* @return 下一次跳的位置集合
*/
public static ArrayList<Point> next(Point curPoint) {
ArrayList<Point> ps = new ArrayList<>();
Point point = new Point();
if ((point.x = curPoint.x - 2) >= 0 && (point.y = curPoint.y - 1) >= 0) {
ps.add(new Point(point));
}
if ((point.x = curPoint.x - 1) >= 0 && (point.y = curPoint.y - 2) >= 0) {
ps.add(new Point(point));
}
if ((point.x = curPoint.x + 1) < X && (point.y = curPoint.y - 2) >= 0) {
ps.add(new Point(point));
}
if ((point.x = curPoint.x + 2) < X && (point.y = curPoint.y - 1) >= 0) {
ps.add(new Point(point));
}
if ((point.x = curPoint.x + 2) < X && (point.y = curPoint.y + 1) < Y) {
ps.add(new Point(point));
}
if ((point.x = curPoint.x + 1) < X && (point.y = curPoint.y + 2) < Y) {
ps.add(new Point(point));
}
if ((point.x = curPoint.x - 1) >= 0 && (point.y = curPoint.y + 2) < Y) {
ps.add(new Point(point));
}
if ((point.x = curPoint.x - 2) >= 0 && (point.y = curPoint.y + 1) < Y) {
ps.add(new Point(point));
}
return ps;
}
public static void sort(ArrayList<Point> ps) {
ps.sort((o1, o2) -> {
int count1 = next(o1).size();
int count2 = next(o2).size();
return Integer.compare(count1, count2);
});
}
}
运行结果:
注:每次结果不一样。