Fortunately a Seeman tile doesn't stick tightly when only one sticky end is bound. Tiles can be designed so that no two types have two identical sticky ends. Then exactly one tile type fits at each spot along a growing frontier.
The expected time to fill an n×n rectangle is O(n2)