Letters Boxed, Like Surgeons General

Consider the following diagram, which consists of eight points (labeled $A$ through $H$), two on each side of the square. A valid “letter boxed” sequence starts at any of the eight points, and proceeds through all of the other points exactly once. However, adjacent points in the sequence can never be on the same side of the square. The first and last points in the sequence can be on the same side, but do not have to be.

As an illustration, $AFBCHEDG$ is a valid sequence of points. However, $AFBCHGED$ is not a valid sequence, since $H$ and $G$ are adjacent in the sequence and on the same side of the square. How many distinct valid “letter boxed” sequences are there that include all eight points on the square?

Well in total, there are $8! = 40,320$ different words that can be made up of the letters $A$ through $H$ with no repeated letters. One possible way is to get this answer is to just enumerate all $40,320$ possible words and throw away any words with forbidden doublets, like $AB$, $EF$ or $HG$. This is not too terribly time consuming in a short Python script, which yields that there are a total of $13,824$ different letters boxed that include all eight points on the square.

Instead of two points on each side of the square (and eight points in total), now there are three points on each side (and twelve points in total), labeled A through L in the diagram below. How many distinct valid “letter boxed” sequences are there that include all $12$ points on the square?

While $8!$ might be well within a modern programming languages wheelhouse to try to iterate through, $12!$ is more than $500$ million possible words that are composed of the letters $A$ through $L$ with no repeated letters. So unless we want to run a script all weekend, let's try a different approach. We can encode the 12 points on the square and the adjacency of the letter boxed game into a graph $\mathcal{G},$ where for instance there is an edge from $A$ to each letter $D, E, F, \dots, L,$ but no edge between $A$ and $B$, $A$ and $C$ or $B$ and $C,$ since they all share the same side of the square. A letter boxed that contains all twelve letters would then be a Hamiltonian path on $\mathcal{G},$ so let's liberally borrow the Python3 code provided by user Gaslight Deceive Subvert from this StackOverflow post related to enumerating all Hamiltonian paths on a graph and get to countings. Since I don't particularly care about the paths themselves and just the number of them, instead of printing the entire list of all Hamiltonian paths, I modified it to just print the number of distinct Hamiltonian paths.

To confirm that everything seemed above board, I started out with the graph from the Classic problem given by \begin{align*}\textsf{G} &\textsf{= \{'A':'CDEFGH', 'B':'CDEFGH', 'C':'ABEFGH', 'D':'ABEFGH',}\\ &\quad\quad \textsf{'E':'ABCDGH', 'F':'ABCDGH','G':'ABCDEF', 'H' : 'ABCDEF'\}}.\end{align*} THankfully, the code retrieved the answer of $13,824$ letters boxed, so I then felt confident enough to encode the Extra Credit graph as \begin{align*}\tilde{G} &\textsf{= \{'A':'DEFGHIJKL', 'B':'DEFGHIJKL', 'C':'DEFGHIJKL',}\\ &\quad\quad\quad \textsf{'D':'ABCGHIJKL', 'E':'ABCGHIJKL', 'F':'ABCGHIJKL',}\\ &\quad\quad\quad\quad \textsf{'G':'ABCDEFJKL', 'H' : 'ABCDEFJKL', 'I':'ABCDEFJKL',}\\ &\quad\quad\quad\quad\quad \textsf{ 'J' : 'ABCDEFGHI', 'K' : 'ABCDEFGHI', 'L' : 'ABCDEFGHI'\}}.\end{align*}.$$ Here, after running the code for roughly 15 minutes, we get a grand total of $53,529,984$ letters boxed with all $12$ points on the square.