It seems that you can choose the initial state of the game, this implies that the number 1000 is no restriction (if it takes a million steps you take the 99900

It seems that you can choose the initial state of the game, this implies that the number 1000 is no restriction (if it takes a million steps you take the 999000 as the initial state. You can program some greedy algorithm and since number of steps is not a problem the solution seems attainable by this method (just 3 minutes thought).