A328931 Number of Hamiltonian paths in an n X n square, starting from an edge, finishing anywhere, all symmetries excluded.

1, 1, 4, 51, 660, 30745, 1621471, 312637285, 72599875346, 60968508324409, 64128000370443037, 240651566540823214362, 1162174738476331286327484, 19776621796151182708398884540, 441809773825445785471324877668710

Offset

1,3

Comments

Given an n X n grid, start from any outside edge, enter the grid, and visit every square. 1 X 1 is a trivial example. 2 X 2 can only be traversed clockwise or counterclockwise (therefore considered the same solution). For 3 X 3 with the cells labeled ABC/DEF/GHI, the four solutions are ADEBCFIHG, ADGHIFEBC, ADGHIFCE and ADGHEBCFI. All others are rotations or reflections.

Discovered programmatically by exhaustive recursive search.

Links

Table of n, a(n) for n=1..15.

David Lawrence, All paths up to 4 X 4

Example

All distinct paths through a 1 X 1 labyrinth visiting all cells.
  +  +
  |**|
  +--+
.
All distinct paths through a 2 X 2 labyrinth visiting all cells.
  +  +--+
  |  |**|
  +  +  +
  |     |
  +--+--+
.
All distinct paths through a 3 X 3 labyrinth visiting all cells.
  +  +--+--+
  |  |     |
  +  +  +  +
  |     |  |
  +--+--+  +
  |**      |
  +--+--+--+
.
  +  +--+--+
  |  |   **|
  +  +  +--+
  |  |     |
  +  +--+  +
  |        |
  +--+--+--+
.
  +  +--+--+
  |  |     |
  +  +  +  +
  |  |**|  |
  +  +--+  +
  |        |
  +--+--+--+
.
  +  +--+--+
  |  |     |
  +  +  +  +
  |  |  |  |
  +  +  +  +
  |     |**|
  +--+--+--+

Crossrefs

Cf. A120443, A121789, A145157, A265914.

Sequence in context: A215639 A320645 A347921 * A343572 A336608 A376105

Adjacent sequences: A328928 A328929 A328930 * A328932 A328933 A328934

Keyword

nonn,more

Author

David Lawrence, Oct 31 2019

Extensions

a(8)-a(15) from Andrew Howroyd, Oct 31 2019

Status

approved