OK. If we allow denormalized values like "057", then our first guess is "210", and it takes not more than 9 guesses, and as few as 1 if the secret number was "210". It takes an average of 7.311 guesses. (An interesting result: 1/8th of the numbers take a full 9.)
If we don't allow denormalized values, then our first guess is "321", and it still takes not more than 9 guesses. It takes an average of 7.09555... guesses.
The strategy starts by observing that every guess splits the space of possibilities five ways.
- that we guessed the secret number.
- that we guessed higher than the secret number and didn't match digits, and therefore lost. We must choose our guesses to make this space empty!
- that we guessed lower than the secret number, and didn't match digits.
- that we guessed higher than the secret number, and matched digits.
- that we guessed lower than the secret number, and matched digits.
The secret is to make the smallest the last three as large as possible. If we could produce an equal split, we could achieve a win in seven guesses. We can't get an equal split.
The first guess of 210 or 321 is the largest number that includes all possible first digits of any smaller number, thus guaranteeing no loss, and getting good splits (1/0/343/210/446 or (1/0/294/221/384). This is the shortest possible guess.
The worst case? Any that take 9 guesses. 432 and 997 is a good examples as they take 9 with or without denormalized numbers.
I'm not going to try to show a full decision tree, since they are huge.
An ideal strategy might to a bit better than what I've cited, as my testing was done based on finding all possible guesses that got the best split, discarding those that aren't possible secret numbers if any are, and then taking the lowest.
I haven't tried the possibility that we are not told that we have guessed the secret number, and must prove it based on other evidence. Even that probably won't take more than 10 guesses.