Make the prize for Sokoban a guaranteed amulet of reflection, and guarantee a bag of holding to generate elsewhere. It could be in any of:

• On Mines’ End, not replacing the luckstone but along it.
• Somewhere below Minetown, not necessarily at Mines’ End.
• In a vault in the Dungeons of Doom, not in the first few levels.
• Somewhere at or above the depth of Mines’ End, which could be in any branch.

However, guaranteeing the existence of a reward item like the amulet of reflection risks funneling players into a single standard strategy.