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.
I must say that your proot that lego is NP-complete is unconvincing.
First, the construction does not scale, as each new variable is encoded as a new color pair. In practice, one could not see the color difference for more than 7 variables neither would be the manufactoring cost in reasonable bounds.
Second, normally people have many lego blocks and thus the restriction on the amount of lego blocks is artificial
Thidly, the shape you want to construct is artificial. I should be eiter a tower or a wall
The author would like to thank the reviewer for a thorough review and thoughtful comments!
The reviewer raises a number of interesting concerns. However, we feel the reviewer did not fully comprehend the scope of the work, and misjudged the results based on incorrect assumptions.
The first concern regards the scalability of the construction. However, as the focus of this work is purely theoretical and not performance-based, scalability issues were not found to be of critical importance to the contribution. Note, for example, that there will never be more than 10^100 LEGO blocks in the world anyway.
We should note that our construction is scalable within reasonable bounds, though. Firstly, much more than "7 colours" are possible: do consider transparent blocks and shaped blocks. Secodly, one needn't limit himself to 1x1x1/1x1x2 blocks for variable representation. Width-N blocks (Nx1x1/Nx1x2), depth-N blocks (1xNx1/1xNx2) and their combinations are also possible. This, and some other trivial modifications of the construction are left as an excercise to the reader.
The reviewer noted that the restriction on the set of LEGO blocks is of limited importance. This is an interesting concern. However, our work is based on completely different first principles. Namely, the task we regard here is the problem of constructing a LEGO toy, depicted on a retail box, from the blocks in that box and without consulting the manual. This is the most typical puzzle a LEGO fan would enjoy solving. The problem of constructing a given shape from an unlimited set of blocks is a completely different task, which is much less realistic and not as interesting. We do plan, however, to include this task in our future research.
Finally, we find the concern regarding the exact shape of the construction as somewhat flawed. Firstly it is a proven fact, that that towers and walls are among the dullest known LEGO configurations (please, consult our extensive previous work on the subject). Secondly, our configuration can be easily recast in a tower- or wall- formulation, which is also left as an excercise for the reader.
Thank you for participating in our peer-reviewed blog-driven open-access no-nonsense research project 🙂