All you really need to do is to solve the right puzzles.
Have you found Cassima?
Did you get in the vizier's room?