FilesExpand file tree

 master

/

csp.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

82 lines (71 loc) · 3.49 KB

 master

/

csp.py

Top

File metadata and controls

• Code
• Blame

82 lines (71 loc) · 3.49 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

# csp.py

# From Classic Computer Science Problems in Python Chapter 3

# Copyright 2018 David Kopec

#

# Licensed under the Apache License, Version 2.0 (the "License");

# you may not use this file except in compliance with the License.

# You may obtain a copy of the License at

#

# http://www.apache.org/licenses/LICENSE-2.0

#

# Unless required by applicable law or agreed to in writing, software

# distributed under the License is distributed on an "AS IS" BASIS,

# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

# See the License for the specific language governing permissions and

# limitations under the License.

from typing import Generic, TypeVar, Dict, List, Optional

from abc import ABC, abstractmethod

V = TypeVar('V') # variable type

D = TypeVar('D') # domain type

# Base class for all constraints

class Constraint(Generic[V, D], ABC):

# The variables that the constraint is between

def __init__(self, variables: List[V]) -> None:

self.variables = variables

# Must be overridden by subclasses

@abstractmethod

def satisfied(self, assignment: Dict[V, D]) -> bool:

...

# A constraint satisfaction problem consists of variables of type V

# that have ranges of values known as domains of type D and constraints

# that determine whether a particular variable's domain selection is valid

class CSP(Generic[V, D]):

def __init__(self, variables: List[V], domains: Dict[V, List[D]]) -> None:

self.variables: List[V] = variables # variables to be constrained

self.domains: Dict[V, List[D]] = domains # domain of each variable

self.constraints: Dict[V, List[Constraint[V, D]]] = {}

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: Constraint[V, D]) -> None:

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)

# Check if the value assignment is consistent by checking all constraints

# for the given variable against it

def consistent(self, variable: V, assignment: Dict[V, D]) -> bool:

for constraint in self.constraints[variable]:

if not constraint.satisfied(assignment):

return False

return True

def backtracking_search(self, assignment: Dict[V, D] = {}) -> Optional[Dict[V, D]]:

# 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: List[V] = [v for v in self.variables if v not in assignment]

# get the every possible domain value of the first unassigned variable

first: V = 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: Optional[Dict[V, D]] = self.backtracking_search(local_assignment)

# if we didn't find the result, we will end up backtracking

if result is not None:

return result

return None