reid@math.arizona.edu (michael reid) wrote:

check out "tiling a polygon with rectangles" by claire and richard kenyon, proceedings of the 33rd foundations of computer science (FOCS), 1992, pp. 610-619. theorem 3 of that paper asserts that, given a simply connected polyomino region tiled by m x 1 (vertical) polyominoes and 1 x n (horizontal) polyominoes, then any two such tilings can be obtained from one another by steps of the form

replace an m x n subrectangle tiled by horizontal tiles by one tiled by vertical tiles

or the inverse operation.

Neat! And the restriction to simply connected regions is necessary: _______ _______ | |_____| |_____| | | | | | | | | | |_|___| | | |___|_| |_____|_| |_|_____| Dan