A140519 -id:A140519 - cp's OEIS frontend

A003763 Number of (undirected) Hamiltonian cycles on a 2n X 2n square grid of points.

1, 6, 1072, 4638576, 467260456608, 1076226888605605706, 56126499620491437281263608, 65882516522625836326159786165530572, 1733926377888966183927790794055670829347983946, 1020460427390768793543026965678152831571073052662428097106

Offset: 1

Jeffrey Shallit, Feb 14 2002

Orientation of the path is not important; you can start going either clockwise or counterclockwise.
The number is zero for a 2n+1 X 2n+1 grid (but see A222200).
These are also called "closed rook tours".

			a(1) = 1 because there is only one such path visiting all nodes of a square.

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

N. J. A. Sloane, Table of n, a(n) for n = 1..13 (first 11 terms from _Artem M. Karavaev_, Sep 29 2010; a(12) and a(13) from Pettersson, 2014, added by _N. J. A. Sloane_, Jun 05 2015)
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor. 40 (2007) 14667-14678.
Artem M. Karavaev, Hamilton Cycles.
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.
A. Pönitz, Computing invariants in graphs of small bandwidth, Mathematics in Computers and Simulation, 49(1999), 179-191.
A. Pönitz, Über eine Methode zur Konstruktion... PhD Thesis (2004) C.3.
T. G. Schmalz, G. E. Hite and D. J. Klein, Compact self-avoiding circuits on two-dimensional lattices, J. Phys. A 17 (1984), 445-453.
N. J. A. Sloane, Illustration of a(2) = 6.
Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles. [Broken link?]
Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles. [Backup copy of top page only, on the Internet Archive]
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Ed Wynn, Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs, arXiv preprint arXiv:1402.0545 [math.CO], 2014.
Index entries for sequences related to graphs, Hamiltonian.

Other enumerations of Hamiltonian cycles on a square grid: A120443, A140519, A140521, A222200, A222201.

a(n) = A321172(2n,2n). - Robert FERREOL, Apr 01 2019

Two more terms from Andre Poenitz [André Pönitz] and Peter Tittmann (poenitz(AT)htwm.de), Mar 03 2003
a(8) from Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 21 2006
a(9) and a(10) from Jesper L. Jacobsen (jesper.jacobsen(AT)u-psud.fr), Dec 12 2007

A209077 Number of Hamiltonian circuits (or self-avoiding rook's tours) on a 2n X 2n grid reduced for symmetry, i.e., where rotations and reflections are not counted as distinct.

Original entry on oeis.org

1, 2, 149, 580717, 58407763266, 134528361351329451, 7015812452562871283559623, 8235314565328229583744138065519908, 216740797236120772990979350241355889872437894, 127557553423846099192878370713500303677609606263171680998

Offset: 1

N. J. A. Sloane, Mar 04 2012

nonn

Christopher Hunt Gribble confirms a(3), and reports that there are 121 figures with group of order 1, 24 with group of order 2, and 4 with group of order 4. Then 121*(8/1) + 24*(8/2) + 4*(8/4) = 1072 = A003763(3), 121 + 24 + 4 = 149 = a(3). - N. J. A. Sloane, Feb 22 2013

Jon Wild, Posting to Sequence Fans Mailing List, Dec 10 2011.

Mathoverflow, Counting Hamiltonian cycles in n x n square grid, question asked by Joseph O'Rourke, Jul 25 2018.
Jon Wild, Illustration of a(3)
Ed Wynn, Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs, arXiv:1402.0545 [math.CO], 3 Feb 2014.
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A120443, A140519, A140521.

a(5)-a(10) from Ed Wynn, Feb 05 2014

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

Original entry on oeis.org

1, 5, 235, 96371, 447544629, 22132498074021, 10621309947362277575, 50819542770311581606906543, 2460791237088492025876789478191411, 1207644919895971862319430895789323709778193, 5996262208084349429209429097224046573095272337986011

Offset: 1

Don Knuth, Jul 26 2008

This graph is the "strong product" of P_n with P_n, where P_n is a path of length n. Sequence A007764 is what we get when we restrict ourselves to rook moves of unit length.

Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

			For example, when n=8 this is the number of ways to move a king from a1 to h8 without occupying any cell twice.

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

Jens Weise, Evolutionary Many-Objective Optimisation for Pathfinding Problems, Ph. D. Dissertation, Otto von Guercke Univ., Magdeburg (Germany, 2022), see p. 53.

Main diagonal of A329118.
Cf. A140519, A158651, A234622, A007764, A038496.
Cf. A220638 (Hosoya index).

a(9)-a(11) from Andrew Howroyd, Apr 07 2016

A288033 Number of (undirected) paths in the n X n king graph.

Original entry on oeis.org

0, 30, 5148, 6014812, 57533191444, 4956907379126694, 3954100866385811897908, 29986588563791584765930866780, 2187482261973324160097873804506155572, 1550696105068168200375810546149511240714556526

Offset: 1

Eric W. Weisstein, Jun 04 2017

Paths of length zero are not counted here. - Andrew Howroyd, Jun 10 2017

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

Cf. A236690, A288032, A288148, A234622, A158651, A140519.

a(5)-a(10) from Andrew Howroyd, Jun 10 2017

A339190 Square array T(n,k), n >= 2, k >= 2, read by antidiagonals, where T(n,k) is the number of (undirected) Hamiltonian cycles on the n X k king graph.

Original entry on oeis.org

3, 4, 4, 8, 16, 8, 16, 120, 120, 16, 32, 744, 2830, 744, 32, 64, 4922, 50354, 50354, 4922, 64, 128, 31904, 1003218, 2462064, 1003218, 31904, 128, 256, 208118, 19380610, 139472532, 139472532, 19380610, 208118, 256, 512, 1354872, 378005474, 7621612496, 22853860116, 7621612496, 378005474, 1354872, 512

Offset: 2

Seiichi Manyama, Nov 27 2020

			Square array T(n,k) begins:
   3,     4,        8,         16,            32,               64, ...
   4,    16,      120,        744,          4922,            31904, ...
   8,   120,     2830,      50354,       1003218,         19380610, ...
  16,   744,    50354,    2462064,     139472532,       7621612496, ...
  32,  4922,  1003218,  139472532,   22853860116,    3601249330324, ...
  64, 31904, 19380610, 7621612496, 3601249330324, 1622043117414624, ...

Seiichi Manyama, Antidiagonals n = 2..12, flattened
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, King Graph
Index entries for sequences related to graphs, Hamiltonian

Rows and columns 3..5 give A339200, A339201, A339202.
Main diagonal gives A140519.
Cf. A321172, A339098, A339849.

# Using graphillion
from graphillion import GraphSet
def make_nXk_king_graph(n, k):
    grids = []
    for i in range(1, k + 1):
        for j in range(1, n):
            grids.append((i + (j - 1) * k, i + j * k))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
            if i > 1:
                grids.append((i + (j - 1) * k, i + j * k - 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339190(n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
print([A339190(j + 2, i - j + 2) for i in range(10 - 1) for j in range(i + 1)])

T(n,k) = T(k,n).

A234622 Numbers of undirected cycles in the n X n king graph.

Original entry on oeis.org

7, 348, 136597, 545217435, 21964731190911, 9389890985897322572, 41930442683035614068268389, 1912714607714074785106312737308553, 888957501697133413663023517792044869026260, 4209348789084188565760570660849691414465827388642586

Offset: 2

Eric W. Weisstein, Dec 28 2013

nonn

Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, King Graph

Cf. A140519, A158651, A234623, A140517.

a(7)-a(11) from Andrew Howroyd, Apr 06 2016

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.

A339854 Number of Hamiltonian circuits within parallelograms of size n X n on the triangular lattice.

Original entry on oeis.org

1, 4, 80, 7104, 3292184, 6523266332, 56203566442908, 2176852129116199068, 373334515946952014204102, 281931891850296665963970600460, 939652851372937937187518231503848142, 13807942929878598929190143960742601141566220, 893498265685263112931409501489577970162598024007690

Offset: 2

Seiichi Manyama, Dec 19 2020

nonn

			a(2) = 1:
    *---*
   /   /
  *---*
a(3) = 4:
      *   *---*      *---*---*
     / \ /   /        \     /
    *   *   *      *---*   *
   /       /      /       /
  *---*---*      *---*---*
      *---*---*      *---*---*
     /       /      /       /
    *   *   *      *   *---*
   /   / \ /      /     \
  *---*   *      *---*---*

Ed Wynn, Table of n, a(n) for n = 2..16

Main diagonal of A339849.

Cf. A140519.

More terms from Ed Wynn, Jun 28 2023

A361171 Number of chordless cycles in the n X n king graph.

Original entry on oeis.org

0, 0, 1, 13, 197, 4729, 156806, 7035482, 505265569, 82612843683, 33651820752580, 23922790371389972, 25614853328191562332, 43322613720440154974138, 128405885225433787867253690, 738840753928503040569961869076, 8481241718402438554921627740308746, 179685856472407342498054958799766397100

Offset: 1

Eric W. Weisstein, Mar 03 2023

nonn

Using the convention that chordless cycles have length >= 4.

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

Cf. A140519, A234622, A297664, A357501.

a(7)-a(18) from Andrew Howroyd, Mar 03 2023

A383154 The number of 2n-by-2n fers-wazir tours.

Original entry on oeis.org

2, 2, 22, 1620, 882130, 3465050546

Offset: 1

Don Knuth, Apr 18 2025

The simplest fairy chess pieces, going back to 9th-century Persia, are the fers -- a (1,1) leaper -- and the wazir -- a (1,0) leaper. (A king combines the moves of a fers and a wazir.) A fers-wazir tour visits every cell of a board exactly once, making fers and wazir moves alternately, and returns to the starting cell.

Such tours exist only when the number of rows is even and the number of columns is even.

			For n=2 the a(2) = 2 solutions are transposes of each other:
.
  0-f 4-3   0 e-d b
   X   X    |X   X|
  e 1-2 5   f 1 a c
  |     |     | |
  d a-9 6   4 2 9 7
   X   X    |X   X|
  b-c 7-8   3 5-6 8

D. E. Knuth, Hamiltonian paths and cycles, Section 7.2.2.4 of The Art of Computer Programming (to appear).

George Jelliss, Introducing Knight's Tours, has a 9th century example of a fers-knight tour due to As-Suli.

Diagonal of A383153.

Cf. A140519.

cp's OEIS Frontend

A003763 Number of (undirected) Hamiltonian cycles on a 2n X 2n square grid of points.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A209077 Number of Hamiltonian circuits (or self-avoiding rook's tours) on a 2n X 2n grid reduced for symmetry, i.e., where rotations and reflections are not counted as distinct.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A288033 Number of (undirected) paths in the n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A339190 Square array T(n,k), n >= 2, k >= 2, read by antidiagonals, where T(n,k) is the number of (undirected) Hamiltonian cycles on the n X k king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A234622 Numbers of undirected cycles in the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

A339854 Number of Hamiltonian circuits within parallelograms of size n X n on the triangular lattice.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A361171 Number of chordless cycles in the n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions