TAOCP 7.2.2.1 Exercise 68
Working
Section 7.2.2.1: Dancing Links
Exercise 68. [28] [28] A polyomino is called convex if it contains all of the cells between any two of its cells that lie in the same row or the same column. (This happens if and only if it has the same perimeter as its minimum bounding box does, because each row and column contribute 2.) For example, all of the pentominoes (36) are convex, except for 'U'.
a) Generate all ways to pack $n$ convex $n$-ominoes into an $n \times n$ box, for $n \le 7$.
b) In how many ways can nine convex nonominoes be packed into a $9 \times 9$ box, when each of them is small enough to fit into a $4 \times 4$? (Consider also the symmetries.)
Verified: no
Solve time: 3m35s
Working