Number conversion via Prime route

Convert the number 12345 to the number 54321 in seven or less steps with the following rules

A: You can only change any one digit at a time using digits 1 to 9

B: After the change the new number formed must be a Prime number

C: The Prime number cannot have a repeat digit in it. All five digits must be different.

D: You can check the Prime Number list from the computer but no programming please.

Bonus Question

Will you shorten the conversion if Rule C is waived?

• @bobble This is not a Word Ladder per se. No words involved.
– DrD
Commented Feb 3, 2021 at 15:11
• You can see the edit reason I left. It's in the word-ladder genre (it is a variant of the genre, as you state) and therefore I felt the tag was useful. Feel free to remove it if you think it goes against your intentions Commented Feb 3, 2021 at 15:12
• OK I Understand
– DrD
Commented Feb 3, 2021 at 15:13
• I don't think it is possible in 6 steps. ROT13(Vg gnxrf guerr fgrcf gb rkpunatr bar naq svir jvgubhg ercrgvgvba, naq fvzvyneyl gjb naq sbhe, fb gubfr ner gur bayl fgrcf. Gur svefg fgrc zhfg or svir gb frira. Gur arkg fgrc zhfg rvgure or bar gb svir, be gjb gb fbzrguvat, be sbhe gb fbzrguvat. V guvax nyy bcgvbaf tvir bayl ercrgvgvbaf be pbzcbfvgrf.) I'm probably overlooking something. Commented Feb 3, 2021 at 15:52
• OK My bad. I did not count going to the last step as a step. I edited it.
– DrD
Commented Feb 3, 2021 at 16:17

Here is a seven step solution which is the minimum

12345 -> 12347 -> 92347 -> 98347 -> 98327 -> 94327 -> 94321 -> 54321

Proof that this is minimal

Jaap Scherphuis makes the point in the comments that it would take at least three steps to swap the 2 and 4 and at least three steps to swap the 1 and 5, under the rules, so let's see if it can be done.
You have to change the last number first because numbers ending in 5 won't be prime and the only choice here is 7, so we get 12347. To achieve six steps, we then must be able to swap the 2 or 4 with a digit not already used or the 1 to a 5 but all cases result in a composite number, so six steps cannot be achieved.

Further to this,

With the idea that we must change 1, 2 or 4 next, the only possibility is that the 1 must change to a 6 or a 9. To achieve a seven step solution, the next step must be changing the 2 or 4 to something already unused or changing the 7 to a 1. The 62347 proves fruitless in this regard but the 92347 path is very fruitful and it's not too hard to generate a solution on this path (I found a few).

What if Rule C is waived

12345 -> 12347 -> 14347 -> 14327 -> 14321 -> 54321.
This is five steps and this is optimal because changing the 5 to 7 is a necessary first step and from there, since four digits are still different, we cannot do better than four steps.

Note: Jaap Scherphuis makes the very valid point in the comments that we can also change the 5 to a 3 in the first step (I missed this) but that it would also take four more steps to convert to our final answer (for the same reasons as above).
Here is a possibility in this case
12345 -> 12343 -> 12323 -> 14323 -> 54323 -> 54321

• A tiny nitpick: When rule C is waived, there is also an equally short solution that changes 5 to 3 in the first step. Commented Feb 3, 2021 at 16:25
• @JaapScherphuis Ah, yes, thank you, I completely forgot about that. Commented Feb 3, 2021 at 16:27