A344129 The minimum number of steps required for a knight, starting at the central square numbered 1, to reach the square numbered n on a square-spiral numbered board.
0, 3, 2, 3, 2, 3, 2, 3, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3
Offset: 1
Keywords
Examples
The board is numbered with the square spiral: . 17--16--15--14--13 . | | . 18 5---4---3 12 29 | | | | | 19 6 1---2 11 28 | | | | 20 7---8---9--10 27 | | 21--22--23--24--25--26 . a(1) = 0 as the knight starts at the central square numbered 1. a(2) = 3 as it requires 3 steps for a knight to move to any of the four adjacent squares. An example path is 1 - 12 - 15 - 2. a(3) = 2 as it requires 2 steps for a knight to move to any of the four diagonally adjacent squares. An example path is 1 - 10 - 3. a(10) = 1 as the square numbered 10, along with the squares numbered 12, 14, 16, 18, 20, 22, 24, are one direct knight leap away from the starting square. a(13) = 4 as it requires 4 steps for a knight to move to any of the four squares diagonally two squares away. An example path is 1 - 14 - 11 - 4 - 13.
Programs
-
Python
# uses get_coordinate(n) in A296030 KM=[(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)] def next_moves(i, j): return [(i+k, j+m) for k, m in KM] def a(n): start, goal, steps = (0, 0), get_coordinate(n), 0 reach, expand = {start}, {start} while goal not in reach: reach1 = set(m for i, j in expand for m in next_moves(i, j)) expand = reach1 - reach steps, reach, reach1 = steps + 1, reach | reach1, set() return steps print([a(n) for n in range(1, 101)]) # Michael S. Branicky, Jun 15 2021