Wave Function Collapse (WFC) is among the most well-known and beloved procedural content generation algorithms. WFC solvers can be understood as a specific type of constraint solver, and as such, backtracking is an integral part of exploring the space of possible solutions. Recent advancements were inspired by this algorithm to model procedural music generation, using a hierarchy of many canvases, each with its own semantic domain within music composition (sections, chords, melody). In the model, due to the structural dependencies between canvases, constraints that involve cells from different canvases make exhaustive backtracking a challenge. Existing backtracking methods only consider a single set of variables, but if a specific value on one canvas can affect the entire structure of another canvas, we need more elaborate ways to deal with conflicts.

This paper presents the basic principles that backtracking models for this hierarchy should abide by, and additional guidelines for evaluating them. Two approaches are proposed, and their runtime efficiencies are compared. Depth-first traversal of the canvas hierarchy results in significantly shorter runtimes than its breadth-first counterpart.