Hamiltonian Cycles on a Square Grid, part 2

The algorithm in my first post on this topic used some of the ideas in  R. Stoyan and V. Strehl: Enumeration of Hamiltonian Circuits in Rectangular Grids. Journal of Combinatorial Mathematics and Combin.Computing 21 (1996), 197-127, but did not employ the construction technique suggested in their paper.

Here is a modified algorithm, with vastly improved performance, using most of the construction method suggested by Stoyan and Strehl.

The algorithm constructs all 1,072 Hamiltonian cycles on a 6 by 6 grid in about 100ms, and all 4,638,576 Hamiltonian cycles on an 8 by 8 grid in about 20 minutes. 

Here, the algorithm runs out of steam, as a 10 by 10 grid has 467,260,456,608 cycles (Sloane A003763)



To construct N by N Hamiltonian cycles, the algorithm builds up  "induced subgraphs" (see diagram at left) of an (N-1) by (N-1) square graph one cell at a time, starting with the top row and working across each row in turn.










The top row is constructed by observing that the corner cells have to be inside the Hamiltonian Cycle, and that no two outside cells can be adjacent.

From then on, cells are added by testing whether a cell can be inside or outside (or both or neither) according to the rule that no 2 by 2 block can be any of these patterns:

A 2 by 2 block $a,b,c,d$ will match one of the four patterns iff $a=d$ and $b=c$




Additional tests check that:

• no 2 adjacent cells on the perimeter can be outside
• the total number of inside and outside cells does not exceed   $\frac{N^2-2}{2}$ and $\frac{(N-2)^2}{2}$ respectively
• After the completion of a row, all inside cells are connected to the row just completed.

Python implementation

Here is the Python code for the algorithm. 

Hamiltonians(N) yields all the Hamiltonian cycles for an N by N grid.

Constructing Hamiltonian Cycles on a Square Grid

Background

A solution to New Scientist Enigma puzzle 1431 led me to consider how to generate all Hamiltonian Cycles for an N by N square grid.

The obvious way to generate Hamiltonian cycles for any graph is to find all Hamiltonian paths that end at a node adjacent to the start node. However, for a 6 by 6 grid, there are 458,696 Hamiltonian paths but only 1,072 Hamiltonian cycles. (Sloane A096969 and A003763)

The analysis in  R. Stoyan and V. Strehl: Enumeration of Hamiltonian Circuits in Rectangular Grids. Journal of Combinatorial Mathematics and Combin.Computing 21 (1996), 197-127, identifies an alternative way of identifying Hamiltonian cycles. For example, this figure shows a Hamiltonian Cycle for a 6 by 6 grid.

Stoyan and Strehl point out that each cell is either inside or outside the Hamiltonian Cycle, as shown here (yellow cells inside, white outside) Thus, Hamiltonian Cycles for an N by N graph can be associated with an "induced subgraph" of an (N-1) by (N-1) square graph.

Stoyan and Strehl show that any induced subgraph corresponds to a Hamiltonian Cycle if: A) It is a tree B) No 2 by 2 sub-grid of the extended grid matches one of the four patterns:

  Additionally, there are always $\frac{N^2-2}{2}$ inside cells and $\frac{(N-2)^2}{2}$ outside cells, and the four corner cells have to be inside.

These constrants can be used to find subgraphs that correspond to Hamiltonian cycles more efficiently than the search of Hamiltonian paths. For N=6, there are $\binom{(N-1)^2-4}{\frac{(N-2)^2}{2}} = \binom{21}{8} = 203,490$ combinations of outside cells that need to be tested.

However, the algorithm does not scale well. For N=8, there are $\binom{45}{18} =  1,715,884,494,940$ combinations of outside cells.

The performance could be improved by using the observation that there cannot be 2 contiguous outside cells on the boundary. However the algorithm as it stands runs in less than 1 second for N=6, and the suggested improvement would not significantly reduce the number of cases that would need to be tested for N=8.

Python Implementation

A Python implementation of an algorithm based on these constraints is presented below. The search for the four patterns of 2 by 2 sub-cells does not cover the extended grid, as it turns out that this is not necessary, at least for the cases N=4 and N=6 (I haven't worked out whether this extends to higher values of N)

Dent, Aye Gill Pike

I camped at High Laning campsite in Dent on a very pleasant sunny evening, and next day walked a circuit from Dent along the ridge of Aye Gill Pike.

View from High Laning campsite

 

   

Although the ridge isn't marked on OS maps as a footpath, it is on access land. There are footpath signs throughout its length and stiles over all walls and fences.

Click for an interactive map

Gate on Dales Way

Mire House

Stopping at the village shop in Dent to buy some pasties for lunch, I walked down to the river Dee, following the Dales Way heading West through numerous fields and gates to Ellers, where I took the footbridge across the river and followed the path up through Mire House, Craggs Farm and Hewthwaite, picking up the Dales Way again.




Before reaching Millthrop, there are good views of Sedbergh, in front of the Howgills.

Sedbergh and the Howgills

Turning East just before Millthrop, I followed a footpath that became increasingly indistinct, taking a bearing East across Frostrow to pick up a bridleway on the far side. This section was quite boggy and hard going. A shorter alternative route (shown in green on the map), would avoid this "off path" section.

Aye Gill Pike

From the end of the bridleway, it is a simple matter of following the wall up to the summit of Aye Gill Pike.

Cowgill Church

From the summit, I followed the wall East to Snaizwold Fell, then followed a ruined wall down to a track which runs past Cowgill Church, and to the Dales Way at Ewegales.






I then  followed the Dales Way all the way back to Dent.

That will teach them!

River Dee

 

Enjoying a well-earned retirement from  show business