🚀 go-pugleaf

Monkey puzzle is NP-complete: In response to the query of Anne Lomax on
TheoryNet, Feb. 1, 1990.
-----------------------------------------------------------------------

You are right -- I did not include a pointer to the proof in the
bibliographic notes of the Algorithmics book. The idea is inspired by
a discussion I had with Adi Shamir. The reduction is from 3-PARTITION,
which is NP-complete in the strong sense (see Garey and Johnson's book,
page 224). Given the 3m numbers, you prepare a set of cards for each,
that make it possible to tile the tiles in the set side by side only. So
if the number is, say, 17, there will be 17 cards that can only fit together
to form a line of length 17, but they have colors (or monkey halves) to
enable that line to be attached on either side to some other such line.
In addition, each line is colored on the top and bottom to enable attachment
to other such lines from above and below. Now, you prepare a set of m^2-3m
tiles of a special kind, that enable ONLY a tiling of a rectangle of width
m-3 and heght m, whose left hand side can be attached to the ends of the
lines coming from the numbers. It can now be shown that these tiles can
cover an mxm square if and only if you can partition the 3m numbers into
m triplets, each summing to B. For one direction, if the numbers can be
partitioned so, then you would lay down m lines of tiles, each representing
the three numbers in the triplet, and each then being of total length B, and
the rest of the square would then be a rectangle as above, and tiled with
the extra tiles. Conversely, assume you have been able to make the mxm
square. Then, the fact that you have managed to lay down the (m-3)xm rectangle
means that the rest of the square is a rectangle too, and since each number
is between B/2 and B/4, there must be exactly three numbers per line,
hence you have your partition.