The smallest positive area achievable with m < n is 2m(n − m) halfsquares; and when m = n the smallest is 2n − 1. Thus we must have n ≤ (N +2)/2, and it’s feasible to backtrack through a finite number of cases.
There are 63 solutions when N = 56. But most of them are unpackable, because of an important property noted by T. H. O’Beirne in 1962: Exactly five of the tetraboloes, namely {E, G, J, K, L}, have an odd number of unmatched 
sides in each direction. It follows that a + c (and b + d) must be odd.
Just 10 of the 63 solutions pass this extra test. Two of those ten — (1×29; 1, 1, 0, 0) and (3×11; 3, 1, 0, 0) — don’t work. But the other eight ...
Get The Art of Computer Programming, Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
