The article doesn't do a good job of explaining the constraint.
The sequence being generated is called a superpermutation [0].
From the Wikipedia article:
"""
...a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring.
"""
In other words, construct a big long string made up of the N symbols where every permutation of the N symbols appears in it. Since there's the possibility of overlaps, you can do better than the naive method of just pasting all N! permutations together.
Note that this sounds very similar to a De Brujn sequence [1] but is different since a De Bruijn sequence ask for every possible sequence of N symbols (of length M, say), not every possible permutation. So a De Bruijn sequence would have 000, 001, 002, ... 200, 201, ... , 222 in it whereas a superpermutation would exclude (or at least not count) some of those sequences as they're not permutations (012, 021, 102, 120, 201, 210).
Is a superpermuation just a more efficient annotation or is it more helpful in solving an optimization problem? They talk about the travelling salesman problem in the article but they don't exactly explain if knowing the superpermutation helps solve it faster.
One goal is to find an 'efficient' annotation of a superposition. That is, "what is the minimum superpermutation string length of of N symbols", which itself is a sort of optimization problem. We can presumably get bounds on the minimum and maximum it can be and maybe the 'optimal' shortest superpermutation has enough variation that the bounds aren't/can't be exact.
As to what "practical" applications superpermutations have, nothing comes to mind but considering how many applications de Bruijn sequences show up, I'd be surprised if they didn't start cropping up from time to time in the future.
As to the travelling salesman/Hamiltonian path/cycle problem, my impression is that they used a clever construction of a Hamiltonian cycle on a hyper-cube/Cayley graph/high-dimensional-high-degree graph to show lower/upper bounds on the number of superpermutations. In other words, the implication is the other way. They construct a Hamiltonian cycle on a specially crafted graph to show lower/upper bounds rather than use superpermutations to say anything about Hamiltonian cycles.
To get a flavor for how this works, I'll copy pasta the de Bruijn "construction" section of Wikipedia [0]:
"""
The de Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional de Bruijn graph over k symbols (or equivalently, an Eulerian cycle of an (n − 1)-dimensional de Bruijn graph).
"""
With a de Bruijn graph [1] being a specialized graph construction.
The sequence being generated is called a superpermutation [0].
From the Wikipedia article:
""" ...a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. """
In other words, construct a big long string made up of the N symbols where every permutation of the N symbols appears in it. Since there's the possibility of overlaps, you can do better than the naive method of just pasting all N! permutations together.
Note that this sounds very similar to a De Brujn sequence [1] but is different since a De Bruijn sequence ask for every possible sequence of N symbols (of length M, say), not every possible permutation. So a De Bruijn sequence would have 000, 001, 002, ... 200, 201, ... , 222 in it whereas a superpermutation would exclude (or at least not count) some of those sequences as they're not permutations (012, 021, 102, 120, 201, 210).
[0] https://en.wikipedia.org/wiki/Superpermutation
[1] https://en.wikipedia.org/wiki/De_Bruijn_sequence
EDIT: links (de bruijn)