mohamed.gaber's blog

knigtht's move
By mohamed.gaber, 13 years ago, In English
we have an infinite chess board and we want to move from the position x1,y1 to the position x2,y2 using the minimum number of knight's moves.
I believe that this problem has a constant time solution but i couldn't approach it.
I would be grateful if any one explained the solution of this problem.
Thanks in advance.
  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
This solution is technically constant time: go greedily (in O(1)) to some fixed neighborhood of x2,y2 (say, closer than 20 cells away), then find remaining route with BFS. The "constant" is quite large though. I think, BFS can be replaced with just some cases, which would look more like constant time solution.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    what is the greedy strategy to go to x2,y2 or how can i choose x2,y2.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Probably we need to consider some cases for greedy movement. Let x1=y1=0, x2>=0, y2>=0. If y2>2*x2, we need to make only [-1,+2] and [+1,+2] jumps. Otherwise we need only [+1,+2] and [+2,+1] jumps. We can approximately find how many jumps of each (of two) type we need using two linear equations.
      → Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
I have the following code which solves this problem in constant time but i couldn't understand how it works.

int64 dist(int64 x1, int64 y1, int64 x2, int64 y2)
{
    int64 dx = abs(x2-x1);
    int64 dy = abs(y2-y1);
    int64 lb=(dx+1)/2;
    lb = max(lb, (dy+1)/2);
    lb = max(lb, (dx+dy+2)/3);
    while ((lb%2)!=(dx+dy)%2) lb++;
    if (abs(dx)==1 && dy==0) return 3;
    if (abs(dy)==1 && dx==0) return 3;
    if (abs(dx)==2 && abs(dy)==2) return 4;
    return lb;
}
→ Reply
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    here you go

    http://math.stackexchange.com/questions/1135683/minimum-number-of-steps-for-knight-in-chess
    → Reply