Problem K
Knight Walk
Before we get into the problem, let’s go over algebraic notation in chess. Algebraic notation refers to the ‘names’ of the squares on a chessboard. Starting from left to right (from white’s perspective), the columns are named a–h. The rows are then named $1$–$8$ in increasing order (again from white’s perspective). Each square’s ‘name’ is the column letter followed by the row number of that particular square.
In Chess, a knight’s move is unique. It may move two squares horizontally and one square vertically, or two squares vertically and one square horizontally (with both forming the shape of an L). For example, a knight on d3 can move to c1, b2, b4, c5, e5, f4, f2, and e1.
It takes (at least) two moves for a knight on d3 to move to d5, with two possible shortest paths: d3 $\rightarrow $ b4 $\rightarrow $ d5 and d3 $\rightarrow $ f4 $\rightarrow $ d5. There are other possible paths (d3 $\rightarrow $ f2 $\rightarrow $ g4 $\rightarrow $ f6 $\rightarrow $ d5 is one), but they are not one of the shortest paths.
Your task is as follows: given the position of a knight on a chessboard and a target square, both in algebraic notation, find all of the possible shortest paths for the knight to move from its starting position to the target square.
Input
Input is the location of the knight in algebraic notation, followed by the target square on the following line. It is guaranteed that the initial location and target square will be distinct, valid squares.
Output
Output is all of the shortest paths in alphabetical order (c1 comes before d1, a1 comes before a2, etc) with each path on its own line, in the following format: starting_square -> square2 -> …-> target_square.
| Sample Input 1 | Sample Output 1 |
|---|---|
d3 d5 |
d3 -> b4 -> d5 d3 -> f4 -> d5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
a6 c8 |
a6 -> b4 -> c6 -> a7 -> c8 a6 -> b4 -> c6 -> e7 -> c8 a6 -> b4 -> d5 -> b6 -> c8 a6 -> b4 -> d5 -> e7 -> c8 a6 -> b8 -> c6 -> a7 -> c8 a6 -> b8 -> c6 -> e7 -> c8 a6 -> b8 -> d7 -> b6 -> c8 a6 -> c5 -> a4 -> b6 -> c8 a6 -> c5 -> b7 -> d6 -> c8 a6 -> c5 -> d7 -> b6 -> c8 a6 -> c5 -> e4 -> d6 -> c8 a6 -> c7 -> a8 -> b6 -> c8 a6 -> c7 -> b5 -> a7 -> c8 a6 -> c7 -> b5 -> d6 -> c8 a6 -> c7 -> d5 -> b6 -> c8 a6 -> c7 -> d5 -> e7 -> c8 a6 -> c7 -> e8 -> d6 -> c8 |
