Min-conflicts Algorithm

Min-conflicts Algorithm

The min conflicts algorithm is a search algorithm to solve constraint satisfaction problems (CSP problems).

It assigns random values to all the variables of a CSP. Then it selects randomly a variable, whose value conflicts with any constraint of the CSP. Then it assigns to this variable the value with the minimum conflicts. If there are more than one minimum, it chooses one among them randomly. After that, a new iteration starts again until a solution is found or a preselected maximum number of iterations is reached.

Because a CSP can be interpreted as a local search problem when all the variables have assigned a value (complete states), the min conflicts algorithm can be seen as a heuristic that chooses the state with the minimum number of conflicts.