Music harmonization has long been recognized as a highly intellectual process. Musicologists have studied music pieces by great composers and formulated a number of symbolic rules. However, these rules usually form only a set of heuristics and may not be absolutely precise. In this paper, we demonstrate how to train a Boltzmann machine to capture these syntactic rules and use it to construct an effective Boltzmann machine (EBM) to harmonize some unseen pieces. We have also incorporated ways to apply absolute constraints to the completion process. Our experiments demonstrate that using an EBM, ‘good’ harmonies can be non-deterministically synthesized along with a relative measure of their quality.