Knight Shortest Path Puzzle | Guptapraveen's Blog

Knight Shortest Path Puzzle | Guptapraveen's Blog

This is the KNIGHT short path problem. Knight should move from any place (x,y) to the bottom right corner of the Chess Board and Chess Board can be of any size ( N x M ). Where N & M  can't be less then 3.

Move the chess piece "KNIGHT" from any location on a
"3 x 3″ Chess Board and make it go to the far right
hand bottom corner^. Chess Board in the problem is
not the usual Chess Board of 8 x 8.

KNIGHT starting position may be any position on board
Program should exit when knight moves to 3 x 3 corner.

Here is how my Chess board looks.
1      2      3
————————-
|      |      |      |
1 |      |      |      |
|      |      |      |
————————-
|      |      |      |
2 |      |      |      |
|      |      |      |
————————-
|      |      |      |
3 |      |      |  X  | <<<<——- KNIGHT should reach
|      |      |      |            this square.
————————-

Here are the steps for the algorithm design.

This application usages searching algorithm based on the weight of next move. Once it opt for a path next move is decided based on the highest weighted legal move. Here are the steps:

1. Start with the initial position. ( You can have maximum 8 move for the knight for NxM)
2. If the next legal move is destination then add that in the Visited List and quit the game.
3. If next legal move is just closer to destination then move and finally move to destination and quit the Game.
4. Move knight to next highest weighted position. Weight is calculated by adding the X,Y position of the next legal move.
5. Again check the step 2 and 3.
6. Do it in a recursive function till you reach the destination.

Hope this will help to solve the puzzle.

Read full article from Knight Shortest Path Puzzle | Guptapraveen's Blog