How many moves does a knight need to get somewhere?

I just saw a thread about chess on an infinite plain and it reminded me of a problem that was posed some time ago in a different forum. On an infinite chessboard with a marked origin square having coordinates (0,0), what is the smallest number of moves a knight needs to go from the origin to square (x,y), for any given values of x and y? (If a regular board were placed on the infinite board with the a1 square at (0,0), then b4 would be at (1,3), a7 would be at (0,6), e1 would be at (4,0), etc.)

The challenge is to devise a function m(x,y) for the required number of knight moves.

For example, m(2,2)=4, since a knight needs at least four moves to get from a1 to c3, and m(1,1)=2 since a knight can go from a1 to b2 in two moves (remember, it's an infinite board).

I was able to devise a general formula for m(x,y). If someone can do the same, it will be interesting to see how our formulas compare.

If you do come up with a formula, you'll want to test it against a number of knight journeys to see if it always gives the right number of moves. I found a simple online BASIC interpreter called QuiteBASIC that can compute the formula I found. If you paste the program below into the BASIC Program window at http://www.quitebasic.com/prj/basics/helloworld/# and click the run button (right arrow) at the top, it will calculate m(x,y) and show the result in the Output window. Click the run button again to repeat with new values of x and y. (Right-click the link above if you want to open it in a new tab and avoid losing your chess.com tab.)

Since the board is infinite, the knight might have to go a long way. You can check your formula to see if it tells you a knight needs 168 moves to go from square (0,0) to square (200,300). That is, m(200,300)=168.

10 input "Enter x"; x1
15 let x1=round(x1)
20 input "Enter y"; y1
25 let y1=round(y1)
30 let x=abs(x1)
40 let y=abs(y1)
50 if y<x then goto 100
60 let t=x
70 let x=y
80 let y=t
100 if x=1 and y=0 then goto 500
110 if x=2 and y=2 then goto 600
120 if 2*y>x then goto 700
130 let m=x-y-2*floor((x-2*y)/4)
140 goto 1000
500 let m=3
510 goto 1000
600 let m=4
610 goto 1000
700 let m=x-y+2*floor((2*y-x+2)/3)
1000 print "m(";x1;",";y1;")=";m
1010 end

I honestly don’t get it. We need some other people to join. Math has never been my strongsuit.

Here are the number of moves my formula gives for a few more knight journeys. If you do come up with your own formula, check it against these results and let me know if there are any differences. If both formulas are correct, they will give the same results.

m(-1,-2)=1

m(7,7)=6

m(12,-15)=9

m(2163,999)=1082

m(-257,-3186)=1593

hmmm, I put your formulas into excel and I get the same results for coordinates 1 to 4, but I get 1149 for m(-257,-3186) instead of 1593

Interesting, By symmetry, we know m(-257,-3186)=m(3186,257), which are the x and y values for which my formula will give a correct result. Does your excel formula also give 1149 instead of 1593 for m(3186,257)?

Maybe I have one of the switches wrong....

in the case of 2y>x

It seems more likely to me that your excel implementation skipped the coordinate swaps in the first ten steps of the BASIC program, which are part of the formula. The part that comes later only applies to the case 0≤y≤x. It's still a general result, since given an arbitrary square, by symmetry there is always a corresponding square the same number of knight-moves from the origin for which 0≤y≤x. The coordinates of that corresponding square are the ones you need to feed to excel to get the correct answer, if the first steps of the BASIC program were skipped.

#3
On a real chessboard the distance between a1 (0,0) and b2 (1,1) is 4 knight moves, but on an infinite chessboard that extends to negative x or y i.e. integer x and y the distance is 2 knight moves.
So your formula is for a semi-infinite chessboard with natural numbers x and y.

If you run the BASIC program, you'll find that under the formula it implements, m(1,1)=m(-1,1)=m(1,-1)=m(-1,-1)=2 and that x and y can be arbitrarily large positive or negative numbers. Why would you call that semi-infinite?

On a real chess board m(1,1) = 4

Yes, and on an infinite chess board m(1,1)=2, which agrees with my formula for an infinite chess board. I'm really not sure what point you are trying to make.

#14
Just pointing out infinite board =/ real board, regarding a1 to b2

Please tell me more about this "semi-infinite chessboard" you brought up. What is it like? What is m(1,1) on a "semi-infinite chessboard"?

on a real chess board with x = 0 to 7 and y = 0 to 7, m(1,1) = 4
on a semi-infinite chess board with x = 0 to infinity and y = 0 to infinity m(1,1) = 4
on an infinite chess board with x = -infinity to +infinity and y = -infinity to +infinity m(1,1) = 2

And where is your knight's starting position on the infinite board?

In variants, it's not usually in the same place as a regular board. May be causing some confusion.

So m(1,1)=2 on an infinite chess board, and m(1,1)=4 on a semi-infinite chess board.

My formula gives m(1,1)=2. Why did you say in #11 that it is the formula for a semi-infinite chessboard?

are you looking at an 8x8 or an 8x10 board?