Number of shortest paths

Question

Here is the problem:

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)

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).

My current ideas:

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

Floyd-Warshall shortest path algorithm.

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

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

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

Answer 1

BFS is efficient enough for this problem as it's complexity is O(n*x) since you explore each cell only one time. For keeping the number of shortest paths, you just have to keep an auxiliary array to save them.

You can also use A* to solve this faster but it's not necessary in this case because it is a programming contest problem.

dist = {}
ways = {}

def bfs():
    start = 1,1
    goal = 6,6

    queue = [start]
    dist[start] = 0
    ways[start] = 1

    while len(queue):
        cur = queue[0]
        queue.pop(0)
        if cur == goal:
            print "reached goal in %d moves and %d ways"%(dist[cur],ways[cur])
            return

        for move in [ (1,2),(2,1),(-1,-2),(-2,-1),(1,-2),(-1,2),(-2,1),(2,-1) ]:
            next_pos = cur[0]+move[0], cur[1]+move[1]
            if next_pos[0] > goal[0] or next_pos[1] > goal[1] or next_pos[0] < 1 or next_pos[1] < 1:
                continue
            if next_pos in dist and dist[next_pos] == dist[cur]+1:
                ways[next_pos] += ways[cur]
            if next_pos not in dist:
                dist[next_pos] = dist[cur]+1
                ways[next_pos] = ways[cur]
                queue.append(next_pos)

bfs()

Output

reached goal in 4 moves and 4 ways

Note that the number of ways to reach the goal can get exponentially big

Answer 2

I suggest:

1. 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 from each other square. For each starting square (i, j), store this distance in d[i][j].
2. Calculate c[i][j], the number of minimum-length paths starting at (i, j) and ending at the target (x, n), recursively as follows:
   • c[x][n] = 1
   • c[i][j] = the sum of c[p][q] over all (p, q) such that both
     • (p, q) is a knight's-move-neighbour of (i, j), and
     • d[p][q] = d[i][j]-1.

Use memoisation 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:

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;
            }
        }
    }
}

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.

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

Answer 3

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

Note: Backtracking algorithms can be slow for certain cases and fast for the other

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.

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.

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

Hope this helps!!

Answer 4

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.

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) )

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.

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.

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.

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