Placing rectangles on a grid randomly?

I'm trying to make a Battleship game. When it came to make the AI opponent I had a few ideas how to get it working, but I stumbled across placing the ships in the first place. So here is some info on what I'm planning:

The player defines a grid size. Then he defines which and how many ships are placed (height and width of every ship). The computer opponent then should proceed to fill it's own field with the exact same ships as the player did, except maybe flipping them by 90 degrees some time. And ofcourse he shouldn't just copy the players board. Or mirror it or something, it should be actually random. Well as far as a PC is capable of, which means pseudo random. What I first thought of would be the following. I create a list with every possible scenario of how these squares could be placed in the grid without hurting the laws of the game. Then I just choose a random entry of the list and apply that to my game. But that is (in my oppinion) not very efficient. Since it's only done once per game it would be tolerable, but it just doesn't seem like a good solution to me. Also I thoght about a brute force attempt where the computer just picks spots and orientations at random until it succeeds. Not very elegant either, especially if the playe chooses to fill up the board with many ships. So I would really like to hear your guys oppinion on that. Am I missing something? Is there an algorithm which handles these kinds of problems?

Greets and thanks for your time!