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>Try something. Draw boards of the following sizes: 1x1, 2x2, 3x3, 4x4, and a few odd ones like 2x4 and 3x4. Starting with the smallest board and working to the largest, start at the bottom left corner and write a 0, then find all moves from zero and write a 1, find all moves from 1 and write a 2, etc. Do this until there are no more possible moves.</p>

<p>After doing this for all 6 boards, you should have noticed a pattern: Some squares couldn't be moved to until you got a larger board, but once a square was "discovered" (ie could be reached), the number of minimum moves to that square was constant for all boards not smaller than the board on which it was first discovered. (Smaller means less than n OR less than x, not  less than (n * x) )</p>

<p>This tells something powerful, anecdotally. All squares have a number associated with them that must be discovered. This number is a property of the square, NOT the board, and is NOT dependent on size/shape of the board. It is always true. However, if the square cannot be reached, then obviously the number is not applicable.</p>

<p>So you need to find the number of every square on a 200x200 board, and you need a way to see if a board is a subset of another board to determine if a square is reachable.</p>

<p>Remember, in these programming challenges, some questions that are really hard can be solved in O(1) time by using lookup tables. I'm not saying this one can, but keep that trick in mind. For this one, pre-calculating the 200x200 board numbers and saving them in an array could save a lot of time, whether it is done only once on first run or run before submission and then the results are hard coded in.</p>

<p>If the problem needs move sequences rather than number of moves, the idea is the same: save move sequences with the numbers.</p>

python algorithm chess