Knight's Shortest Path Chess Question

Question

I've been practicing for an upcoming programming competition and I have stumbled across a question that I am just completely bewildered at. However, I feel as though it's a concept I should learn now rather than cross my fingers that it never comes up.

Basically, it deals with a knight piece on a chess board. You are given two inputs: starting location and ending location. The goal is to then calculate and print the shortest path that the knight can take to get to the target location.

I've never dealt with shortest-path-esque things, and I don't even know where to start. What logic do I employ to go about tackling this?

P.S. If it's of any relevance, they want you to supplement the Knight's normal move ability by also allowing it to move to the four corners of the square a Knight's move paths create if in the center of the board.

Answer 1

You have a graph here, where all available moves are connected (value=1), and unavailable moves are disconnected (value=0), the sparse matrix would be like:

(a1,b3)=1,
(a1,c2)=1,
  .....

And the shortest path of two points in a graph can be found using http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Pseudo-code from wikipedia-page:

   function Dijkstra(Graph, source):
   for each vertex v in Graph:           // Initializations
       dist[v] := infinity               // Unknown distance function from source to v
       previous[v] := undefined          // Previous node in optimal path from source
   dist[source] := 0                     // Distance from source to source
   Q := the set of all nodes in Graph
   // All nodes in the graph are unoptimized - thus are in Q
   while Q is not empty:                 // The main loop
       u := vertex in Q with smallest dist[]
       if dist[u] = infinity:
          break                         // all remaining vertices are inaccessible from source
       remove u from Q
       for each neighbor v of u:         // where v has not yet been removed from Q.
           alt := dist[u] + dist_between(u, v) 
           if alt < dist[v]:             // Relax (u,v,a)
               dist[v] := alt
               previous[v] := u
   return dist[]

EDIT:

1. as moron, said using the http://en.wikipedia.org/wiki/A*_algorithm can be faster.
2. the fastest way, is to pre-calculate all the distances and save it to a 8x8 full matrix. well, I would call that cheating, and works only because the problem is small. But sometimes competitions will check how fast your program runs.
3. The main point is that if you are preparing for a programming competition, you must know common algorithms including Dijkstra's. A good starting point is reading Introduction to Algorithms ISBN 0-262-03384-4. Or you could try wikipedia, http://en.wikipedia.org/wiki/List_of_algorithms

Answer 2

What you need to do is think of the possible moves of the knight as a graph, where every position on the board is a node and the possible moves to other position as an edge. There is no need for dijkstra's algorithm, because every edge has the same weight or distance (they are all just as easy or short to do). You can just do a BFS search from your starting point until you reach the end position.

Answer 3

Yes, Dijkstra and BFS will get you the answer, but I think the chess context of this problem provides knowledge that can yield a solution that is much faster than a generic shortest-path algorithm, especially on an infinite chess board.

For simplicity, let's describe the chess board as the (x,y) plane. The goal is to find the shortest path from (x0,y0) to (x1,y1) using only the candidate steps (+-1, +-2) and (+-2, +-2), as described in the question's P.S.

Here is the new observation: draw a square with corners (x-4,y-4), (x-4,y+4), (x+4,y-4), (x+4,y+4). This set (call it S4) contains 32 points. The shortest path from any of these 32 points to (x,y) requires exactly two moves.

The shortest path from any of the 24 points in the set S3 (defined similarly) to (x,y) requires at least two moves.

Therefore, if |x1-x0|>4 or |y1-y0|>4, the shortest path from (x0,y0) to (x1,y1) is exactly two moves greater than the shortest path from (x0,y0) to S4. And the latter problem can be solved quickly with straightforward iteration.

Let N = max(|x1-x0|,|y1-y0|). If N>=4, then the shortest path from (x0,y0) to (x1,y1) has ceil(N/2) steps.