By the way it's not that sure that you can start with every 4 digit number. I think you can - but you need to prove it.

You can.

First, it is sufficient to prove that you can do it with every possible pattern of same/differing numbers. Permutations take care of the rest. (Your thinking on that was fine, by the way.) There are only twelve such patterns: AAAA AAAB AABA ABAA BAAA AABC ABAC ABCA BAAC BACA BCAA ABCD. All you have to do is choose A, B, C, and D as four different digits and find a solution for each one. I chose A=0, B=1, C=2, and D=3 and then, using the same code in my original solution, found that there was indeed a solution for each of the 12 patterns.

So, for a lower bound, we have at least 12 * 10! (or the number of starting patterns multiplied by the permutations.)

Some other interesting facts (proofs left as an exercise):

• The reverse of a valid solution is a valid solution.
• No valid solutions are palindromic.

-sauoq
"My two cents aren't worth a dime.";