骑士巡游问题

sdongy

根据骑士巡游问题（就是8*8国际象棋盘上马从任意位置开始走遍棋盘每个位置 并且每个位置只能走一次）用JAVA编写一小游戏，要求用户手动寻找路径。急啊
有高手吗 帮忙弄个哦 十分着急 如果哪位高手帮忙请联系我哦 （重金答谢）QQ19778847

arping

我写了一段用机器自动寻找的，里面是一个递归程序，找到一个路径就返回
CHESS_SIZE是棋盘的大小，CHESS_SIZE为5时表示5x5的
8x8的太大了，时间太久就改成5x5的了

1. 
   
2. package game;
   
3. 
   
4. import java.util.ArrayList;
   
5. import java.util.Arrays;
   
6. import java.util.LinkedList;
   
7. 
   
8. class Cordinate {
   
9.        
   
10.         public int x;
    
11. 
    
12.         public int y;
    
13. 
    
14.         Cordinate(int cx, int cy) {
    
15.                 x = cx;
    
16.                 y = cy;
    
17.         }
    
18. 
    
19.         public String toString() {
    
20.                 return "(" + x + "," + y + ")";
    
21.         }
    
22. }
    
23. 
    
24. public class Chess {
    
25. 
    
26.         public static int CHESS_SIZE = 5;
    
27. 
    
28.         public static Cordinate INIT_CORD = new Cordinate(0, 0);
    
29. 
    
30.         /**
    
31.          * Test whether a cordinate is valid in a chesspane
    
32.          * @param cord
    
33.          * @param clength
    
34.          * @return whether it is valid
    
35.          */
    
36.         public static boolean valid(int cord, int clength) {
    
37.                 if ((cord >= 0) && (cord < clength))
    
38.                         return true;
    
39.                 else
    
40.                         return false;
    
41.         }
    
42. 
    
43.         /**
    
44.          * Calculate next steps from the latest step
    
45.          * @param chesspane:
    
46.          *            show which cordinate has been visited and which hasn't
    
47.          * @param laststep:
    
48.          *            the last cordinate which has been visited
    
49.          * @return A list of Cordinates which can be visited, excluding the visited
    
50.          *         Cordinates
    
51.          */
    
52.         public static ArrayList<Cordinate> nextStep(int[][] chesspane,
    
53.                         Cordinate laststep) {
    
54.                 int j, k;
    
55.                 int nextx, nexty;
    
56.                 int clength = chesspane.length;
    
57.                 ArrayList<Cordinate> result = new ArrayList<Cordinate>();
    
58. 
    
59.                 for (j = -2; j <= 2; j++) {
    
60.                         if (j == 0)
    
61.                                 continue;
    
62. 
    
63.                         nextx = laststep.x + j;
    
64. 
    
65.                         k = Math.abs(j) - 3;
    
66.                         nexty = laststep.y + k;
    
67.                         if (valid(nextx, clength) && valid(nexty, clength)
    
68.                                         && chesspane[nextx][nexty] == 0)
    
69.                                 result.add(new Cordinate(nextx, nexty));
    
70.                         k = 3 - Math.abs(j);
    
71.                         nexty = laststep.y + k;
    
72.                         if (valid(nextx, clength) && valid(nexty, clength)
    
73.                                         && chesspane[nextx][nexty] == 0)
    
74.                                 result.add(new Cordinate(nextx, nexty));
    
75.                 }
    
76. 
    
77.                 return result;
    
78.         }
    
79. 
    
80.         /**
    
81.          * @param chesspane:
    
82.          *            show which cordinate has been visited and which hasn't
    
83.          * @param path:
    
84.          *            the path of cordinates where has been visited
    
85.          * @return the length of the path, if it equals "chesspane.length *
    
86.          *         chesspane.length" , means having found a solution.
    
87.          */
    
88.         public static int chessfrom(int[][] chesspane, LinkedList<Cordinate> path) {
    
89.                 int pathlength;
    
90.                 Cordinate laststep = path.getLast();
    
91.                 ArrayList<Cordinate> nextsteps = nextStep(chesspane, laststep);
    
92. 
    
93.                 if (nextsteps.size() == 0) {
    
94.                         if (path.size() == chesspane.length * chesspane.length) {
    
95.                                 System.out.println(path);
    
96.                         }
    
97.                         return path.size();
    
98.                 }
    
99. 
    
100.                 for (Cordinate step : nextsteps) {
     
101.                         path.add(step);
     
102.                         chesspane[step.x][step.y] = 1;
     
103.                         pathlength = chessfrom(chesspane, path);
     
104. 
     
105.                         if (pathlength == chesspane.length * chesspane.length) {
     
106.                                 // System.out.println(path);
     
107.                                 return chesspane.length * chesspane.length;
     
108.                         } else {
     
109.                                 path.removeLast();
     
110.                                 chesspane[step.x][step.y] = 0;
     
111.                         }
     
112.                 }
     
113.                 return 0;
     
114.         }
     
115. 
     
116.         /**
     
117.          * @param args
     
118.          */
     
119.         public static void main(String[] args) {
     
120.                 // TODO Auto-generated method stub
     
121.                 int[][] chesspane = new int[CHESS_SIZE][CHESS_SIZE];
     
122.                 LinkedList<Cordinate> path = new LinkedList<Cordinate>();
     
123. 
     
124.                 for (int i = 0; i < chesspane.length; i++) {
     
125.                         Arrays.fill(chesspane[i], 0);
     
126.                 }
     
127. 
     
128.                 path.add(INIT_CORD);
     
129.                 chesspane[INIT_CORD.x][INIT_CORD.y] = 1;
     
130. 
     
131.                 int length = chessfrom(chesspane, path);
     
132.                 System.out.println(length);
     
133.         }
     
134. 
     
135. }
     

复制代码