This question asks to find a solution without the use of graph theory or de Bruijn Sequences. Since I was unaware of these theories when I was working on the answer I think this qualifies. Although the algorithm I used is probably the same without me realizing it. Anyway, here’s my thought process:
Obviously for a 4 digit code with 10 numbers there will be 10^4 = 10,000 combinations. After you’ve entered the first combination – requiring 4 digits, each additional digit can theoretically introduce a new combination. Since you need to try 9,999 more combinations then the smallest sequence will be 9,999+4 = 10,003.
To have a consistent algorithm, whenever I have a choice I will choose the lowest possible option that hasn’t already been tried or that doesn’t break the sequence. This means I’ll start with 0000. Now, since with each step I am adding one more digit to the end of the sequence, that means that each step I am just looking at the last three digits of the sequence. My algorithm will then be to break down the 10,000 combinations into 1000 three digit blocks with 10 choices in each block. Whenever I encounter a three digit block, for my next digit I just choose the smallest option in the block that hasn’t been used yet.
000 0 .. 900 0 .. 990 0 .. 999 0
000 1 900 1 990 1 999 1
000 2 900 2 990 2 999 2
. . . .
. . . .
000 9 900 9 990 9 999 9
So, since I started with 0000 then the first block I encounter is 000.
I already used the 0, so that can be eliminated from the block. The next number will then be 0001. After I write that down I eliminate 0001 from the block. Now I look at the block 001
The smallest number in that block is 0010, after I write that down I can eliminate it from the block. And so on.
This algorithm works pretty well. There are only 3 places where it will give you trouble. The first two problem spots are pretty early in the sequence, the third one is a bit further down the line, but if you’re looking for it it’s not hard to find.
The first problem is when I’ve eliminated the entire 000 block. I have to make sure now that I do not encounter a 000 block again until the end. This happens at this point:
Normally I would put 0 after this, because the lowest option in the 900 block is 9000, but in this case that will leave me with no way to progress, so I save 9000 until the end and move on to 9001.
The second problem is when I’ve used up the entire 900 block, except for the 9000 choice which I am saving until the end. This happens at this time:
Again, normally when I encounter a 990 block I would choose 9900 as that’s the lowest available, but in this case it will force me into a 900 block which only has one option left that terminates the sequence. So I leave 9900 until the end and move on to 9901.
I think you’ve seen the pattern now. Once I’ve used up the entire 990 block, except for 9900, now I have to be vigilant not to enter that block again until the end. This happens at this location:
Instead of 9990 I will have to put 9991 here and save 9990 until the end. After navigating these 3 problem places there are no more issues in the sequence. At the end I just close with the numbers that I’ve saved: 9990, 9900, and 9000.
This is the exact same sequence that the other answer provided.
And that’s how you do it without knowing anything about anything. I don’t know if this too complicated or too simple or too labor intensive, but it gets the job done.