+2440 Max0815, you are very close; all you need to consider is the potential overlap. Look at the diagrams below.
Source: http://mathworld.wolfram.com/images/eps-gif/QueensMax_800.gif
Look at these two arrangements of the rooks. The first set you considered was that every rook occupied every column. The second set you considered was that every rook occupied every row. The diagrams above show some positions that satisfy both conditions; all the rooks are in every column and every row only once.
In order to figure out the overlap, ask yourself the following: How many ways can each rook occupy one and only one row and column?
Edit: I realize that the diagrams contain queens--not rooks. Oops! I think the main point still remains, however, so I will keep the diagrams as is.
