Math puzzle: 10 digit strings generations There was a question in a math competition that I attended last year. At the end of competition, I realized that my answer was wrong for the question below and I have never been able to figure out how to solve it.
Here is the question:
You are asked to generate 10 digit strings using digits from 0 to 9 once each. Any four-digit substring used in a string cannot be used again.
What is the highest number of unique strings you can generate using these rules? (and I need the list of them)
Example:
If you use a string 0243697518 in your list, you can not generate strings contain 0243, 2436, 4369, 3697, 6975, 9751 and 7518
To solve the problem, I have written a c++ program, simply it scans all permutation of "0123456789" and add them into a solution list if 4 digit sub-strings of the code has not been used before. But the problem of my algorithm is that the size of solution list varies by depending on your starting point that you add into the list first. If I start adding into list from "0123456789", list ends up with 504 entries which is not the maximum asked. I really wonder how to solve this question, any help highly appreciated. I'm open to hear your mathematical solution or any algorithm suggestions to generate the list asked.
Histogram of random approach as suggested by Peter (min: 575, max: 606): 

Above algorithm tries to generate list asked by scanning all possible 10 digit strings in a random sequence. Histogram generated over 100K trials. Because all possible 10 digits strings needed to be scanned for each iterations are 10! = 3.6 million, each iterations takes 10 seconds on my pc to complete. I could try optimizing my algorithm more if I believed that there was really no deterministic solution for the question.
 A: The de Bruijn sequence gives you approximately 1428 possibilities (10000/7 plus or minus one or two due to rounding): shift a window of size 10 through it, each time shifting by 3 positions.
Edit (sorry, I also missed the part that you want permutations). This might bring you a bit closer to what you need: "Universal cycles of k-subsets and k-permutations" by B.W. Jackson, and also look for newer papers and books citing this paper (for example, in Google scholar). By building an Eulerian walk in a suitable graph you can generate a cycle containing each partial 4-permutation exactly once, something called a universal cycle (ucycle) of partial permutations.
A: Instead of iterating between 10-digit numbers, make a list of all the possible 4-digit numbers (which are $10*9*8*7=5040$ and merge 7 4-digit numbers at a time to obtain 10-digit numbers. It is a dynamic programming question and you will have to backtrack to get already used 4-digit numbers into 10-digit numbers that require them the most. Using this approach, the maximum possible 10-digit strings should be $(10*9*8*7)/7=720$.
A: I don't have a solution but here are some thoughts on the problem. We can look at the $(m,n)$ of finding the maximum possible number of strings of $m$ symbols with no strings of length $n$ used more than once in the whole set of strings. We can construct a graph $G$ whose vertices $V$ are the $n$-digit strings. We'll put an edge between two vertices $v$ and $v'$ if the strings overlap in the following way
$$v = s_1 s_2 \ldots s_n, \quad v' = s_2 \ldots s_n s_{n+1}$$
where $s_1 \neq s_{n+1}$. We connect every vertex $v$ to $m-n$ other vertices. Also every vertex has $m-n$ edges leading to it. Overall
$$|V| = n!\binom{m}{n} = \frac{m!}{(m-n)!},\quad |E| = (m-n)|V| = \frac{m!}{(m-n-1)!}$$
We can represent each $m$-digit string by a directed path in $G$ of length $m-n$, containing $m-n+1$ vertices. We need to find the maximum number of such vertex-disjoint paths in $G$. One would have a theoretical maximum of
$$\frac{m!}{(m-n+1)!}$$
such paths if all the vertices are used. In your case of $m = 10$, $n = 4$ you have 720 possible paths and from the problem you know you can find this many paths. This corresponds to finding a vertex cover of $G$ consisting of paths of vertex length 7. If anyone knows of an algorithm to find such a cover, then they can apply it to this problem. This is not always the case though. For $m = 3$ and $n = 2$ you'd expect $6/2 = 3$ such paths but the graph $G$ consists of 2 disjoint directed 3-cycles.
Clearly, the graph $G$ has to remain invariant by any permutation of the digits themselves, so one could easily set one of the paths in the cover as $0123\to 1234 \to \cdots \to 6789$. 
Another thing to note is that if we can find a Hamiltonian cycle in the graph we can delete every $m-n+1$-th edge to obtain such a maximal cover if one exists. Unfortunately I don't have an algorithm for finding Hamiltonian cycles in a directed graph but someone else might.
