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.

Solution 1:

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.

Solution 2:

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$.