|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|