This site is supported by donations to The OEIS Foundation.
Knight tours
Contents
Introduction
Here we compile results and references to sequences related to knight tours on an infinite chess board, with squares numbered following an infinite (counter-clockwise) square spiral. On each move, the knight jumps to one of the eight squares it can reach (with coordinates (x+-1, y+-2) or (x+-2, y+-1), if (x, y) are those of the knight), depending on various criteria which result in the different variants of the sequences:
- the knight must jump on a square not visited before, if this is possible. If not, either the sequence ends or there is a special rule for what to do in that case, usually some "back tracking".
- among the possible choices, it must jump on the square satisfying some minimality condition(s) which can be expressed as lexicographic order of a vector of values. That is, each square n (as numbered following the spiral) gets attributed a vector v(n) = (v0(n), v1(n), v2(n), ...), and the knight will choose the square with the lexicographically smallest v(n).
- We then record the tour as the sequence a(k) of numbers (= ID = rank = position in the spiral) of the squares in the order they are visited. Usually we start out with a(0) = 0 referring to initial position at the center of the spiral. (In some variants the central square has number 1.)
- Associated to the sequence of "positions" there is the sequence of "values" associated with ("written on") the squares and serving as main criterion for the choice of the next move (after the criterion of being unvisited, and before additional criteria serving as tie breakers, if needed).
More technical details follow below.
Numbering of the squares
The squares may be identified by Cartesian coordinates (x,y) ∈ Z × Z, but also by a number or ID which is the rank in the square spiral starting at (0,0) in positive x direction, and turning counter-clockwise:
64--63--62--61--60--59--58--57--56 ... | | | 65 36--35--34--33--32--31--30 55 88 | | | | | 66 37 16--15--14--13--12 29 54 87 | | | | | | | 67 38 17 4---3---2 11 28 53 86 | | | | | | | | | 68 39 18 5 0---1 10 27 52 85 | | | | | | | | 69 40 19 6---7---8---9 26 51 84 | | | | | | 70 41 20--21--22--23--24--25 50 83 | | | | 71 42--43--44--45--46--47--48--49 82 | | 72--73--74--75--76--77--78--79--80--81
Some sequences (e.g., A316667) use a numberig starting at 1 in the center (and also offset = 1 for the initial position), but the most canonical sequence A316328: "Lexicographically earliest knight's path on spiral on infinite chessboard", starts at 0.
The x- and y-coordinate of the square numbered n are given by A174344(n) and A274923(n); sequence A296030 lists the pairs (x,y). A PARI/GP function coords(n) which returns the pair (A174344(n), A274923(n)) is given in A316328, A328908 and many others.
The numbers on the four rays starting at the center (0,0) in diagonal directions are
- NE: A002939(n) = 2n(2n-1): (0, 2, 12, 30, ...),
- NW: A016742(n) = 4n^2: (0, 4, 16, 36, ...),
- SW: A002943(n) = 2n(2n+1): (0, 6, 20, 42, ...),
- SE: A033996(n) = 4n(n+1): (0, 8, 24, 48, ...).
A formula and/or program which gives the number of the square as function of (x,y) is yet to be written.
List of the "tour" sequences
length ID of k-th value on square first tie second tie Comments of seq square visited at move k breaker breaker 2015 A316328 A316328: ID -- -- no tie breaker needed since ID unique. A323809 = infinite extension 2015 A316667 A316667: ID+1 -- -- as above, but squares numbered starting at 1. A323808 = infinite extension 22325 A326924 A326922: L2-norm ID -- "value" is x² + y² where (x,y) are coordinates of the square 1092366 A328908 A328928: L1-norm ID -- "value" is L1- or taxicab norm |x| + |y| 25108 A328909 A328929: oo-norm ID -- "value" is max(|x|, |y|) 1069 A326916 A326918: digit(n) L2-norm ID digit(n) = A007376(n) = (0,1,2,3,...,9,1,0,1,1,1,2,...) 1217 - A326413: digit(n) L2-norm x-coord a "tie" could still occurs but doesn't, in this sequence. 644 - A328698: digit(n) L2-norm angle Preferred direction = turn to the left w.r.t. previous leap.
Choosing the square
As outlined in the introduction, the choice of square to go to at a given move can formulated by associating to each square n under consideration a vector v(n) = (v0(n), v0(n), ...) such that the lexicographically smallest vector corresponds to the square that should be chosen.
- v0(n) may be taken as the number of times the knight has visited that square. Then all unvisited squares will be considered before any square that has already been visited. One can also start the vector v with component v1 as below, and set that value to +oo if the square was already visited.
- v1(n) is in some sense the main criterion, if one considers v0(n) = 0 as an unconditional requirement. Often the board is presented as squares filled with these numbers v1(n), and the knight must jump to the square with the least value written on it. Then in general subsequent criteria will be needed as "tie breakers", to fix the choice in case several available squares have the same minimal value v1(n). The "knight tour" is sometimes considered as the sequence of these values v1(n), rather than the sequence of the ID numbers of the squares, cf. second column of A-numbers in the table above.
- A "canonical" choice is to take v1(n) = n, so the "least value" to be found by the knight means the square coming earliest on the spiral. Since these ID's are unique, there is no further "tie breaker" after this criterion. By definition, here the sequence of IDs of the visited squares is the same as the sequence of "values" v1(n) = n on these squares.
- Another "general" choice is the distance of the square from the origin. (The above choice of v1(n)=n can be seen as a special case of this.) In particular we consider:
- the Euclidean distance or L2-norm, usually squared, (||(x,y)||2)2 = x² + y²:
- the taxicab distance or L1-norm, ||(x,y)||1 = |x| + |y|:
- the Loo- or sup norm, ||(x,y)||oo = max(|x|, |y|):
- One quite different choice is to let v1(n) = A007376(n), the n-th digit of the infinite Barbier word 0,1,2,...,9,1,0,1,1,1,2,.... Then we choose the Euclidean distance as first tie-breaker v2(n), and depending on the second tie-breaker we get sequence A326413 (values v1(n) for v3(n) = the x-coordinate) and A326916 & A326918 (v3(n) = n).
- The tie-breakers need not to depend statically on n, for example, one could use in any of the above v2(n) = absolute value of the angle between and , where P, Q, R are the current position, destination square under consideration, and the previous position. This means that the knight would prefer, in case of a tie, to go straight on into the same direction as before, or change it as little as possible.
Infinite extensions
Originally these sequences were defined to end when the knight gets "trapped" in a position a(N) from where it cannot reach any unvisited square. However, any such sequence will be equal to the restriction to 0..N of its infinite extension according to the rule:
- Go back to the previously visited square(s) a(N-1), a(N-2), ... until an unvisited square is within reach. (If it must go back M moves, this means that a(N+m) = a(N-m) for m = 1, ..., M, before a(N+M+1) = the second best choice that was possible when the knight moved from a(N-M) to a(N-M+1).)
- This way the infinite extensions A323808 and A323809 of A316667 and A316328, respectively, are obtained.
Other ways of defining infinite extensions could be possible. For example, one could decide to use the same vector v(n) to make the choice, but now to choose the lexicographically largest one. In case the main criterion was the distance from the origin, the knight would then move as far as possible away from the origin - of course only as long as there is no unvisited square within reach.
Surjectivity
It is interesting to study whether there could remain unvisited squares in any of the considered variants. I.e., can there be a square which will never be visited in one of the infinite extensions?
Obviously, for all finite sequences, almost all squares of the infinite board will never be visited. If one does not wish to consider an infinite extension of the sequence, one can only ask whether there are "maximal" subsets of unvisited squares which cannot not be reached from "outside" due to lack of an unvisited square in their neighborhood. (A square may be unreachable even if it has an unvisited neighbor, in case the two taken together do not have an unvisited neighbor square.)
Interestingly enough, the list A316338 of unvisited squares for the sequence A316328 ("lex.first knight tour") starts with squares from the very border of the visited zone, which suggests that the infinite extension might not lack any number.
Is this really the case? What about the variants?
See also
(...)
Authorship
M. F. Hasler, Knight tours.— From the On-Line Encyclopedia of Integer Sequences® Wiki (OEIS® Wiki). [https://oeis.org/wiki/Knight_tours], initial version Nov. 2, 2019