CODEWITHSUNDEEP
pythonpython-3.xpython-2.7constraintsconstraint-programming
ma7642
ma7642

Reputation: 149

Constraint Satisfaction Problem - ERROR: Class object has no attribute

I am trying to develop a framework for a Constraint Satisfaction Problem (CSP) following the code and explanations from this page. My Python version is 2.7.13, so I had to slightly modify the code (I can't make updates or downloads in this computer). See below:

from abc import ABCMeta

class abstractclassmethod(classmethod):

    __isabstractmethod__ = True

    def __init__(self, callable):
        callable.__isabstractmethod__ = True
        super(abstractclassmethod, self).__init__(callable)

class Constraint(object):

    def __init__(self, variables):
        self.variables = variables

    @abstractclassmethod
    def satisfied(self, assignment):
        pass

class CSP(Constraint):

    def __init__(self, variables, domains):
        self.variables   = variables 
        self.domains     = domains 
        self.constraints = {}

        for variable in self.variables:
            self.constraints[variable] = []
            if variable not in self.domains:
                raise LookupError("Every variable should have a domain assigned to it")

    def add_constraint(self, constraint):
        for variable in constraint.variables:
            if variable not in self.variables:
                raise LookupError("Variable in constraint not in CSP")
            else:
                self.constraints[variable].append(constraint)

    def consistent(self, variable, assignment):
        for constraint in self.constraints[variable]:
            if not constraint.satisfied(assignment):
                return False

        return True

    def backtracking_search(self, assignment):

        if len(assignment) == len(self.variables):
             return assignment

        for v in self.variables:
             if v not in assignment:
                unassigned.append(v)

        first = unassigned[0]
        for value in self.domains[first]:
            local_assignment = assignment[:] # we make a copy
            local_assignment[first] = value 

            if self.consistent(first, local_assignment):
                result = self.backtracking_search(local_assignment)
                if result is not None:
                    return result 
        return None


 class MapColoringConstraint(Constraint):

    def __init__(self, place1, place2):
        self.place1 = place1
        self.place2 = place2
        super(Constraint, self).__init__()

    def satisfied(sef, assignment):
        if self.place1 not in assignment or self.place2 not in assignment:
            return True
        return assignment[self.place1] != assignment[self.place2]

I am testing the framework with the Australian map-coloring problem (as shown in the link above)

if __name__ == "__main__":

    variables =  ["Western Australia", "Northern Territory", "South Australia",
                         "Queensland", "New South Wales", "Victoria", "Tasmania"]
    domains = {}

    for variable in variables:
        domains[variable] = ['red', 'green', 'blue']

    csp = CSP(variables, domains)
    csp.add_constraint(MapColoringConstraint("Western Australia", "Northern Terriroty"))
    csp.add_constraint(MapColoringConstraint("Western Australia", "South Australia"))
    csp.add_constraint(MapColoringConstraint("South Australia", "Northern Territory"))
    csp.add_constraint(MapColoringConstraint("Queensland", "Northern Territory"))
    csp.add_constraint(MapColoringConstraint("Queensland", "South Australia"))
    csp.add_constraint(MapColoringConstraint("Queensland", "New South Wales"))
    csp.add_constraint(MapColoringConstraint("New South Wales", "South Australia"))
    csp.add_constraint(MapColoringConstraint("Victoria", "South Australia"))
    csp.add_constraint(MapColoringConstraint("Victoria", "New South Wales"))
    csp.add_constraint(MapColoringConstraint("Victoria", "Tasmania"))

    solution = csp.backtracking_search() 
    if solution is None:
        print("No solution found!")
    else:
        print(solution)

I am constantly getting the following error:

File 'csp.py', line 33, in add_constraint
    for variable in constraint.variables:
AttributeError: 'MapColoringConstraint' object has no attribute 'variables'

Except for a few modifications, my code should be the same as that on the webpage. I seem to be overlooking something or removed something I should not. Can someone help me figure out what is missing?

Upvotes: 0

Views: 713

Answers (1)

Gideon Maina
Gideon Maina

Reputation: 870

Your call to the super() method on the parent's init() method is where the issue is super(Constraint, self).__init__(), this does not assign the parent variable attribute to the child class, hence when the add_constraint() method tries to get the attribute it throws the error you have indicated.

You can read more about pythons inheritance hierarchy to understand more, this article is good.

I have done some few references to the article and updated the code as below, it should be able to run as expected. 

# coding: utf-8
from abc import ABC, abstractmethod


class Constraint(ABC):
    def __init__(self, variables):
        self.variables = variables

    @abstractmethod
    def satisfied(self, assignment):
        pass


class CSP():
    def __init__(self, variables, domains):
        self.variables = variables
        self.domains = domains
        self.constraints = {}
        for variable in self.variables:
            self.constraints[variable] = []
            if variable not in self.domains:
                raise LookupError(
                    'Every variable should have a domain assigned to it.')

    def add_constraint(self, constraint):
        for variable in constraint.variables:
            if variable not in self.variables:
                raise LookupError("Variable in constraint not in CSP")
            else:
                self.constraints[variable].append(constraint)

    def consistent(self, variable, assignment):
        for constraint in self.constraints[variable]:
            if not constraint.satisfied(assignment):
                return False
        return True

    def backtracking_search(self, assignment={}):
        # assignment is complete if every variable is assigned (our base case)
        if len(assignment) == len(self.variables):
            return assignment
        # get all variables in the CSP but not in the assignment
        unassigned = [v for v in self.variables if v not in assignment]
        first = unassigned[0]
        for value in self.domains[first]:
            local_assignment = assignment.copy()
            local_assignment[first] = value
            # if we're still consistent, we recurse (continue)
            if self.consistent(first, local_assignment):
                result = self.backtracking_search(local_assignment)
                if result is not None:
                    return result
        return None


class MapColoringConstraint(Constraint):
    def __init__(self, place1, place2):
        super().__init__([place1, place2])
        self.place1 = place1
        self.place2 = place2

    def satisfied(self, assignment):
        if self.place1 not in assignment or self.place2 not in assignment:
            return True
        return assignment[self.place1] != assignment[self.place2]


if __name__ == '__main__':
    variables = [
        "Western Australia", "Northern Territory", "South Australia",
        "Queensland", "New South Wales", "Victoria", "Tasmania"
    ]
    domains = {}
    for variable in variables:
        domains[variable] = ['red', 'green', 'blue']

    csp = CSP(variables, domains)
    csp.add_constraint(
        MapColoringConstraint("Western Australia", "Northern Territory"))
    csp.add_constraint(
        MapColoringConstraint("Western Australia", "South Australia"))
    csp.add_constraint(
        MapColoringConstraint("South Australia", "Northern Territory"))
    csp.add_constraint(
        MapColoringConstraint("Queensland", "Northern Territory"))
    csp.add_constraint(MapColoringConstraint("Queensland", "South Australia"))
    csp.add_constraint(MapColoringConstraint("Queensland", "New South Wales"))
    csp.add_constraint(
        MapColoringConstraint("New South Wales", "South Australia"))
    csp.add_constraint(MapColoringConstraint("Victoria", "South Australia"))
    csp.add_constraint(MapColoringConstraint("Victoria", "New South Wales"))
    csp.add_constraint(MapColoringConstraint("Victoria", "Tasmania"))

    solution = csp.backtracking_search()

    if solution is None:
        print("No solution found!")
    else:
        print(solution)

Sample run

$ python csp.py
{'Western Australia': 'red', 'Northern Territory': 'green', 'South Australia': 'blue', 'Queensland': 'red', 'New South Wales': 'green', 'Victoria': 'red', 'Tasmania': 'green'}
$ python --version
Python 3.7.5

Upvotes: 1

Related Questions