Earlier quoted context omitted.
Not an expert on how they do it, but I've played a few. The logic in these things is excellent, they won't ever give you an unsolvable game (and the Zelda ones have been playtested to death at this point). I think they just specify the prerequisites for each item and then just don't assign them if they are impossible to get, not sure how exactly the algorithm works but I can think some easy ways on how solve this pro…
Essentially there is a couple of state machines for area access and the conditions/items that enable access. So within each subarea the candidate items can be distributed. Now, if they could randomize dungeon maps in the original zelda...
They do, and have for some time.