Structural decomposition methods have been proposed for identifying tractable Constraint Satisfaction Problems (CSPs)[1-5]. The basic principle is to decompose a CSP into tree-structured sub-problems. The subproblems are solved independently, then the original CSP is solved in a backtrack-free manner after the tree structure is made arc-consistent, as described in . In , we proposed four decomposition methods: HINGE
, CUT, TRAVERSE, and CaT and tested these methods on randomly generated CSPs. We compare these techniques on instances of the fully interlocked Crossword Puzzle Problems (CPPs)  taken from a public library  and identify special cases of the constraint hypergraphs where some decomposition techniques yield better results than others although in general the opposite holds. Our future work includes: 1)Identifying more such configurations, and building hybrid decompositions techniques that exploit this information; 2)Tailoring existing decomposition methods for fully interlocked CPPs so that every sub-problem, after backtrack search, has few solutions; and 3)Designing a heuristic for applying local search for fully interlocked CPPs. This work is supported by CAREER Award #0133568 from the National Science Foundation.