马踏棋盘算法用Java语言实现
在国际象棋的棋盘上有64个方格，而其中马的走法是“L”型，放到中国象棋盘就是“日”型，现在，我们要设计一个算法，让马在棋盘上的某一点出发，一直以“L”型的走法不重复的将棋盘上的每一个方格都走一次。
那么问题来了，马走的时候是有限制的，首先是方向的问题，马可以向8个方向走，而在边角却不能跳出边界，还有就是不能重复走已经走过的方格。下面我们尝试着用Java语言来编写一下这个程序。
public class HorseChess {
// 定义一个8*8的棋盘
int[][] chess = new int[8][8];
// 定义一个步数表示当前的步数
static int step = 1;
// 定义马可以走的下一步，有8种走法
Point[] next = {
new Point(-1, -2),
new Point(-1, 2),
new Point(-2, -1),
new Point(-2, 1),
new Point(1, -2),
new Point(1, 2),
new Point(2, -1),
new Point(2, 1) };
// 定义马走棋盘的方法，参数是当前的坐标点
public void move(Point p) {
if (p.x < 0 || p.y < 0 || p.x > 7 || p.y > 7) {
return;
}
// 如果走到的位置已经有了坐标值，则退出重新选择下一步
if (chess[p.x][p.y] != 0) {
return;
}
chess[p.x][p.y] = step;
//System.out.println(step);
step++;
Point nextPoint = new Point(0, 0);
if (step > 64) {
for(int i=0; i<8; i++) {
for(int j=0; j<8;j++) {
if(chess[i][j]<10) {
System.out.print(" "+chess[i][j] + " ");
}
else {
System.out.print(chess[i][j] + " ");
}
}
System.out.println();
}
System.exit(0);
}
// 然后向8个方向一个一个试着走，能走下去就调用自身的move()方法
else {
for (int i = 0; i < 8; i++) {
nextPoint.x = p.x + next[i].x;
nextPoint.y = p.y + next[i].y;
if (nextPoint.x < 0 || nextPoint.x > 7 || nextPoint.y < 0
|| nextPoint.y > 7) {
} else {
move(nextPoint);
}
}
}
// 8个方向都不能走，则退到上一步位置，换一个方向走，此位置的坐标值清0
chess[p.x][p.y] = 0;
step--;
// 继续执行move()方法
}
public static void main(String[] args) {
HorseChess h = new HorseChess();
Point start = new Point(0,0);
h.move(start);
}
}
class Point {
int x;
int y;
public Point(int a, int b) {
x = a;
y = b;
}
}下面是在eclipse之中的运行结果：
1 16 13 6 3 18 21 10 14 7 2 17 12 9 4 19 31 34 15 8 5 20 11 22 28 25 30 33 38 23 50 47 35 32 27 24 51 48 39 60 26 29 54 37 42 59 46 49 55 36 63 52 57 44 61 40 64 53 56 43 62 41 58 45
马从左上角的起始点开始走，按照“L”型走法分别走到2,3,4即可走完整个棋盘，对于这个问题大家如果有什么疑问可以联系本人，本人邮箱：zhaoheng2017@126.com，欢迎大家前来探讨。
