java实现马踏棋盘算法(骑士周游问题)

Java实现马踏棋盘算法(骑士周游问题)

算法简介

马踏棋盘算法也叫做骑士周游问题，是指在一个棋盘（8 * 8）上，棋子（马）起始位置任意，按照马的走法，要踏遍棋盘上所有的格子，一个格子只能踏一次。马走法包括：

• 向左移动一格，向上移动两格
• 向左移动一格，向下移动两格
• 向右移动一格，向上移动两格
• 向右移动一格，向下移动两格
• 向上移动一格，向左移动两格
• 向上移动一格，向右移动两格
• 向下移动一格，向左移动两格
• 向下移动一格，向右移动两格

算法实现

下面通过Java代码实现该算法。

1. 定义棋盘大小

java
// 棋盘大小为8 * 8
private static int BOARD_SIZE = 8;

1. 创建棋盘

java
// 定义棋盘
private static int[][] chessboard = new int[BOARD_SIZE][BOARD_SIZE];

1. 定义马走法

java
// 马走法
private static int[] dx = {1, 2, 2, 1, -1, -2, -2, -1};
private static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};

1. 实现回溯算法

java
public static void backtrack(int x, int y, int step) {
// 当所有格子都被踩过时，回溯结束
if (step == BOARD_SIZE * BOARD_SIZE) {
printChessBoard();
return;
}
// 依次尝试每一个位置
for (int i = 0; i < 8; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
// 判断是否越界
if (newX < 0 || newX >= BOARD_SIZE || newY < 0 || newY >= BOARD_SIZE) {
continue;
}
// 判断下一步位置是否已经走过
if (chessboard[newX][newY] != 0) {
continue;
}
// 标记该位置已经走过
chessboard[newX][newY] = step + 1;
// 继续尝试下一步
backtrack(newX, newY, step + 1);
// 如果走不通，回溯到上一步，标记为未走过
chessboard[newX][newY] = 0;
}
}

1. 打印棋盘

java
private static void printChessBoard() {
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
System.out.print(chessboard[i][j] + "\t");
}
System.out.println();
}
}

1. 完整代码

```java
public class HorseTraversal {
// 棋盘大小为8 * 8
private static int BOARD_SIZE = 8;

   // 定义棋盘
   private static int[][] chessboard = new int[BOARD_SIZE][BOARD_SIZE];

   // 马走法
   private static int[] dx = {1, 2, 2, 1, -1, -2, -2, -1};
   private static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};

   public static void backtrack(int x, int y, int step) {
       // 当所有格子都被踩过时，回溯结束
       if (step == BOARD_SIZE * BOARD_SIZE) {
           printChessBoard();
           return;
       }
       // 依次尝试每一个位置
       for (int i = 0; i < 8; i++) {
           int newX = x + dx[i];
           int newY = y + dy[i];
           // 判断是否越界
           if (newX < 0 || newX >= BOARD_SIZE || newY < 0 || newY >= BOARD_SIZE) {
               continue;
           }
           // 判断下一步位置是否已经走过
           if (chessboard[newX][newY] != 0) {
               continue;
           }
           // 标记该位置已经走过
           chessboard[newX][newY] = step + 1;
           // 继续尝试下一步
           backtrack(newX, newY, step + 1);
           // 如果走不通，回溯到上一步，标记为未走过
           chessboard[newX][newY] = 0;
       }
   }

   private static void printChessBoard() {
       for (int i = 0; i < BOARD_SIZE; i++) {
           for (int j = 0; j < BOARD_SIZE; j++) {
               System.out.print(chessboard[i][j] + "\t");
           }
           System.out.println();
       }
       System.out.println("------------------------------");
   }

   public static void main(String[] args) {
       // 起始位置定为(3, 4)
       chessboard[3][4] = 1;
       backtrack(3, 4, 1);
   }

}
```

示例说明

下面以起始位置为(0, 0)，(4, 4)为例演示马踏棋盘算法的实现过程。

• 起始位置为(0, 0)

算法实现过程：

java
public static void main(String[] args) {
// 起始位置定为(0, 0)
chessboard[0][0] = 1;
backtrack(0, 0, 1);
}

执行结果：

```
1 38 31 36 3 34 21 8
30 35 2 37 32 7 4 33
39 12 29 22 19 6 9 20
28 41 14 1 24 13 18 5
11 40 23 42 15 26 47 10
46 27 44 9 48 45 16 25
43 54 61 50 57 52 55 60
62 49 56 53 40 59 46 51

---

```

• 起始位置为(4, 4)

算法实现过程：

java
public static void main(String[] args) {
// 起始位置定为(4, 4)
chessboard[4][4] = 1;
backtrack(4, 4, 1);
}

执行结果：

```
15 4 25 18 23 14 3 32
24 19 16 5 2 31 34 13
3 26 21 36 17 22 33 12
20 9 30 27 40 35 8 1
5 14 7 42 37 48 41 10
28 41 46 33 6 11 2 47
13 6 39 50 45 52 43 38
44 29 54 59 56 51 48 53

---

```

从上述结果可以看出，无论从哪个位置开始，最终都能够覆盖到棋盘的所有格子。