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>I suggest:</p>

<ol>
<li>Use BFS backwards from the target location to calculate (in just O(nx) total time) the minimum distance to the target (x, n) in knight's moves <em>from each other square</em>.  For each starting square (i, j), store this distance in d[i][j].</li>
<li>Calculate c[i][j], the number of minimum-length paths starting at (i, j) and ending at the target (x, n), recursively as follows:

<ul>
<li>c[x][n] = 1</li>
<li>c[i][j] = the sum of c[p][q] over all (p, q) such that both

<ul>
<li>(p, q) is a knight's-move-neighbour of (i, j), and</li>
<li>d[p][q] = d[i][j]-1.</li>
</ul></li>
</ul></li>
</ol>

<p>Use <a href="https://en.wikipedia.org/wiki/Memoization" rel="nofollow">memoisation</a> in step 2 to keep the recursion from taking exponential time.  Alternatively, you can compute c[][] bottom-up with a slightly modified second BFS (also backwards) as follows:</p>

<pre><code>c = x by n array with each entry initially 0;
seen = x by n array with each entry initially 0;
s = createQueue();
push(s, (x, n));

while (notEmpty(s)) {
    (i, j) = pop(s);
    for (each location (p, q) that is a knight's-move-neighbour of (i, j) {
        if (d[p][q] == d[i][j] + 1) {
            c[p][q] = c[p][q] + c[i][j];
            if (seen[p][q] == 0) {
                push(s, (p, q));
                seen[p][q] = 1;
            }
        }
    }
}
</code></pre>

<p>The idea here is to always compute c[][] values for all positions having some given distance from the target before computing any c[][] value for a position having a larger distance, as the latter depend on the former.</p>

<p>The length of a shortest path will be d[1][1], and the number of such shortest paths will be c[1][1].  <strong>Total computation time is O(nx)</strong>, which is clearly best-possible in an asymptotic sense.</p>

python algorithm chess