login
Length of uncrossed knight's path on an n X n board.
(Formerly M1369)
12

%I M1369 #68 May 20 2024 13:21:45

%S 0,0,2,5,10,17,24,35,47

%N Length of uncrossed knight's path on an n X n board.

%C I used ZDD techniques to show that a(9)=47. (This is the longest uncrossed knight's path on a 9 X 9 board; thus I confirmed the conjecture that the paths of length 47, found by hand long ago, are indeed optimum.) - _Don Knuth_, Jun 24 2010

%C For best known results see link to Alex Chernov's site. - _Dmitry Kamenetsky_, Mar 02 2021

%D D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, CSLI, Stanford, CA, 2010. (CSLI Lecture Notes, vol. 192)

%D J. S. Madachy, Letter to N. J. A. Sloane, Apr 26 1975.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D Various authors, Uncrossed knight's tours, J. Rec. Math., 2 (1969), 154-157.

%D L. D. Yarbrough, Uncrossed knight's tours, J. Rec. Math., 1 (No. 3, 1969), 140-142.

%H Alex Chernov, <a href="https://web.archive.org/web/20210416192956/http://ukt.alex-black.ru/">Uncrossed Knight's Tours</a>.

%H George Jelliss, <a href="http://www.mayhematics.com/t/2n.htm">Non-Intersecting Paths</a>.

%H J. S. Madachy, <a href="/A003192/a003192_2.pdf">Letter to N. J. A. Sloane, Apr 26 1975</a>.

%H Jean-Charles Meyrignac, <a href="http://euler.free.fr/knight/index.htm">Non-crossing knight tours</a>.

%H N. J. A. Sloane, <a href="/A003192/a003192.gif">Illustration of initial terms</a>

%H Various authors, <a href="/A003192/a003192.pdf">Uncrossed knight's tours</a>, J. Rec. Math., 2 (1969), 154-157. [Annotated scanned copy]

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KnightsTour.html">Knight's Tour</a>

%H L. D. Yarbrough, <a href="/A003192/a003192_1.pdf">Uncrossed knight's tours</a>, J. Rec. Math., 1 (No. 3, 1969), 140-142. [Annotated scanned copy]

%e Lengths of longest uncrossed knight's paths on all sufficiently small rectangular boards m X n, with 3 <= m <= n:

%e ......2...4...5...6...8...9..10

%e ..........5...7...9..11..13..15

%e .............10..14..16..19..22

%e .................17..21..25..29

%e .....................24..30..35

%e .........................35..42

%e .............................47

%Y Cf. A157416.

%K nonn,walk,nice,more,hard

%O 1,3

%A _N. J. A. Sloane_

%E a(1)=a(2)=0 prepended by _Max Alekseyev_, Jul 17 2011