A 2x2 room is easily filled as, once the empty square is allocated, the mere remainder of the room makes up a single tile. As you can see from this picture, an empty square can also fit into any 4x4 pattern and it is that top-leftmost 4x4 pattern (herein referred to as the TL pattern) that is key for filling any size room.
In this example, the empty square has a coordinate of (2,5) in an 8x8 room. Once the first 4x4 pattern was found, the TL pattern from the previous image was wrapped around it and the pink tile filled in what was left. Another way of looking at the process (I'm unsure as to which is more efficient for an algorithm) is the pink tile being placed on the corner of the 4x4 pattern (this corner is also the center of the room; in larger rooms this corner is at the center of a subsection of the room), followed by the TL pattern wrapping around the pink tile.
The following process illustrates how to fill a 32x32 room with an empty tile coordinate of (2,19):
The reasoning behind finding the empty square's position relative to fourths is that the room is filled via an inverse process. You might find it more streamlined to simply find the empty square in a two hundred fifty-sixth from the start, but the room is still filled by fourths:
You take the empty square and generate a 4x4 pattern around it. This can be done similar to the 8x8 example above. The remainder of the two hundred fifty-sixth that the empty square occupies becomes a tile, then you wrap a 2x2 pattern around that with empty spaces becoming a tile (or have a tile attach itself to the corner of the two hundred fifty-sixth [which corner is determined by being in the center of a sixty-fourth] with other tiles generating around that tile).
This process can be used to fill any sized room presented in your problem, but unfortunately I am not so mathematically minded as to translate this process into an algorithm.
(P.S. All of the images in this post were created using MS Paint, so you can take your Photoshop and shove it. )