In a sandbox, I declare I (as my character) go over here. The GM consults their notes, or applies their heuristic (random table or extrapolation or whatever) and tells me *Here's what you see."
In a module, I declare I (as my character) go over here. The GM consults the module, sees it has nothing useful to say about what's over there, and so uses their control over fiction and backstory to "bounce me back", and tells me "Here's what you see" where some of what I see is the bouncing.
What is the difference in agency in these two cases?
To me, there is quite a bit of difference - in the sandbox version the customer has achieved what they set out to do - they wanted to go over there, and they got over there. In the module, they wanted to go over there, and they didn't get there, they were bounced back.
For a module - next step is they are going into a jungle, no matter which direction they pick, they end up in the jungle, which gets worse when most modules contain maps the players can access, so is clear they are being rerouted, and so lack agency.
In a sandbox setting, I see two main approaches:
The setting is preset, so there is a map with everything in it, and potentially a GM version and a player version if there are things the GM wants predetermined (e.g. dungeons, dragon lairs) that a character wouldn't know, and so in a potential concern about trust or just impacts of knowledge, you don't show these to a player.
In this set up - the players want to visit that forest, or that desert, and they can visit that forest or desert, they have full agency to make that choice.
The setting is not preset, then the GM is either making it up, or working with the players to determine what is in the new area, if the former, can be danger if the GM is wanting it to be jungle regardless, that it looks like the module version, and players lose agency.
To borrow / stretch your puzzle analogy, I'm thinking it as two options for the old great Fighting Fantasy novels:
Module version:
You come to a clearing, there are paths to the left, straight ahead, or right, and there is an old abandoned house. What will you do?
If go left, turn to page
98
If go right, turn to page
98
If go straight ahead, turn to page
98
If enter the house, turn to page
98
- there is no meaningful choice, to my mind no real agency, you are going where the module dictates. (I think module still has options for agency, e.g. in my dragonlance campaign, I certainly didn't force two characters in two different situations to go on the gnome flinger with no safety apparatus, they chose to do so and I facilitated that, but overall they still ended up in the village, and will end up in Kalaman).
Sandbox version:
You come to a clearing, there are paths to the left, straight ahead, or right, and there is an old abandoned house. What will you do?
If go left, turn to page
98
If go right, turn to page
203
If go straight ahead, turn to page
399
If enter the house, turn to page
42
And assuming they don't all circle back to same destination (which did happen occasionally) - then customer had agency in direction to go, they may or may not know some key differences between the options, but had the option and agency to choose, whether the gamebook or DM ultimately describes what they see.