  In this article, we show that the completion problem, i.e. the decision
problem whether a partial structure can be completed to a full structure, is
NP-complete for many combinatorial structures. While the gadgets for most
reductions in literature are found by hand, we present an algorithm to
construct gadgets in a fully automated way. Using our framework which is based
on SAT, we present the first thorough study of the completion problem on sign
mappings with forbidden substructures by classifying thousands of structures
for which the completion problem is NP-complete. Our list in particular
includes interior triple systems, which were introduced by Knuth towards an
axiomatization of planar point configurations. Last but not least, we give an
infinite family of structures generalizing interior triple system to higher
dimensions for which the completion problem is NP-complete.
