login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A328931 Number of Hamiltonian paths in an n X n square, starting from an edge, finishing anywhere, all symmetries excluded. 1
1, 1, 4, 51, 660, 30745, 1621471, 312637285, 72599875346, 60968508324409, 64128000370443037, 240651566540823214362, 1162174738476331286327484, 19776621796151182708398884540, 441809773825445785471324877668710 (list; graph; refs; listen; history; text; internal format)
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: A048995 A215639 A320645 * A235325 A230401 A293075

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 27 18:28 EST 2020. Contains 332307 sequences. (Running on oeis4.)