Number of shortest paths of a knight in chessboard from A to B
<p>Here is the problem:</p>

<p>Given the input n = 4 x = 5, we must imagine a chessboard that is 4 squares across (x-axis) and 5 squares tall (y-axis). (This input changes, all the up to n = 200 x = 200)</p>

<p>Then, we are asked to determine the minimum shortest path from the bottom left square on the board to the top right square on the board for the Knight (the Knight can move 2 spaces on one axis, then 1 space on the other axis).</p>

<p>My current ideas:</p>

<p>Use a 2d array to store all the possible moves, perform breadth-first 
search(BFS) on the 2d array to find the shortest path.</p>

<p>Floyd-Warshall shortest path algorithm.</p>

<p>Create an adjacency list and perform BFS on that (but I think this would be inefficient).</p>

<p>To be honest though I don't really have a solid grasp on the logic.</p>

<p>Can anyone help me with psuedocode, python code, or even just a logical walk-through of the problem?</p>

<p>My approach to this question would be backtracking as the number of squares in the x-axis and y-axis are different. </p>

<p><strong>Note: Backtracking algorithms can be slow for certain cases and fast for the other</strong> </p>

<p>Create a 2-d Array for the chess-board. You know the staring index and the final index. To reach to the final index u need to keep close to the diagonal that's joining the two indexes. </p>

<p>From the starting index see all the indexes that the knight can travel to, choose the index which is closest to the diagonal indexes and keep on traversing, if there is no way to travel any further backtrack one step and move to the next location available from there.</p>

<p><strong>PS : This is a bit similar to a well known problem Knight's Tour, in which choosing any starting point you have to find that path in which the knight whould cover all squares. I have codes this as a java gui application, I can send you the link if you want any help</strong></p>

<p>Hope this helps!!</p>

python algorithm chess