A001230 -id:A001230 - cp's OEIS frontend

A070030 Number of closed Knight's tours on a 3 X 2n board.

0, 0, 0, 0, 16, 176, 1536, 15424, 147728, 1448416, 14060048, 136947616, 1332257856, 12965578752, 126169362176, 1227776129152, 11947846468608, 116266505653888, 1131418872918784, 11010065269439104, 107141489725900544, 1042616896632882688, 10145938076107491328

Offset: 1

Noam D. Elkies, Apr 13 2002

Leonhard Euler stated that no such tours are possible [Memoires Acad. Roy. Sci. (Berlin, 1759), 310-337], and many authors echoed this statement until Ernest Bergholt exhibited solutions for 2n=10 and 12 in British Chess Magazine 1918, page 74. The full set of 16 solutions for 2n=10 was published by Kraitchik in 1927. - Don Knuth, Apr 28 2010
Obtained independently by Don Knuth and Noam D. Elkies in April 1994, both using the transfer-matrix method (in slightly different ways). For this method, see for instance chapter 4.7 of R. P. Stanley's Enumerative Combinatorics, Vol. 1 (1986).
Ian Stewart, Mathematical Recreations column, Scientific American, February 1998, "Feedback", page 95, reports that Richard Ulmer of Denver has sent him a letter reporting work on this subject, about which he is writing a thesis, giving the terms though a(21). - N. J. A. Sloane, Mar 01 2018

			The smallest 3 X 2n board admitting a closed Knight's tour is the 3 X 10, on which there are 16 such tours.

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

Alois P. Heinz, Table of n, a(n) for n = 1..1000
N. D. Elkies and R. P. Stanley, The mathematical knight, Math. Intelligencer, 25 (No. 1) (2003), 22-34.
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).
Eric Weisstein's World of Mathematics, Knight's Tour

See also A169764, which gives the number of closed Knight's tours on a 3 X n board. Cf. A169696, A169765-A169777, A001230.

Cf. A158074, A383660.

Rest[CoefficientList[Series[16 * (x^5 + 5*x^6 - 34*x^7 - 116*x^8 + 505*x^9 + 616*x^10 - 3179*x^11 - 4*x^12 + 9536*x^13 - 8176*x^14 - 13392*x^15 + 15360*x^16 + 13888*x^17 + 2784*x^18 - 3328*x^19 - 22016*x^20 + 5120*x^21 + 2048*x^22) / (1 - 6*x - 64*x^2 + 200*x^3 + 1000*x^4 - 3016*x^5 - 3488*x^6 + 24256*x^7 - 23776*x^8 - 104168*x^9 + 203408*x^10 + 184704*x^11 - 443392*x^12 - 14336*x^13 + 151296*x^14 - 145920*x^15 + 263424*x^16 - 317440*x^17 - 36864*x^18 + 966656*x^19 - 573440*x^20 - 131072*x^21), {x, 0, 30}], x]] (* Vaclav Kotesovec, Mar 03 2016 *)

g = 16 * (z^5 + 5*z^6 - 34*z^7 - 116*z^8 + 505*z^9 + 616*z^10 - 3179*z^11 - 4*z^ 12 + 9536*z^13 - 8176*z^14 - 13392*z^15 + 15360*z^16 + 13888*z^17 + 2784*z^18 - 3328*z^19 - 22016*z^20 + 5120*z^21 + 2048*z^22) / (1 - 6*z - 64*z^2 + 200*z^3 + 1000*z^4 - 3016*z^5 - 3488*z^6 + 24256*z^7 - 23776*z^8 - 104168*z^9 + 203408*z^1 0 + 184704*z^11 - 443392*z^12 - 14336*z^13 + 151296*z^14 - 145920*z^15 + 263424* z^16 - 317440*z^17 - 36864*z^18 + 966656*z^19 - 573440*z^20 - 131072*z^21); g = g + O(z^31); vector(30,n,polcoeff(g,n))

Generating function: 16 * (z^5 + 5*z^6 - 34*z^7 - 116*z^8 + 505*z^9 + 616*z^10 - 3179*z^11 - 4*z^12 + 9536*z^13 - 8176*z^14 - 13392*z^15 + 15360*z^16 + 13888*z^17 + 2784*z^18 - 3328*z^19 - 22016*z^20 + 5120*z^21 + 2048*z^22) / (1 - 6*z - 64*z^2 + 200*z^3 + 1000*z^4 - 3016*z^5 - 3488*z^6 + 24256*z^7 - 23776*z^8 - 104168*z^9 + 203408*z^10 + 184704*z^11 - 443392*z^12 - 14336*z^13 + 151296*z^14 - 145920*z^15 + 263424*z^16 - 317440*z^17 - 36864*z^18 + 966656*z^19 - 573440*z^20 - 131072*z^21).
Asymptotic value .0001899*3.11949^(2n). - Don Knuth, Apr 28 2010. More decimal places: a(n) ~ 0.0001898644879979384968655648993009439045986223511152141689341... * 3.1194904567551021585814810124470909514449088706168023079811958...^(2*n). - Vaclav Kotesovec, Mar 03 2016
a(n) = A158074(n)/2. - Eric W. Weisstein, Mar 18 2009
Recurrence (D. E. Knuth and N. D. Elkies, 1994): a(n) = 6*a(n-1) + 64*a(n-2) - 200*a(n-3) - 1000*a(n-4) + 3016*a(n-5) + 3488*a(n-6) - 24256*a(n-7) + 23776*a(n-8) + 104168*a(n-9) - 203408*a(n-10) - 184704*a(n-11) + 443392*a(n-12) + 14336*a(n-13) - 151296*a(n-14) + 145920*a(n-15) - 263424*a(n-16) + 317440*a(n-17) + 36864*a(n-18) - 966656*a(n-19) + 573440*a(n-20) + 131072*a(n-21), for n>=23. - Vaclav Kotesovec, Mar 03 2016
a(n) = A383660(3n). - Don Knuth, May 05 2025

Comment corrected by Johannes W. Meijer, Nov 22 2010

A140519 Number of (undirected) Hamiltonian cycles on the n X n king graph.

Original entry on oeis.org

1, 3, 16, 2830, 2462064, 22853860116, 1622043117414624, 961742089476282321684, 4601667243759511495116347104, 179517749570891592016479828267003018, 56735527086758553613684823040730404215973136, 145328824470156271670635015466987199469360063082789418

Offset: 1

Don Knuth, Jul 26 2008

Or, number of Hamiltonian cycles in the graph P_n X P_n (strong product of two paths of length n-1).
If the direction of the tour is to be taken into account, the numbers for n > 1 must be multiplied by 2 (see A140521).
Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

D. E. Knuth, The Art of Computer Programming, Section 7.1.4, in preparation.

N. J. A. Sloane, Table of n, a(n) for n = 1..16 [From Pettersson 2014]
Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Dissertation, Aalto, Finland, 2015.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, King Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A001230, A140521.

New name from Eric W. Weisstein, May 06 2019

A165134 Number of directed Hamiltonian paths in the n X n knight graph.

Original entry on oeis.org

1, 0, 0, 0, 1728, 6637920, 165575218320, 19591828170979904

Offset: 1

[No name given] (c.candide(AT)free.fr), Sep 04 2009

Previous name was: Number of knight's paths visiting each square of an n X n chessboard exactly once.

			From _Gheorghe Coserea_, Oct 08 2016: (Start)
For n=5 the numbers in the table below give the number of knight's paths starting at the respective position on the 5 X 5 chessboard.  In total there are a(5) = 304*4 + 56*8 + 64 = 1728 solutions.
    [1]  [2]  [3]  [4]  [5]
[1] 304    0   56    0  304
[2]   0   56    0   56    0
[3]  56    0   64    0   56
[4]   0   56    0   56    0
[5] 304    0   56    0  304
(End)

Stefan Behnel, The Knight's Paths
A. Chernov, Open knight's tours
Gheorghe Coserea, Solutions for 5x5 chessboard
P. Hingston, G. Kendall, Enumerating knight's tours using an ant colony algorithm, The 2005 IEEE Congress on Evolutionary Computation, 2 (2006), 1003-1010
G. Stertenbrink, Number of Knight's Tours
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Knight Graph

Cf. Undirected Hamiltonian paths: A169696 (3 X n), A079137 (4 X n), A083386 (5 X n), A306281 (6 X n), A306283 (7 X n), A308131 (n X n).

Cf. A001230, A118067, A306282.

a(7) from Guenter Stertenbrink, added by Alex Chernov, Sep 01 2013
a(1)=1, a(2)=0 prepended by Max Alekseyev, Sep 22 2013
a(8) from Alex Chernov, May 10 2014
Name made more precise by Eric W. Weisstein, Apr 14 2019

A140521 Number of directed "king tours" on an n X n board.

Original entry on oeis.org

1, 6, 32, 5660, 4924128, 45707720232, 3244086234829248, 1923484178952564643368

Offset: 1

Don Knuth, Jul 26 2008

Or, number of directed Hamiltonian cycles in the graph P_n X P_n.
If the direction of the tour is not taken into account, the numbers for n > 1 must be halved (see A140519).
Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 2009.

Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, King Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A001230, A140519.

A186441 Number of n-vertex knight's tours on the 8x8 chessboard summed over all choices for the starting position.

Original entry on oeis.org

64, 336, 1672, 8320, 39616, 186544, 847520, 3846192, 16784384, 72946352, 304472976, 1265186112

Offset: 1

N. J. A. Sloane, Feb 21 2011

			a(1) = 64, since the knight cannot move.

L. Lant, A method for calculating the Knight's total tour count, Congress. Numerant., 202 (2010), 33-40. [Lant comments that "a(5)=40208 has not yet been verified."]

Ron Hardin, Knight's tour A186441, seqfan mailing list Feb 23 2011

Cf. A001230.

Column 6 of A186851

a(n) = row(n,6)[6] \\ row(m,n) defined in A186851. - Andrew Howroyd, Jan 02 2023

a(5) to a(8) are tabulated here as computed by R. H. Hardin and D. S. McNeil.
Ambiguous a(0) removed by Max Alekseyev, Sep 22 2013
a(9)-a(12) from Andrew Howroyd, Jan 02 2023

A368499 Number of non-congruent simple polygons with 2n sides on the unbounded chessboard such that each side is an edge of the corresponding knight graph.

Original entry on oeis.org

3, 13, 178, 3034, 64877, 1503790, 36930111

Offset: 2

Kaloyan Kapralov, Dec 27 2023

A knight graph is a graph that represents all legal moves of the knight chess piece on a chessboard. Each vertex of this graph represents a square of the chessboard, and each edge connects two squares that are a knight's move apart from each other.
Two polygons in the knight graph are called congruent if one can be transformed into the other by applying one or more of the operations of translation, rotation, and reflection on the chessboard; otherwise, they are non-congruent.
This sequence, in contrast to A366778, considers only simple, i.e., non-self-intersecting polygons.

			For n=2 the a(2)=3 solutions (in standard chess notation) are:
  (a1,c2,d4,b3), (a2,c1,d2,c3), (a2,c1,d3,b3).
For n=3 the a(3)=13 solutions are:
  (a1,b3,a5,c4,e3,c2), (a1,b3,a5,c6,b4,c2), (a1,b3,a5,c6,d4,c2),
  (a1,b3,c5,e6,d4,c2), (a2,b4,c2,d4,e2,c1), (a2,b4,c6,d4,b3,c1),
  (a2,b4,c6,d4,e2,c1), (a2,b4,c6,e5,d3,c1), (a2,b4,d5,c3,e2,c1),
  (a2,b4,d5,f4,d3,c1), (a2,b4,d5,f4,e2,c1), (a2,c1,d3,f4,d5,c3),
  (a2,c1,e2,g3,e4,c3).

Stoyan Kapralov, Valentin Bakoev, and Kaloyan Kapralov, Algorithms for Construction and Enumeration of Closed Knight's Paths, Mathematics and Informatics, 2, (2023), 107-114; arXiv:2304.00565 [math.CO], 2023.
Kaloyan Kapralov, Example for n=3: the 13 non-congruent simple polygons.

Cf. A366778, A001230, A234623, A254129, A356404.

A289204 Number of (undirected) paths in the n X n knight graph.

Original entry on oeis.org

0, 0, 56, 14980, 19005336, 278982789260

Offset: 1

Eric W. Weisstein, Jun 28 2017

Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Knight Graph

Cf. A234623, A212715, A165134, A001230.

a(5)-a(6) from Andrew Howroyd, Jul 01 2017

A297666 Number of chordless cycles in the n X n knight graph.

Original entry on oeis.org

0, 0, 1, 64, 651, 4680, 56919, 2578420, 205224704

Offset: 1

Eric W. Weisstein, Jan 02 2018

Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Knight Graph

Cf. A001230, A234623.

a(6)-a(9) from Andrew Howroyd, Jan 08 2018

A366778 Number of nonequivalent cycles of length 2n in the (2n+1) X (2n+1) knight graph.

Original entry on oeis.org

3, 25, 480, 12000, 350256, 10780549, 344680960

Offset: 2

Stoyan Kapralov, Dec 15 2023

A knight graph is a graph that represents all legal moves of the knight chess piece on a chessboard. Each vertex of this graph represents a square of the chessboard, and each edge connects two squares that are a knight's move apart from each other.

Two cycles in the knight graph are called equivalent if one can be obtained from another by applying one or more of the operations of translation, rotation, and symmetry on the chessboard; otherwise, they are nonequivalent.

			For n=2 the a(2)=3 solutions (in standard chess notation) are: (a1, c2, d4, b3), (a2, c1, d2, c3), and (a2, c1, d3, b3).
Note that each of these three cycles is non-self-intersecting. For the remaining values of n there are two kind of cycles - self-intersecting and non-self-intersecting. For example, a self-intersecting cycle of length 6 is (a1, c2, b4, a2, c1, b3), while the cycle (a1, c2, e1, f3, d4, b3) is non-self-intersecting.

Stoyan Kapralov, Valentin Bakoev, and Kaloyan Kapralov, Algorithms for Construction and Enumeration of Closed Knight's Paths, Mathematics and Informatics, 2, (2023), 107-114; arXiv:2304.00565 [math.CO], 2023.

Cf. A368499, A001230, A234623, A254129, A356404.

A037009 Consider an n X n board with a knight's path, not necessarily closed, that visits every square exactly once; number the squares [ 1..n^2 ] along the path; a(n) = maximal number of prime numbered squares that can be attacked by a queen.

Original entry on oeis.org

0, 0, 0, 0, 9, 11, 15, 18, 22, 25

Offset: 1

G. L. Honaker, Jr., Nov 15 1998

Chris K. Caldwell and G. L. Honaker, Jr., Prime Curio for 18
Mike Keith, The Prime Queen Attacking Problem
Jacques Tramu, Le problème de Honaker résolu pour n=9, on Echolalie.
Jacques Tramu, Le problème de Honaker pour n=10.

Cf. A001230.

a(9)-a(10) from Jacques Tramu, Mar 28 2004

cp's OEIS Frontend

A070030 Number of closed Knight's tours on a 3 X 2n board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A140519 Number of (undirected) Hamiltonian cycles on the n X n king graph.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A165134 Number of directed Hamiltonian paths in the n X n knight graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A140521 Number of directed "king tours" on an n X n board.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A186441 Number of n-vertex knight's tours on the 8x8 chessboard summed over all choices for the starting position.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A368499 Number of non-congruent simple polygons with 2n sides on the unbounded chessboard such that each side is an edge of the corresponding knight graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A289204 Number of (undirected) paths in the n X n knight graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A297666 Number of chordless cycles in the n X n knight graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A366778 Number of nonequivalent cycles of length 2n in the (2n+1) X (2n+1) knight graph.

Views

Author

Keywords

Comments

Examples