Conventional constraint satisfaction problem (CSP) formulations are static. There is a given set of constraints and variables, and the structure of the constraint graph does not change. For a lot of search problems, though, it is not clear in advance what a solution’s constraint graph will look like. To overcome these deficiencies, we introduce the concept of structural constraints, which are restrictions on admissible constraint graphs. The construction of constraint graphs is based on the concept of graph grammars. This allows us to formulate and solve structural constraint satisfaction problems (SCSPs), handling combinatorial search problems without explicitly giving the solution’s structure.