Recently my players decided to make the game as hard as possible for themselves by planning a jailbreak that will make them fugitives before they complete their mission to spy on the King. To make matters even harder the minotaurs in the world are supposed to be jailed and killed on sight by order of the King... and it just so happens the person the group is saving is a player character that happens to be a minotaur. So, the group of fugitives with a minotaur is going to have to stealth around a highly populated city and the surrounding areas spying on the King of all people.
When the players decided that was the best idea I told them that I was going to make the game as hard as I possibly could (while still giving them a chance to succeed). Now I am faced with a level 5 party of a Minotaur Shaman, Dwarf Cleric, Human Wizard, Human Sorcerer and possibly a fifth member depending on his schedule.
So this leaves me with about 4-5 players at level 5. What is the hardest encounter I can throw at them that still gives them a chance to survive? is a level 8 solo creature to strong for 4 level 5s? is there anything in the DMGs I am blind and am missing regarding this?
NOTE: Everyone is agreed that the challenges are likely to be deadly, so I am looking for a way to supply enemies in my encounters that have a good chance of killing the players and will be hard to take down.