Knight's Shortest Path on Chessboard

EDIT: See simon's answer, where he fixed the formula presented here.

Actually there is an O(1) formula

This is an image that I've made to visualize it ( Squares a knight can reach on N^th move are painted with same color ).

Can you notice the pattern here?

Although we can see the pattern, it is really hard to find the function f( x , y ) that returns the number of moves required to go from square ( 0 , 0 ) to square ( x , y )

But here is the formula that works when 0 <= y <= x

int f( int x , int y )
{
    int delta = x - y;

    if( y > delta )
        return 2 * ( ( y - delta ) / 3 ) + delta;
    else
        return delta - 2 * ( ( delta - y ) / 4 );
}

Note: This question was asked on SACO 2007 Day 1
And solutions are here

Here's a correct O(1) solution, but for the case where the knight moves like a chess knight only, and on an infinite chess board:

https://jsfiddle.net/graemian/5qgvr1ba/11/

The key to finding this is to notice the patterns that emerge when you draw the board. In the diagram below, the number in the square is the minimum number of moves needed to reach that square (you can use breadth-first search to find this):

Because the solution is symmetrical across the axes and the diagonals, I've only drawn the x >= 0 and y >= x case.

The bottom-left block is the starting position and the numbers in the blocks represent the minimum number of moves to reach those blocks.

There are 3 patterns to notice:

• The incrementing blue vertical groups of 4
• The "primary" red diagonals (they run top-left to bottom-right, like a backslash)
• The "secondary" green diagonals (same orientation as red)

(Make sure you see both sets of diagonals as top-left to bottom-right. They have a constant move-count. The bottom-left top-right diagonals are much more complex.)

You can derive formulas for each. The yellow blocks are special cases. So the solution becomes:

function getMoveCountO1(x, y) {

    var newXY = simplifyBySymmetry(x, y);

    x = newXY.x;
    y = newXY.y;

    var specialMoveCount = getSpecialCaseMoveCount(x ,y);

    if (specialMoveCount !== undefined)
        return specialMoveCount;

    else if (isVerticalCase(x, y))
        return getVerticalCaseMoveCount(x ,y);

    else if (isPrimaryDiagonalCase(x, y))
        return getPrimaryDiagonalCaseMoveCount(x ,y);

    else if (isSecondaryDiagonalCase(x, y))
        return getSecondaryDiagonalCaseMoveCount(x ,y);

}

with the hardest being the vertical groups:

function isVerticalCase(x, y) {

    return y >= 2 * x;

}

function getVerticalCaseMoveCount(x, y) {

    var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);

    var groupIndex = Math.floor( normalizedHeight / 4);

    var groupStartMoveCount = groupIndex * 2 + x;

    return groupStartMoveCount + getIndexInVerticalGroup(x, y);

}

function getIndexInVerticalGroup(x, y) {

    return getNormalizedHeightForVerticalGroupCase(x, y) % 4;

}

function getYOffsetForVerticalGroupCase(x) {

    return x * 2;

}

function getNormalizedHeightForVerticalGroupCase(x, y) {

    return y - getYOffsetForVerticalGroupCase(x);

}

See the fiddle for the other cases.

Maybe there are simpler or more elegant patterns I missed? If so, I would love to see them. In particular, I notice some diagonal patterns in the blue vertical cases, but I haven't explored them. Regardless, this solution still satisfies the O(1) constraint.

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