Calculate the number of moves requires for a knight chess piece It's possible to work out the number of moves required to move from (0, 0) to (A, B) for a knight on an infinite chess board in O(1) time.

This is an attempt at a solution to do it in O(n) time, where n is the number of moves required.

#define ABS(a) ({ typeof (a) _a = (a); _a &gt; 0 ? _a : -_a; })

int movesRequired(int A, int B) {
    int X = 0, Y = 0;
    int count = 0;
    if (!(((A-X) % 2) ^ ((Y-B) % 2)))
        return -1;
    while (X != A &amp;&amp; Y != B) {
        int distX = A-X;
        int distY = B-Y;
        if (ABS(distX) &gt; ABS(distY)) {
            X += distX&gt;0?2:-2;
            Y += distY&gt;0?1:-1;
        } else {
            X += distX&gt;0?1:-1;
            Y += distY&gt;0?2:-2;
        }
        count++;
    }
    return count;
}


It returns the minimum moves required, or -1 if it's not possible.

What I'm interested in:


As far as I am aware, this runs in O(n) time. However, I may not be correct. Does it?
Is there a way to improve my algorithm so it runs in O(n) time?
\$O(1)\$ Discussion


  Is it possible to calculate the distance in \$O(1)\$ time complexity?


Yes, it is.

This problem is called the "Knight's distance" problem, and googling it find a number of references.

This problem was posed as part of the South African "Computer Olympiad" in 2007 for high-school students to solve.... (I know, kids these days.... :) ). The specification was such that some input values for the programs were large enough that \$O(n)\$ solutions would fail to compute in the required time limits, so to get full marks you needed to (devise, and) compute the \$O(1)\$ system.

The problem description, and enough of the description of the \$O(1)\$ solution are available. In case the .za net goes dead, here's the description of the solution:


  4 The Knights Who Say Ni
  
  The (x, y)-coordinates in the 50% constraints are small enough to
  generate a full grid of the minimum number of moves required to get
  from any point to (0,0). The grid can be generated by a breadth-first
  search (BFS).
  
  We know that getting to (0,0) requires 0 moves. We therefore know that
  the points (1,2), (2,1) and the other six movements each require 1
  move. From each of those points with a shortest distance of 1, we can
  take another step in each direction for a shortest path of 2. However,
  some moves will bring us back to a point we have already found a
  shorter distance for and we therefore discard such moves. We continue
  this until the grid is full and then use the grid to find the
  distances for each knight.
  
  To get 100%, a lot of scribbling on paper is required to make some key
  observations and work out some formulae. The first thing to note is
  that the grid is symetrical along the x, y axis and the lines y = ±x.
  You can therefore convert all points (x, y) into an equivalent
  point such that the new 0 ≤ y ≤ x.
  
  The magic formula is:
  
  $$
f(x, y) = \left\{
 \begin{array}{ll}
  2 \left\lfloor \frac{y - \delta}{3} \right\rfloor  + \delta &amp; \mbox{if } y &gt; \delta \\
  \delta - 2 \left\lfloor \frac{\delta - y}{4} \right\rfloor &amp; \mbox{otherwise}
 \end{array}
\right.
$$
  
  where \$δ = x − y\$.


Are there mistakes

Yes.... All squares are accessible to the knight. Why do you have a restriction?

I put your code in to an Ideone that loops through the 100 targets in positions (0,0) through (9,9).... and its results are disappointing... Does your code work?

NO. it does not. It produces wildly wrong values.....

Now, the algorithm I referenced above does not seem to be producing good values either (at least a short range....), but seriously? Your code hardly works at all :(

Lots, and lots of -1 distances, and lots and lots of 0.....