High Entropy Alloys (HEAs), Multi-principal Component Alloys (MCA), or Compositionally Complex Alloys (CCAs) are alloys that contain multiple principal alloying elements. While many HEAs have been shown to have unique properties, their discovery has been largely done through costly and time-consuming trial-and-error approaches, with only an infinitesimally small fraction of the entire possible composition space having been explored. In this work, the exploration of the HEA composition space is framed as a Continuous Constraint Satisfaction Problem (CCSP) and solved using a novel Constraint Satisfaction Algorithm (CSA) for the rapid and robust exploration of alloy thermodynamic spaces. The algorithm is used to discover regions in the HEA Composition-Temperature space that satisfy desired phase constitution requirements. The algorithm is demonstrated against a new (TCHEA1) CALPHAD HEA thermodynamic database. The database is first validated by comparing phase stability predictions against experiments and then the CSA is deployed and tested against design tasks consisting of identifying not only single phase solid solution regions in ternary, quaternary and quinary composition spaces but also the identification of regions that are likely to yield precipitation-strengthened HEAs.