This site is supported by donations to The OEIS Foundation.

Knight tours

From OeisWiki
Jump to: navigation, search

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²:
        sequences A326924 (IDs), A326922 (values = Euclidean distance from origin).
      • the taxicab distance or L1-norm, ||(x,y)||1 = |x| + |y|:
        sequence A328908 (IDs), A328928 (values = taxicab distance from origin).
      • the Loo- or sup norm, ||(x,y)||oo = max(|x|, |y|):
        sequences A328909 (IDs) and A328929 (values).
    • 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