Assuming an implementation containing multiple puzzle branches (to offer players an alternative to Sokoban), have all the branches start from an “antechamber” level off the main dungeon. This is a small unpopulated level, and contains terrain clues around each puzzle branch staircase in it, such as boulders and strangely shaped walls for Sokoban, ice if there is an ice sliding puzzle, etc.