Constraint Satisfaction Problems (CSP) belongs to this kind of traditional NPhard problems with a high impact in both, research and industrial domains. CSP problems are represented using triples (X, D, C) where X represents a set of variables that needs to be assigned with a particular value (V ), which must satisfy a set of constraints (C) [1,2]. The possible utilization of ACO algorithms to solve CSP problems requires the design of the decision graph where the ACO is executed. The classical approach [3,4,5] builds a graph where the nodes represent the variable/value pairs (< variable, value >) and the edges connect those nodes whose variables X are different. One of the problem with this representation is that problems composed by many variables or by variables that could be assigned with many different values, become really difficult to model due to the size of the resulting graph.