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
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
±x. You can therefore convert all points
(x, y) into an equivalent
point such that the new
0 ≤ y ≤ x.
The magic formula is:
δ = 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.....