  We present a methodology for generating Ising Hamiltonians of tunable
complexity and with a priori known ground states based on a decomposition of
the model graph into edge-disjoint subgraphs. The idea is illustrated with a
spin-glass model defined on a cubic lattice, where subproblems, whose couplers
are restricted to the two values {-1,+1}, are specified on unit cubes and are
parametrized by their local degeneracy. The construction is shown to be
equivalent to a type of three-dimensional constraint satisfaction problem known
as the tiling puzzle. By varying the proportions of subproblem types, the
Hamiltonian can span a dramatic range of typical computational complexity, from
fairly easy to many orders of magnitude more difficult than prototypical
bimodal and Gaussian spin glasses in three space dimensions. We corroborate
this behavior via experiments with different algorithms and discuss
generalizations and extensions to different types of graphs.
