THE LEGO CONSTRUCTION PROBLEM

The LEGO Construction Problem is the problem of deciding which bricks to place where in a predefined 3D construction. The input consists of coloured voxels that each correspond to the size of a LEGO unit, such that all LEGO bricks are multiples of this LEGO unit. While we must place bricks of a predefined colour on all visible voxels of the construction, the non-visible bricks on the inside have no colour constraints and can even be hollowed out if the construction remains stable. We limit the set of available bricks to rectangular bricks. A solution to the LEGO Construction Problem is feasible if all bricks are placed within the design domain, the bricks do not overlap, all colour constraints are obeyed, and all bricks connect into a single connected component. The objective is to minimise the number of bricks used while maximising the strength of the construction. Finding stable constructions require advanced search methods, because relatively small constructions lead to a colossal amount of possible brick combinations.

This presentation introduces the LEGO Construction Problem. First, we present various objectives proposed in the literature that differ in complexity and quality.  Second, we discuss various search strategies for optimising these objectives. We conclude this presentation by discussing promising avenues of future research.