python-constraint · hassidm · Jun 4, 2019 · Jun 4, 2019 · Jun 4, 2019 · Jun 4, 2019
diff --git a/README.rst b/README.rst
@@ -99,6 +99,7 @@ The following solvers are available:
 - Backtracking solver
 - Recursive backtracking solver
 - Minimum conflicts solver
+- Least conflicts solver (returns a solution with minimum conflicts).
 
 
 .. role:: python(code)

diff --git a/constraint/__init__.py b/constraint/__init__.py
@@ -50,6 +50,7 @@
     "BacktrackingSolver",
     "RecursiveBacktrackingSolver",
     "MinConflictsSolver",
+    "LeastConflictsSolver",
     "Constraint",
     "FunctionConstraint",
     "AllDifferentConstraint",
@@ -718,6 +719,91 @@ def getSolution(self, domains, constraints, vconstraints):
         return None
 
 
+class LeastConflictsSolver(Solver):
+    """
+    Problem solver based on the minimum conflicts theory.
+    With this solver - you will always get an assignment -
+    the one with the minimum coflicts that the algorithm found.
-    the one with the minimum coflicts that the algorithm found.
+    the one with the minimum conflicts that the algorithm found.
-    the one with the minimum coflicts that the algorithm found.
+    the one with the minimum conflicts that the algorithm found.
+
+    Examples:
+
+    >>> result = [[('a', 1), ('b', 2), ('c', 1)],
+    ...           [('a', 2), ('b', 1), ('c', 1)]]
+
+    >>> problem = Problem(LeastConflictsSolver())
+    >>> problem.addVariables(["a", "b"], [1, 2])
+    >>> problem.addVariable("c", [1])
+    >>> problem.addConstraint(lambda a, b: b != a, ["a", "b"])
+    >>> problem.addConstraint(lambda a, b: b != a, ["a", "c"])
+    >>> problem.addConstraint(lambda a, b: b != a, ["b", "c"])
+
+    >>> solution = problem.getSolution()
+    >>> sorted(solution.items()) in result
+    True
+
+    >>> problem.getSolutions()
+    Traceback (most recent call last):
+       ...
+    NotImplementedError: LeastConflictsSolver provides only a single solution
+
+    >>> problem.getSolutionIter()
+    Traceback (most recent call last):
+       ...
+    NotImplementedError: LeastConflictsSolver doesn't provide iteration
+    """
+
+    def __init__(self, steps=1000):
+        """
+        @param steps: Maximum number of steps to perform before giving up
+                      when looking for a solution (default is 1000)
+        @type  steps: int
+        """
+        self._steps = steps
+
+    def getSolution(self, domains, constraints, vconstraints):
+        assignments = {}
+        best_assign = {}
+        best_conflicted = float('inf')
+        # Initial assignment
+        for variable in domains:
+            assignments[variable] = random.choice(domains[variable])
+        for _ in xrange(self._steps):
+            conflicted = 0
+            lst = list(domains.keys())
+            random.shuffle(lst)
+            conflicted_var = None
+            for variable in lst:
+                # Check if variable is not in conflict
+                for constraint, variables in vconstraints[variable]:
+                    if not constraint(variables, domains, assignments):
+                        conflicted += 1
+                # Variable has conflicts. Save it:
+                if conflicted > 0 and conflicted_var is None:
+                    conflicted_var = variable
+            if conflicted == 0:
+                return assignments
+            if best_conflicted > conflicted:
+                best_assign = assignments
+                best_conflicted = conflicted
+            # Find values with less conflicts.
+            mincount = len(vconstraints[conflicted_var])
+            minvalues = []
+            for value in domains[conflicted_var]:
+                assignments[conflicted_var] = value
+                count = 0
+                for constraint, variables in vconstraints[conflicted_var]:
+                    if not constraint(variables, domains, assignments):
+                        count += 1
+                if count == mincount:
+                    minvalues.append(value)
+                elif count < mincount:
+                    mincount = count
+                    del minvalues[:]
+                    minvalues.append(value)
+            # Pick a random one from these values.
+            assignments[conflicted_var] = random.choice(minvalues)
+        return best_assign
+
 # ----------------------------------------------------------------------
 # Variables
 # ----------------------------------------------------------------------

diff --git a/tests/test_solvers.py b/tests/test_solvers.py
@@ -1,5 +1,5 @@
-from constraint import Problem, MinConflictsSolver
-
+from constraint import Problem, MinConflictsSolver, LeastConflictsSolver
+import itertools
 
 def test_min_conflicts_solver():
     problem = Problem(MinConflictsSolver())
@@ -15,3 +15,24 @@ def test_min_conflicts_solver():
     ]
 
     assert solution in possible_solutions
+
+
+def test_least_conflicts_solver():
+    # another test for LeastConflictsSolver
+
+    problem = Problem(LeastConflictsSolver())
+
+
+    result = [[('a', 1), ('b', 2), ('c', 1)], [('a', 2), ('b', 1), ('c', 1)]
+              , [('a', 2), ('b', 2), ('c', 1)]]
+
+    problem.addVariables(["a", "b"], [1, 2])
+    problem.addVariable("c", [1])
+    problem.addConstraint(lambda a, b: b != a, ["a", "b"])
+    problem.addConstraint(lambda a, b: b != a, ["a", "c"])
+    problem.addConstraint(lambda a, b: b != a, ["b", "c"])
+
+    solution = problem.getSolution()
+    assert sorted(solution.items()) in result
+
+test_least_conflicts_solver()