Solstice: The Quest for the Staff of Demnos (1990) follows a wizard called Shadax on his quest to retrieve the eponymous staff in order to save a princess from being unjustly incarcerated. The game is essentially a huge isometric labyrinth filled with devious traps and oddball creatures to ensure especially frustrating peril in the absence of any kind of map to help the player. (Well, at least it was like that before the Internet era, but make no mistake: the game isn't by any means easy nowadays, either.) One of the most memorable aspects of the game is its jazzy musical theme filled with deep bass notes uncommon for the NES.
This movie is 00:00.43 seconds faster than its predecessor, thanks to better optimization and using hidden stone in one room.
We also have a 100% Solstice run.