|
| |
|
|
A344046
|
|
Squares visited by a knight moving on a spirally numbered board where the knight moves to the smallest unvisited square using the fewest possible steps. If two or more equal length paths exist it chooses the path with the lowest sum of visited numbers, and if two paths have the same sum of visited numbers it chooses the one that visits the smallest number.
|
|
2
|
|
|
|
1, 14, 5, 2, 15, 6, 3, 8, 11, 4, 7, 46, 9, 12, 53, 10, 51, 28, 13, 58, 33, 16, 19, 68, 17, 64, 35, 18, 69, 20, 23, 76, 21, 72, 41, 22, 77, 24, 27, 50, 25, 80, 47, 26, 83, 52, 29, 32, 57, 30, 89, 54, 31, 92, 59, 34, 97, 36, 39, 104, 37, 100, 63, 38, 105, 40, 107, 42, 45, 114, 43, 110, 71, 44, 115
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The knight starts on square 1 and then moves to the lowest unvisited square using the fewest possible steps. At the start the lowest unvisited square is the adjacent square numbered 2. This takes three steps, and there are twelve different 3-step paths that can be taken to reach it. The knight therefore chooses the path with the lowest sum of visited numbers, which is a step to 14, then 5, then to 2. The lowest unvisited square is now 3, and it can be reached in three steps, the lowest sum path of which is steps to 15, then 6, then 3. The next lowest unvisited square numbered 4 can be visited similarly, via 8 and 11. The next lowest unvisited square is now 7, as 5 and 6 have been visited in the previous steps, and from 4 the square numbered 7 can be reached in one step. After 7 the next lowest unvisited square is 9.
The sequence lists all the numbers visited by the knight using the above step rules.
The sequence is finite. After 929 total steps the square numbered 800 is reached, after which all eight neighboring squares of 800 have been visited, so the knight has no path to the next lowest unvisited square, which is 804.
The longest path between the previous and the next lowest unvisited square is an 11-step path between 281 to 300, via squares 432, 355, 522, 437, 360, 363, 446, 537, 450, 371. See the linked image.
|
|
|
LINKS
|
Scott R. Shannon, Image showing the 930 visited squares. The starting square is highlighted in white, the visited squares in yellow, the final square in red, while the path is colored across the spectrum to show the relative step ordering. The longest path between the previous and next lowest unvisited square is lined in black. The visited squares are numbered in blue text for next lowest unvisited squares that are reached from the previous lowest, while those numbered in white are visited as a part of reaching a smaller unvisited square.
|
|
|
EXAMPLE
|
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
.
See the comments for a(1) to a(11).
a(12) = 46, a(13) = 9. After a(11) = 7 the next lowest unvisited square is 9, and that can be reached in two steps via 49 and then 9. No other 2-step path exists.
a(26) = 64, a(27) = 35, a(28) = 18. From a(25) = 17 the next lowest unvisited square is the adjacent square 18, which can be reached in three steps. Two paths exist which have a visited number sum of 117; one is 17 to 64 to 35 to 18, and the other is 17 to 62 to 37 to 18. As the first path visits 35, which is the smallest of the intermediate visited squares, that is the path chosen.
a(927) = 917, a(928) = 802, a(929) = 1043, a(930) = 800. From a(926) = 798 there are two 4-step paths to 800, and the chosen one has the lowest visit number sum. However after reaching 800 all eight neighboring squares of 800 have been visited, so the sequence terminates leaving 804 as the next lowest unvisited square.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,fini
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
