I searched for this topic on the web, and found remarkably little. Amanda M. Miller, David L. Farnsworth "Counting the Number of Squares Reachable in k Knight's Moves" Open Journal of Discrete Mathematics, 2013, 3, 151-154 http://dx.doi.org/10.4236/ojdm.2013.33027 does what it says on the tin, but disappointingly avoids any attempt at an explicit distance function. http://www.chessbanter.com/rec-games-chess-misc-chess/30866-counting-knight-... --- one of four strangely similar posts --- puffs to almost universal disdain << Fortunately, there's a better way. I'm a fan of obscure chess books, so when I was at a local chess store the other day, the book "Knight Moves" by Charles Alexander caught my eye. In it he describes a relatively simple method, which he calls "Alexander's Technique", to count the minimum number of knight moves it would take a knight to move from any given square to any other square. >> Said tome apparently manages to devote 80 pages to this delicate investigation. http://math.stackexchange.com/questions/104700/minimum-number-of-moves-to-re... is frankly feeble. http://stackoverflow.com/questions/2339101/knights-shortest-path-chess-quest... finally turns up something nontrivial: << Note: This question was asked on SACO 2007 Day 1 http://olympiad.cs.uct.ac.za/old/saco2007/day1_2007.pdf And solutions are here http://olympiad.cs.uct.ac.za/old/saco2007/day1_2007_solutions.pdf >> The problem appears as no. 4 on day 1 of the 2007 SA Mathematical Olympiad, posed by one Harry Wiggins. The proposed solution is not explicitly credited, but might well have been prepared by Tommy Cooper --- its "magic formula" transports the knight from [0,0] to [1,1] in zero moves, by way of one of three errors shoehorned into just two lines! Well, if you want a job done properly, do it yourself. A corrected and tested revision of Wiggins' prestidigitation, together with --- in answer to the enquiry from Warren Smith --- a proof of correctness, will follow in a separate post. Magma program is available on request. Fred Lunnon On 3/28/14, Andy Latto <andy.latto@pobox.com> wrote:
On Fri, Mar 28, 2014 at 2:58 PM, Tom Rokicki <rokicki@gmail.com> wrote:
The sequence is for squares at exactly that distance, not squares reachable in that distance or less. Thus, it should increase as order n, not n^2.
oops, sorry! I should read more carefully.
Andy
On Fri, Mar 28, 2014 at 11:20 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Fri, Mar 28, 2014 at 1:16 PM, Marc LeBrun <mlb@well.com> wrote:
="Warren D Smith" <warren.wds@gmail.com> What is the distance between (x1,y1) and (x2,y2) measured in number of knight-moves?
Warren, some years ago I put some "knight metric" sequences in the OEIS. Special-cases to compare with your conjecture: dx,dy =...
...n,0: http://oeis.org/A018837 2[ (n+2)/4 ] if n even, 2[ (n+1)/4 ]+1 if n odd (n >= 8)
...n,n: http://oeis.org/A018839 2*ceiling(n/3), n >= 3
When I follow that link, I don't get knight distance to (n,n); I get a series purporting to be the series for
Squares on infinite chess-board at n moves from center using a {2,3} fairy knight.
But this sequence is incorrect; it claims that the answer is For n >= 8, a(n) = 68n - 72. But that can't be right; you can reach any square within distance n by first going to an appropriate square in a (2,6) neighborhood of the initial square, and then zigzagging to the right to get to a square from which you can get to the desired square in a straight line. Each part of this procedure takes a number of steps linear in n, so the total number of squares at n moves from the center must be of order n^2.
Andy
Also perhaps of interest is the size of the n-move neighborhood, etc. The OEIS has some references as well. Search on "knight" gives many hits.
"Enjoy"! --MLB
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun