The four-part harmonization problem is a well known problem that has been studied in the last three centuries by music scholars. The goal is to build up three different voices, melodies, based on a previously provided one, being it a soprano melody or a bass instead, so that a complete soprano, alto, tenor and bass (SATB) score is completed. The nature of the problem has attracted interest for decades, and different artificial intelligence techniques have subsequently been applied, such as constraint programing or genetic algorithms. Although researchers employing the first have already stated that the problem is basically solved, and comparisons with GAs typically benefit the first, we think that a critical review of literature may provide useful information demonstrating that the problem is open for improvement, and that GAs still have an opportunity: tests presented in literature frequently employ examples of low difficulty, which provide misleading conclusions. In this paper we present a review the literature and analyzed many of the solutions provided, and have seen how they are not solutions at all, given the number of errors they embody. Yet, we not only try to show drawbacks of previous approaches. We also try to understand difficulties for GAs when addressing the problem. We analyze the nature of the problem performing a number of tests, and try to see why the standard GA cannot cope with the problem. We propose new approaches that show how GAs could in the future be perfectly capable of addressing large and complex samples, providing solutions of much higher quality.
