This is not really a Walkthrough but a couple of hints on how to get through the game in "Impossible?" mode.
1. Saharia and Flying Monsters
The most important thing to find the sceptre is flexibility and speed. So we want to get our guy into flying mode as fast as possible. That means that we want an army solely comprised of flying monsters, those are: Dragons, Archmages, Vampires
and Demons. Sprites may fly but cannot carry your guy.
Thereby we have to get to Saharia (the 4th and last of the continents of the game).
As you may already know, on each continent there is a chest somewhere which carries the location of the next continent. For all other Platforms than Genesis, you should quickly check each chest to get stepwise to the next continents in order to finally get to Saharia.
Along our way we will find treasures which offer money or leadership. It is advisable to get some money, but then we should only take the leadership. High class monsters need a high leadership in order to be bought.
3. Genesis Glitch
For the Genesis Platform there is a glitch, which can be abused:
Take the sorceress as the character of choice, because she can use magic directly from the beginning and is able to "buy" 5 magic spells.
Starting in Continentia we visit every town in order to find the "Castle Gate" spell. If we find it, we buy it 2 times. We also need either "Bridge" or "Time Stop" spells, with "Time Stop" the thing is easier. We need 2 times "Time Stop" or 2 times "Bridge". "Time Stop" has to be searched for in the towns. "Bridge" is always available at "Town of Hunterville" (the first town from the Castle).
Along the way searching for the spells (if we do not find "Castle Gate", reset the console and try again), we just visit Castle "Rhytacon", which is South-East of Continentia. It is very important, that we do not visit any other Castle than Rhytacon!
Now Rhytacon is the only Castle listed, when we use the Castle Gate spell.
If we have Time Stop, we cast it 2 or 3 times immediately.
Then we cast Castle Gate one time, which transports us to Rhytacon, then we do not move a muscle and spell Castle Gate with Rhytacon again, to be magically transported elsewhere (to be correct, it's Castle Endryx on Archipelia, the 3rd of the 4 continents).
Endryx Castle is surrounded by two monsters. With Time Stop active, we can go west to Topshore Town and rent a ship. With the Bridge spell we have to go north and build two bridges over the water in order to reach Simpleton Town where we can rent the ship there. Being on the ship, we are safe from being attacked from monsters being way too strong for us. Now the continent Archipelia has many many treasures which are not surrounded by monsters, so the possibility of getting the passage to Saharia is very high.
4. Being at Saharia
Here we need to find a location where we can buy flying monsters. In order to buy some we also need the high leadership, which we can get from treasures lying around. If we found a location not filled with dragons (our monster of choice), but with another flying monster, we take just one and dismiss all other monsters from our army. Now we can fly (on Genesis it is Button "B"). In order to land, we press the same button, landing is only allowed on green surface. Now we fly around Saharia, take the chests (preferably some money and lots of leadership). And finally find the location of dragons (it's a hill). We buy 2-4 which is really enough for now. After that we leave Saharia and go back to Continentia.
5. Back to Continentia
Here we buy siege weapons. Locate every Castle, check which villain is in there, then go to a town, get a new contract and defeat the villain with our dragons. On the way we find artefacts etc. Defeated enemies and found artefacts reveal the location of the sceptre which can be easily found by flying over the continents.
If a location looks like the revealed location by the puzzle pieces, we search the area and hopefully save the kingdom :)