I read this fairy tale when I was a kid, around 30 years ago. I've now tried searching for this story, checking the usual suspects (brothers Grimm and H.C.Andersen), but haven't found anything matching.
Here's the story:
Once upon a time there was a king of a small/poor kingdom, and he had three sons. Since they were so poor, the king decided that one of the princes should marry the princess in a much larger/richer kingdom. The problem was that this particular princess was very picky, and also had magical powers. So any suitors she didn't like, she would turn into stone statues.
The princes went to the princess' castle, and entered it one at a time (maybe only one prince was allowed in per day?). The garden of the castle was full stone statues, all the previous suitors.
Secretly, the princess had disguised/turned herself into a maid so that she could observe the princes before meeting them officially. The first (and of course the oldest) prince went in first; he was certain that the princess would be very impressed by his strength and fighting skills. He of course treated the maid very poorly. Needless to say, the princess turned him into a statue.
The second prince didn't do any better.
The third prince was very uncertain of himself, I think he discussed with the maid that he didn't really want to do this, but had to try in order to save his poor country. If all three princes were turned to stone, their kingdom would be ruined. He also treated the maid well.
I believe the maid turned into the princess right there in front of him. I guess they got married, and possibly she brought back to life the other too princes (maybe even everyone she had turned to stone?). And they lived happily ever after.
This story to me seems to be a bit more modern than Grimm/Andersen; the princess decides herself whom she wants to marry, and there are no animals featured.