@samjshah2 Suppose swapping columns A and B introduces a bad rectangle.
Then at least one side of the rectangle must be in column A or B, say A w.l.o.g.
Then swapping the columns back puts that side of the rectangle in column B. But that's the initial arrangement, which had no rectangles