One goal of Artificial Intelligence is to develop and understand computational mechanisms for solving difficult real-world problems. Unfortunately, domains traditionally used in general problem-solving research lack important characteristics of real-world domains, making it difficult to apply the techniques developed. Most classic AI domains require satisfying a set of Boolean constraints. Real-world problems require finding a solution that meets a set of Boolean constraints and performs well on a set of real-valued constraints. In addition, most classic domains are static while domains from the real world change. In this paper we demonstrate that SteppingStone, a general learning problem solver, is capable of solving problems with these characteristics. SteppingStone heuristically decomposes a problem into simpler subproblems, and then learns to deal with the interactions that arise between the subproblems. In lieu of an agreed upon metric for problem difficulty, we choose significant problems that are difficult for both people and programs as good candidates for evaluating progress. Consequently we adopt the domain of logic synthesis from VLSI design to demonstrate SteppingStone’s capabilities.