The amusing fact that Minesweeper was proven to be NP-complete is quite well known in certain circles. However, it seems that no one has yet cared to publicly demonstrate the (probably obvious, but not a single bit less amusing) fact, that constructing LEGO toys is also an NP-complete task. Here I fix this disturbing flaw and present a reduction of SAT to LEGO by a simple example.
Suppose you are given the following set of LEGO blocks
and you wish to construct the following structure from them (using only this picture as a reference):
It turns out that devising such a configuration is equivalent to finding a satisfying assignment for the boolean formula 
, and it is possible to devise an analogous configuration for any other logical formula in CNF. Thus, building LEGO must be at least as hard as satisfying boolean formulas, that is, NP-hard.
Indeed, let the red brick correspond to the variable 
, the blue brick let be 
, the pink brick 
and the light blue brick 
.
Consider the part I of the target configuration (the one in the upper left). It contains one red brick and one light blue brick, but because of the black block in front of them we don't know whether the red and the light blue bricks are of height 1 or 2. There are three possible options:
We say that this configuration corresponds to the term 
, where having a higher brick for a given variable corresponds to setting the value of that variable to True. Clearly, for the configuration to be possible either the red brick () or the light blue brick () must be high, and therefore a proper choice of bricks here corresponds to a choice of values in the expression . Analogously, part II corresponds to the term 
and the fact that both parts are possible translates to the full equation .
Now what about parts III and IV? These guarantee that if we choose the high red brick when constructing parts I and II, we shall necessarily have to use the shorter pink brick there, and similarly for the blue and light blue bricks. Indeed, due to the choice of white bricks there are two ways of constructing part III:
In the first case we use up the high red brick and the short pink brick for constructing part III, and therefore end up with the short red brick and high pink brick for building parts I and II. This corresponds to picking the value False for . Similarly, the second way of constructing part III would enforce the value True for the variable .
A short reflection should convince you now, that the same scheme can be used to represent any other CNF boolean expression. As it is well known that finding a satisfying assignment for a boolean formula is NP-complete, it follows that LEGO is NP-complete too.
Q.E.D.
