A169777 Number of geometrically distinct open knight's tours of a 3 X n chessboard.

3, 0, 0, 14, 104, 146, 773, 2698, 14350, 32296, 161714, 460022, 2159794, 5851548, 26468357, 76442996, 330719293, 965759972, 4056479056, 12186078360, 49668414086, 151760518296, 604396415979, 1879966906486, 7330203447133, 23126786408904, 88609897281582

Offset

4,1

References

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

Links

Table of n, a(n) for n=4..30.

George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).

George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).

D. E. Knuth Generating functions for A169770-A169777 and A169696.

Formula

a(n) = A169696(n)/4 + A169776(n)/2.

Example

The three distinct 3x4 tours were published by Euler in Memoires Acad. Roy. Sci. (Berlin, 1759), 310-337.

Prog

(Python)
def a(n):
    moves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
    graph = {(r, c): [(r+dr, c+dc) for dr, dc in moves if 0<=r+dr<3 and 0<=c+dc<n]
             for r in range(3) for c in range(n)}
    paths = []
    def bt(cur, vis):
        if len(vis) == 3*n:
            paths.append(tuple(vis)); return
        for nb in graph[cur]:
            if nb not in vis:
                vis.append(nb)
                bt(nb, vis)
                vis.pop()
    for r in range(3):
        for c in range(n):
            bt((r, c), [(r, c)])
    def canon(p):
        rot = lambda q: tuple((2-r, n-1-c) for r, c in q)
        rh = lambda q: tuple((2-r, c) for r, c in q)
        rv = lambda q: tuple((r, n-1-c) for r, c in q)
        s = set()
        for x in [tuple(p), tuple(reversed(p))]:
            for t in [lambda q:q, rot, rh, rv]:
                s.add(t(x))
        return min(s)
    return len({canon(p) for p in paths}) # Steven Kotlarz, Mar 08 2026

Crossrefs

Cf. A070030, A169696, A169764-A169777.

Sequence in context: A277788 A208848 A277945 * A338464 A278208 A105786

Adjacent sequences: A169774 A169775 A169776 * A169778 A169779 A169780

Keyword

nonn

Author

N. J. A. Sloane, May 10 2010, based on a communication from Don Knuth, Apr 28 2010

Status

approved