Maybe something could be introduced such as Icefall cave in kanto (pokemon) or the eight gym of hoenn region.
The first picture (icechallenge1.png) is of the 8th gym, where each tile could only be stepped on once, and all tiles had to be stepped on in order to unlock the stairwell to get to the next puzzle.
The second picture is of icefall cave, (icechallenge2.png) where once you stepped on ice, you kept sliding in that direction until you hit a barrier. You had to navigate your way through the room, and it could be pretty tricky at times.
Just a few suggestions for incorporating puzzles in classic!