I would be very tempted to see if the generation of possibilites can be done recursively -- and generated in a way, that checks for duplicates as part of the process. It will likely not be faster, but at least it won't have the ridiculous number of nested "for" loops, and nested "if" conditions.... Okay, and the other reason would be just to see if it can be done that way...
This algorithm goes through every single possibility for every single substitution, and checks for consistency at the lowest level.
The main way to optimise this is to not descend into a nested loop until you have to.
You can quite easily eliminate huge branches of this search tree by doing checks earlier.
Ask your self at each level of looping "is it worth continuing" ?
When I wrote my general-purpose alphametic solver, I started at the top right and worked from top to bottom and from left to right. I also used backtracking -- which means that when I got to a place where there wasn't any valid value for the cell I was trying to fill in, I went back to the previous cell and tried the next value.
So the logic would go something like this:
Try D = 0. Is that okay? Yes.
Try E = 0. Is that okay? No, try E = 1. Is that okay? Yes.
Try Y = 0. Is that okay? No, try Y = 1. Is that okay? (We're always going to have E = Y or else D + E <> Y plus carry so let's skip ahead...) Y = 9 isn't okay, so let's backtrack to E.
Try E = 2. Is that okay? Yes.
(All values of E are going to result in no valid values of Y as long as D = 0, so let's skip ahead...) E = 9 isn't okay, so let's backtrack to D.
Try D = 1. Is that okay? Yes.
And so it goes on, until either you get to the point where you have filled in valid values for all of the cells, or you've backtracked right off the very first cell.
This of course is completely different than the original posted code, but it would run a lot faster.