黑马程序员技术交流社区

标题: java经典算法之骑士走棋盘（Knight tour） [打印本页]
作者: 王海彬    时间: 2015-9-16 23:00
标题: java经典算法之骑士走棋盘（Knight tour）
问题说明：
骑士游戏，在十八世纪倍受数学家与拼图迷的注意，骑士的走法为西洋棋的走发，骑士可以由任何一个位置出发，它要如何走完所有的位置。


算法代码：
1.      public class Knight {
2.          public boolean travel(int startX,
3.                               int startY, int[][] board) {
4.              // 对应骑士可以走的八个方向
5.              int[] ktmove1 = {-2, -1, 1, 2, 2, 1,-1, -2};
6.              int[] ktmove2 = {1, 2, 2, 1, -1, -2,-2, -1};
7.              
8.              // 下一个出路的位置        int[] nexti = new int[board.length];
9.              int[] nextj = new int[board.length];
10.         
11.          // 记录出路的个数
12.          int[] exists = newint[board.length];
13.         
14.          int x = startX;
15.          int y = startY;
16.         
17.          board[x][y] = 1;
18.         
19.          for(int m = 2; m <=Math.pow(board.length, 2); m++) {
20.              for(int k = 0; k <board.length; k++) {
21.                 exists[k] = 0;
22.              }
23.              
24.              int count = 0;
25.              // 试探八个方向
26.              for(int k = 0; k <board.length; k++) {
27.                  int tmpi= x + ktmove1[k];
28.                  int tmpj= y + ktmove2[k];
29.                  
30.                  // 如果是边界，不可以走
31.                  if(tmpi< 0 || tmpj < 0 ||
32.                    tmpi > 7 || tmpj > 7) {
33.                     continue;
34.                  }
35.                  
36.                  // 如果这个方向可以走，记录下来
37.                 if(board[tmpi][tmpj] == 0) {
38.                     nexti[count] = tmpi;
39.                     nextj[count] = tmpj;
40.                     // 可走的方向加一个
41.                     count++;
42.                  }
43.              }
44.              
45.              int min = -1;
46.              if(count == 0) {
47.                  returnfalse;
48.              }
49.              else if(count == 1) {
50.                  min = 0;
51.              }
52.              else {
53.                  // 找出下个位置的出路数
54.                  for(intl = 0; l < count; l++) {
55.                     for(int k = 0; k < board.length; k++) {
56.                         int tmpi = nexti[l] + ktmove1[k];
57.                         int tmpj = nextj[l] + ktmove2[k];
58.   
59.                         if(tmpi < 0 || tmpj < 0 ||
60.                            tmpi > 7 || tmpj > 7) {
61.                             continue;
62.                         }
63.   
64.                         if(board[tmpi][tmpj] == 0)
65.                             exists[l]++;
66.                     }
67.                  }
68.   
69.                  int tmp= exists[0];
70.                  min = 0;
71.   
72.                  // 从可走的方向寻找最少出路的方向
73.                  for(intl = 1; l < count; l++) {
74.                     if(exists[l] < tmp) {
75.                         tmp = exists[l];
76.                         min = l;
77.                     }
78.                  }
79.              }
80.              
81.              // 走最少出路的方向
82.              x = nexti[min];
83.              y = nextj[min];
84.              board[x][y] = m;
85.          }
86.         
87.          return true;
88.      }
89.      
90.      public static void main(String[] args) {
91.          int[][] board = new int[8][8];
92.          Knight knight = new Knight();
93.         
94.          if(knight.travel(
95.                 Integer.parseInt(args[0]),
96.                 Integer.parseInt(args[1]), board)) {
97.             System.out.println("走棋完成！");
98.          }
99.          else {
100.              System.out.println("走棋失败！");
101.           }
102.           
103.           for(int i = 0; i < board.length;i++) {
104.               for(int j = 0; j <board[0].length; j++) {
105.                  if(board[j] < 10) {
106.                      System.out.print(" " + board[j]);
107.                   }
108.                   else {
109.                      System.out.print(board[j]);
110.                   }
111.                  System.out.print(" ");
112.               }
113.               System.out.println();
114.           }
115.       }
116.   }

作者: 王海彬    时间: 2015-9-16 23:01
希望各位哥们不会被二维数组搞蒙
作者: 王海彬    时间: 2015-9-16 23:30
不知道以后会不会用到四维数组和八维数组之类的那就真的要死人了
作者: kaysun    时间: 2015-9-17 00:09
明天复习一下数组
作者: 那过往de小时光    时间: 2015-9-17 08:26
我还是有点晕
作者: 张寰宇    时间: 2015-9-17 12:10
多谢分享学习了



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2