|
%I M1369 #64 Sep 02 2023 15:13:49
%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="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
| 