cp's OEIS Frontend

A359740 Maximal number of moves needed by a knight to reach every cell from a fixed position on an n X n X n chessboard, or -1 if it is not possible to reach every square.

%I A359740 #40 Feb 16 2025 08:34:04
%S A359740 0,-1,-1,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,
%T A359740 26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,
%U A359740 49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67
%N A359740 Maximal number of moves needed by a knight to reach every cell from a fixed position on an n X n X n chessboard, or -1 if it is not possible to reach every square.
%C A359740 The author conjectures that, for any n greater than 3, a(n) = n, while all the 10 independent cases has been manually checked for n = 5 and n = 6 (if n = 4, there are only 4 cases to be checked in order to show that a(4) = 4).
%C A359740 As noted by Eric Weisstein in A232007, a(n) is the graph diameter of the n X n X n knight graph (or -1 if the graph is disconnected).
%C A359740 In general, by assuming n > 3, it is not hard to prove that d(n,k)(N), the knight graph diameter for a k-dimensional n X n X ... X n board, belongs to the closed interval [(ceiling(n*sqrt(k))/sqrt(5), k*n] if n is odd and to [(ceiling(n*sqrt(k))/sqrt(5), k*(n + 1)] if n is even.
%C A359740 From _Pontus von Brömssen_, Jan 13 2023: (Start)
%C A359740 a(n) >= n can be proved by showing that at least n moves are required to go from a corner cell to a cell adjacent to the diagonally opposite corner: First note that the (Manhattan) distance between those two cells is 3(n-1)-1, and each knight move changes the distance by at most 3, so we need at least n-1 moves. Color each cell black or white according to the parity of the sum of the coordinates. Then each move changes the color of the current cell. The starting cell and the target cell have the same color if n is even and different colors if n is odd. This means that after n-1 moves we are at the wrong color, so we need at least n moves. (End)
%C A359740 From _Michael S. Branicky_, Jan 21 2023: (Start)
%C A359740 For n > 5, a(n) <= max{a(n-1)+1, a(n-2)+2} since all but the corner in the newly added n-th "shell" has a neighbor in the (n-1)-th shell, and the corner has a neighbor at distance 2 in the (n-2)-th shell.
%C A359740 Combining with the lower bound above, a(n) = n for n > 3 by induction. (End)
%H A359740 Michael S. Branicky, <a href="/A359740/a359740.py.txt">Python program computing graph diameter explicitly</a>
%H A359740 David Hartenstine, <a href="https://www.math.utah.edu/mathcircle/notes/distance.pdf">Distance and Metric Spaces</a>
%H A359740 MathOverflow, <a href="https://mathoverflow.net/questions/437443/chess-pieces-metrics-in-higher-dimensions">MathStackExchange discussion concerning chess pieces metrics on k-dimensional boards</a>
%H A359740 Marco Ripà, <a href="https://arxiv.org/abs/2311.00016">Metric spaces in chess and international chess pieces graph diameters</a>, arXiv:2311.00016 [math.HO], 2023. See pp. 11, 14.
%H A359740 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphDiameter.html">Graph Diameter</a>
%H A359740 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KnightGraph.html">Knight Graph</a>
%F A359740 a(n) = n for n >= 4 (conjectured by author; proved above).
%e A359740 a(4) = 4, since we can reach any cell of a n X n X n chessboard, from any given starting position, by spending at most 4 knight moves. For a 3 X 3 X 3 chessboard, it is impossible to reach the middle cell starting from any other, so a(3) = -1.
%t A359740 Join[{0, -1, -1}, Range[4, 100]] (* _Paolo Xausa_, Jan 31 2024 *)
%Y A359740 Cf. A232007.
%K A359740 sign,easy
%O A359740 1,4
%A A359740 _Marco Ripà_, Jan 12 2023
%E A359740 a(7)-a(38) using linked program, a(39) and beyond using formula from _Michael S. Branicky_, Jan 21 2023