This is a solution somewhere between brutal force and dynamical programming, definitely not fully optimized but it worked.

You can define an iteration function with takes two inputs:

1. the current number up to i digits
2. the current step/depth

Then in the function, you check if the int(number) can divide the step completely.

If yes, you go through all the digits "123456789", pick one which is not within the current number, concatenate the current number and the selected digit, and send this new number and step + 1 into the next step.

Since the hint says that the outcome is unique. You can print it in step=9.