Hi folks!
\r\n\r\nI've just handed in an assignment and I thought I'd try yakking about some of it here. The assignment had two parts; solving the Knight's Path and Knight's Tour problems.
\r\n\r\nIf you don't know what they are, they're chess problems. The Knight's Path is finding a path between two arbitrary points on a chessboard using the Knight piece. To spice it up, chessboards can be any size X x X. The Knight's Tour is having the Knight start on an arbitrary place on the chessboard and take a tour of the board, visiting each square once and only once.
\r\n\r\nHere's some sample output from the program I wrote to give you an idea. These are small boards. Each number represents which step each square represents:
\r\n\r\n[E:\\Personal Folder\\SchoolWork\\CISC121\\Assignment 6]java KnightsPath\r\nsize of chessboard: 8\r\nrow of starting position (1 - 8): 1\r\ncolumn of starting position (1 - 8): 1\r\nrow of ending position (1 - 8): 8\r\ncolumn of end position (1 - 8): 8\r\nSuccess! Took 53 steps:\r\n ----------------------------------------\r\n | 1 | 12 | 9 | 6 | 3 | 14 | 17 | 20 |\r\n -----------------------------------------\r\n | 10 | 7 | 2 | 13 | 18 | 21 | 4 | 15 |\r\n -----------------------------------------\r\n | 31 | 28 | 11 | 8 | 5 | 16 | 19 | 22 |\r\n -----------------------------------------\r\n | 0 | 25 | 32 | 29 | 38 | 23 | 36 | 47 |\r\n -----------------------------------------\r\n | 33 | 30 | 27 | 24 | 35 | 48 | 39 | 0 |\r\n -----------------------------------------\r\n | 26 | 43 | 34 | 49 | 40 | 37 | 46 | 0 |\r\n -----------------------------------------\r\n | 0 | 50 | 41 | 44 | 0 | 52 | 0 | 0 |\r\n -----------------------------------------\r\n | 42 | 0 | 0 | 51 | 0 | 45 | 0 | 53 |\r\n -----------------------------------------\r\n\r\n[E:\\Personal Folder\\SchoolWork\\CISC121\\Assignment 6]java KnightsTour\r\nsize of chessboard: 6\r\nrow of starting position (1 - 6): 1\r\ncolumn of starting position (1 - 6): 1\r\nSuccess! Took 36 steps:\r\n ------------------------------\r\n | 1 | 8 | 5 | 20 | 3 | 10 |\r\n -------------------------------\r\n | 6 | 19 | 2 | 9 | 34 | 21 |\r\n -------------------------------\r\n | 15 | 28 | 7 | 4 | 11 | 32 |\r\n -------------------------------\r\n | 18 | 25 | 16 | 33 | 22 | 35 |\r\n -------------------------------\r\n | 29 | 14 | 27 | 24 | 31 | 12 |\r\n -------------------------------\r\n | 26 | 17 | 30 | 13 | 36 | 23 |\r\n -------------------------------\r\n\r\n
This is an introductory course, so the requirements were pretty simple; just solve them, not prettily. The avowed purpose of the assignment is to get people used to using recursive techniques. In the class, the prof specifically stated "applying a heuristic is not part of the assignment."
\r\n\r\nSo, of course, I had to take a shot at coming up with a heuristic. :)
\r\n\r\nI only ended up coming up with a heuristic for the Knight's path problem. However, while my heuristic works (as in, it's better than the version of the path calculated by the brute force method shown above) it runs into problems in certain cases. To illustrate, here's a ten by ten board showing the result of using the version with the heuristic:
\r\n\r\n[E:\\Personal Folder\\SchoolWork\\CISC121\\Assignment 6]java KnightsRace\r\nsize of chessboard: 10\r\nrow of starting position (1 - 10): 1\r\ncolumn of starting position (1 - 10): 1\r\nrow of ending position (1 - 10): 10\r\ncolumn of end position (1 - 10): 10\r\nSuccess! Took 7 steps:\r\n --------------------------------------------------\r\n | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\r\n ---------------------------------------------------\r\n | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\r\n ---------------------------------------------------\r\n | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\r\n ---------------------------------------------------\r\n | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\r\n ---------------------------------------------------\r\n | 0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\r\n ---------------------------------------------------\r\n | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 0 |\r\n ---------------------------------------------------\r\n | 0 | 0 | 0 | 0 | 0 | 0 | 5 | 0 | 0 | 0 |\r\n ---------------------------------------------------\r\n | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 6 | 0 |\r\n ---------------------------------------------------\r\n | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\r\n ---------------------------------------------------\r\n | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 7 |\r\n ---------------------------------------------------\r\n\r\n
Now, here's the results using an eight by eight board:
\r\n\r\n[E:\\Personal Folder\\SchoolWork\\CISC121\\Assignment 6]java KnightsRace\r\nsize of chessboard: 8\r\nrow of starting position (1 - 8): 1\r\ncolumn of starting position (1 - 8): 1\r\nrow of ending position (1 - 8): 8\r\ncolumn of end position (1 - 8): 8\r\nSuccess! Took 11 steps:\r\n ----------------------------------------\r\n | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\r\n -----------------------------------------\r\n | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\r\n -----------------------------------------\r\n | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 |\r\n -----------------------------------------\r\n | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\r\n -----------------------------------------\r\n | 0 | 0 | 3 | 0 | 0 | 0 | 0 | 6 |\r\n -----------------------------------------\r\n | 0 | 0 | 0 | 9 | 4 | 7 | 0 | 0 |\r\n -----------------------------------------\r\n | 0 | 0 | 0 | 0 | 0 | 10 | 5 | 0 |\r\n -----------------------------------------\r\n | 0 | 0 | 0 | 0 | 8 | 0 | 0 | 11 |\r\n -----------------------------------------\r\n\r\n
As you can see, it gets screwed up on the smaller board, taking many more moves to get to the end.
\r\n\r\nThe heuristic I came up with was pretty simple. The program looks ahead at the next move, and calculates the distance of the next move from the final destination point. This is an integer that consists of the sum of the vertical and horizontal difference from the next move to the end point. Then, it looks for the following results in turn: the one with 0 distance, the one with 3 distance, and the smallest distance.
\r\n\r\nOne obvious problem with looking for delta 3 is that you get the result of move 6 directly above, which is a bad move. The problem with looking for the smallest distance is you can get the result of 5 above, which is also a bad move. From the various times I've run it, it's pretty obvious that the strategy of looking for the smallest works until you get within two moves of the end point (a vertical or a horizontal difference of four, more or less). My math is pretty weak, so I can't mathematically prove what the right place where the strategy should change, but it's not too hard to figure out. So, a way to improve the heuristic is to use the smallest distance rule until the knight gets close. However, after that, I'm not too sure what the best approach to figuring out the right move is; one should start looking for the jump to the landing pad, but figuring out exactly where to find the springboard is not easy. Any ideas?