One embodiment of the present invention provides a system that reuses information associated with a constraint solving operation for a problem domain. This system begins by receiving a constraint problem from the problem domain. Then, the system searches through a problem cache for an entry which corresponds to the canonical representation. If a corresponding entry does not exist in the problem cache, the system produces an entry in the problem cache for the canonical representation. Otherwise, if a corresponding entry already exists in the problem cache, the system generates a solution to the canonical representation by reusing the solver heuristic associated with the corresponding entry in the problem cache.