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