Buy a North Town Key.
Go to the Orc King's Castle. Get a key from a kill, then kill the Orc King. Take his armor (needed later).
Get a key for the Pumphouse from a Gnoll.
Find the entrance to the Gnoll King's area. Go up and find a key for the door (or use a Door Scroll).
Go up and kill the Gnoll King. Take his armor and trade it for a key north of South Town.
Go to the Portal Room in the Gnoll King's dungeon.
Trade the Orc King's armor to the King's spy for a key to the Portal Room.
Jump down the hole near South Town.
Go east of the King in North Town. Get a scroll so the Princess will follow you.
Princess Anne's cell is on the 2nd level of the Gnoll King's dungeon.
Use a Door Scroll to open the wall in the southwest corner.
Go north then east through the passage. Kill the Archer Orcs behind counters.
Open the Princess' cell.
Go east through the bottom level of the Gnoll King's dungeon to the Portal.
Open the Portal to the King's Throne Room.