马踏棋盘算法

基本介绍

马踏棋盘算法也被称为骑士周游问题。

将马随机放在国际象棋的8×8棋盘Board[0～7] [0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。

游戏演示: http://www.4399.com/flash/146267_2.htm

解决思路

  1. 创建棋盘 chessBoard , 是一个二维数组
  2. 将当前位置标记为已经访问和第几步，然后根据当前位置，计算马儿还能走哪些位置，并放入到一个集合中(ArrayList), 最多有8个位置， 每走一步，就使用step+1
  3. 遍历ArrayList中存放的所有位置，看看哪个可以走通 , 如果走通，就继续，走不通，就回溯
  4. 判断马儿是否完成了任务，使用 step 和应该走的步数比较 ， 如果不相等，则表示没有完成任务，置0回溯

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package com.nanzx.horse;

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

public class HorseChessboard {
	private static int COLUMN; // 棋盘的列数
	private static int ROW; // 棋盘的行数
	private static boolean visited[][];// 标记棋盘的各个位置是否被访问过
	private static boolean finished; // 标记棋盘的所有位置是否都被访问

	public static void main(String[] args) {
		System.out.println("骑士周游算法，开始运行~~");
		COLUMN = 8;
		ROW = 8;
		int row = 1; // 马儿初始位置的行，从1开始编号
		int column = 1; // 马儿初始位置的列，从1开始编号
		// 创建棋盘
		int[][] chessboard = new int[ROW][COLUMN];
		visited = new boolean[ROW][COLUMN];// 初始值都是false

		// 测试一下耗时
		long start = System.currentTimeMillis();
		travelChessboard(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();
		}
	}

	public static void travelChessboard(int[][] chessboard, int row, int column, int step) {
		chessboard[row][column] = step;// 标记该位置是第几步
		visited[row][column] = true; // 标记该位置已经访问
		ArrayList<Point> ps = next(new Point(row, column));
		while (!ps.isEmpty()) {
			Point p = ps.remove(0);
			if (visited[p.x][p.y] == false) {
				travelChessboard(chessboard, p.x, p.y, step + 1);
			}
		}
		// 说明: step <ROW * COLUMN 成立的情况有两种
		// 1. 棋盘到目前位置，仍然没有走完，出现死棋
		// 2. 棋盘处于一个回溯过程
		if (step < ROW * COLUMN && finished == false) {
			chessboard[row][column] = 0;
			visited[row][column] = false;
		} else {
			finished = true;// 防止走完后回溯被打乱
		}
	}

	// 功能： 根据当前位置，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList), 最多有8个位置
	public static ArrayList<Point> next(Point curPoint) {
		ArrayList<Point> ps = new ArrayList<Point>();
		Point p1 = new Point();
		// 表示马儿是否可以走5这个位置
		if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
			ps.add(new Point(p1));
		}
		// 判断马儿是否可以走6这个位置
		if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
			ps.add(new Point(p1));
		}
		// 判断马儿是否可以走7这个位置
		if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < COLUMN) {
			ps.add(new Point(p1));
		}
		// 判断马儿是否可以走0这个位置
		if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < COLUMN) {
			ps.add(new Point(p1));
		}
		// 判断马儿是否可以走1这个位置
		if ((p1.x = curPoint.x + 1) < ROW && (p1.y = curPoint.y + 2) < COLUMN) {
			ps.add(new Point(p1));
		}
		// 判断马儿是否可以走2这个位置
		if ((p1.x = curPoint.x + 2) < ROW && (p1.y = curPoint.y + 1) < COLUMN) {
			ps.add(new Point(p1));
		}
		// 判断马儿是否可以走3这个位置
		if ((p1.x = curPoint.x + 2) < ROW && (p1.y = curPoint.y - 1) >= 0) {
			ps.add(new Point(p1));
		}
		// 判断马儿是否可以走4这个位置
		if ((p1.x = curPoint.x + 1) < ROW && (p1.y = curPoint.y - 2) >= 0) {
			ps.add(new Point(p1));
		}
		return ps;
	}
}

运行结果：

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

算法优化

马儿不同的走法（策略），会得到不同的结果，效率也会有影响。

上面的策略就是按照5,6,7,0,1,2,3,4的顺序来走。

使用贪心算法对原来的算法优化，我们需要对ps 中所有的Point 的下一步的所有集合的数目，进行非递减排序即可。

关于数据结构中非递减 递减 非递增 递增

非递减就是a[i]<=a[i+1]

递减就是a[i]>a[i+1]

非递增就是a[i]>=a[i+1]

递增就是a[i]<a[i+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
	public static void travelChessboard(int[][] chessboard, int row, int column, int step) {
		chessboard[row][column] = step;
		visited[row][column] = true; 
		ArrayList<Point> ps = next(new Point(row, column));
		sort(ps);//对ps中的point进行排序
		while (!ps.isEmpty()) {
			Point p = ps.remove(0);
			if (visited[p.x][p.y] == false) {
				travelChessboard(chessboard, p.x, p.y, step + 1);
			}
		}
		if (step < ROW * COLUMN && finished == false) {
			chessboard[row][column] = 0;
			visited[row][column] = false;
		} else {
			finished = true;
		}
	}

	// 根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
	public static void sort(ArrayList<Point> ps) {
		ps.sort(new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				int count1 = next(o1).size();
				int count2 = next(o2).size();
				return count1 - count2;
			}
		});
	}
}

运行结果：

骑士周游算法，开始运行~~
共耗时: 48 毫秒
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

关于compa方法的返回值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
return count1 - count2;//升序
等价于
    if(count1 < count2) {
        return -1;
    } else if (count1 == count2) {
        return 0;
    } else {
        return 1;
    }
return -(count1 - count2);//降序
等价于
    if(count1 < count2) {
        return 1;
    } else if (count1 == count2) {
        return 0;
    } else {
        return -1;
    }