The first step in the constraint satisfaction problem in Python
TL;DR
――Learn the basic definition of what a constraint satisfaction problem is. ――I will try to solve a very simple problem by writing code in Python.
What is the constraint satisfaction problem?
In English, it is a constraint satisfaction problem. It is also written as CSP by taking the acronym.
The problem is to find a condition that can avoid the constraint within the range that the variable can select, with some variables and constraints given.
It mainly consists of the following three elements.
--variables: Given variables / elements --domains: Range of choices for each variable --constraints: Given constraints
For example, suppose you want to set up three MTGs, A, B, and C, as a very simple CSP example.
Mr. A has a schedule from 11:00 to 16:00, Mr. B from 12:00 to 15:00, and Mr. C from 14:00 to 18:00.
Also, Mr. A is in a great position at MTG, and Mr. A must attend MTG. If Mr. A participates, Mr. B and Mr. C can participate in MTG individually, or both Mr. B and Mr. C can participate in MTG at the same time (however, since it is MTG, at least A total of 2 people are needed).
If you assign this problem to variables, domains, and constraints, A, B, and C will be variables.
In addition, the range of time that each person can select (11:00 to 16:00 for Mr. A) is domains, and there are constraints that Mr. A must participate or at least two people are required for MTG.
Preparing Constraint Satisfiation Problem and Solving the Problem in Python
The problem to be solved with Python this time
Since it is the very first, we will solve a very simple problem.
Use 5 adjacent blocks as shown below.
Suppose that each of these five blocks can take one of the colors "red", "green", and "blue". However, there is a restriction that the same color must not be adjacent.
In this problem,
--variables: Each block from ① to ⑤. --domains: This time, all blocks have the same value, and you can select three values, "red", "green", and "blue". --constraints: Constraints that the same color must not be adjacent.
And so on. For example, it can be solved by assigning the following colors (there are many combinations that satisfy the conditions).
(It's a very simple problem, and it's easy to solve intuitively, so it's not necessary to write code, but as mentioned above, it's the first time, so I'll proceed as it is.)
What to use
- Python 3.8.5
Add constants for required imports and variables (block names) and domains (colors)
For the time being, we will prepare the necessary imports and constants.
Since we will use type annotations, we will import what we need from the typing module.
from typing import Dict, List, Optional
Also, since variables are blocks this time, each block name is defined as a constant in (1) to (5).
BLOCK_NAME_1: str = '①'
BLOCK_NAME_2: str = '②'
BLOCK_NAME_3: str = '③'
BLOCK_NAME_4: str = '④'
BLOCK_NAME_5: str = '⑤'
Since domains is the color that each block can take, this is also defined as red, green, and blue with a constant.
COLOR_RED: str = 'Red'
COLOR_GREEN: str = 'Green'
COLOR_BLUE: str = 'Blue'
Add a class for constraints
Create a single class of constraints.
The constraint is a sentence that "the same color cannot be set between adjacent blocks", but when actually handling it on the code, "the blocks ① and ② must not be the same color" "① Define constraints by instantiating multiple classes such as "blocks ④ and ③ must not have the same color" and "blocks ④ and ⑤ must not have the same color".
class ColoringConstraint:
def __init__(self, block_name_1: str, block_name_2: str) -> None:
"""
A class that handles one constraint of block color setting.
Parameters
----------
block_name_1 : str
The name of the first block between adjacent blocks (① to ⑤).
block_name_2 : str
The name of the second block between adjacent blocks (①-⑤).
"""
self.block_name_1: str = block_name_1
self.block_name_2: str = block_name_2
def satisfied(self, current_color_assignment: Dict[str, str]) -> bool:
"""
The boolean value of whether the current allocation status meets this constraint
get.
Parameters
----------
current_color_assignment : dict
Current allocation status to each block. Block name on the key,
A character string of color constants is set for each value.
Returns
-------
result_bool : bool
True and satisfying the constraint condition. Check under the following conditions
Will be executed.
-If in the assigned dictionary the first block or the second
If the block has not been allocated yet (target block)
True is set if the color has not yet been set to.
-Set if two blocks have already been assigned colors
True if the colors are not the same, otherwise
False is set (each of two adjacent blocks
True if different colors are set in.
"""
block_1_color_assigned: bool = \
self.block_name_1 in current_color_assignment
block_2_color_assigned: bool = \
self.block_name_2 in current_color_assignment
if not block_1_color_assigned or not block_2_color_assigned:
return True
color_1: str = current_color_assignment[self.block_name_1]
color_2: str = current_color_assignment[self.block_name_2]
if color_1 != color_2:
return True
return False
In the constructor, the constants of two adjacent block names are specified. For example, ① and ②, ① and ③.
The satisfied method is an interface that refers to the current color allocation value for each block to get the boolean value of whether the constraint condition is satisfied.
True is returned if the block has not yet been assigned a color, or if the colors between the two blocks are different. It will be used for backtracking search, which will be touched on later.
Definition of constants in the list of variables, domains, constraints
Prepare the constants of the list that stores each value by using the constants and classes of the prepared values alone. Each constant name is VARIABLES, DOMAINS, CONSTRAINTS.
VARIABLES: List[str] = [
BLOCK_NAME_1,
BLOCK_NAME_2,
BLOCK_NAME_3,
BLOCK_NAME_4,
BLOCK_NAME_5,
]
DOMAINS: List[str] = [
COLOR_RED,
COLOR_GREEN,
COLOR_BLUE,
]
CONSTRAINTS: List[ColoringConstraint] = [
ColoringConstraint(
block_name_1=BLOCK_NAME_1,
block_name_2=BLOCK_NAME_2),
ColoringConstraint(
block_name_1=BLOCK_NAME_1,
block_name_2=BLOCK_NAME_3),
ColoringConstraint(
block_name_1=BLOCK_NAME_2,
block_name_2=BLOCK_NAME_3),
ColoringConstraint(
block_name_1=BLOCK_NAME_3,
block_name_2=BLOCK_NAME_4),
ColoringConstraint(
block_name_1=BLOCK_NAME_3,
block_name_2=BLOCK_NAME_5),
ColoringConstraint(
block_name_1=BLOCK_NAME_4,
block_name_2=BLOCK_NAME_5),
]
Each value included in CONSTRAINTS is added by the combination of adjacent blocks.
Addition of backtracking search processing
This time, we use a technique called backtracking to calculate the combination of color allocations for each block that meets the constraint conditions.
Backtracking can be roughly summarized as follows.
--As long as the constraint conditions are met, the next block combination is verified one by one. --If the constraint condition cannot be met, return to the previous condition and try to see if the constraint condition is met with the value (color) of the next domain. --If the color allocation to all blocks is completed, the combination (allocation) result is returned and the processing is stopped.
The content is similar to the so-called previously written depth-first search algorithm.
def backtracking_search(
current_color_assignment: Optional[Dict[str, str]]=None
) -> Optional[Dict[str, str]]:
"""
Solve the constraint satisfaction problem by backtracking.
Notes
-----
The search is recursively executed until all allocations are completed.
Parameters
----------
current_color_assignment : dict or None, default None
Current allocation status to each block. Block name on the key,
A character string of color constants is set for each value.
* If None is specified, it will be initialized with an empty dictionary.
Returns
-------
current_color_assignment : dict or None
A dictionary that stores the allocation values when the constraints are cleared.
"""
if current_color_assignment is None:
current_color_assignment = {}
#If you have already allocated the number of variables
#Return the dictionary and stop the process.
if len(current_color_assignment) == len(VARIABLES):
return current_color_assignment
unassigned_variables: List[str] = get_unassigned_variables(
current_color_assignment=current_color_assignment)
first_variable: str = unassigned_variables[0]
for domain_value in DOMAINS:
copied_assignment: Dict[str, str] = current_color_assignment.copy()
copied_assignment[first_variable] = domain_value
if is_valid_assignment(assignment=copied_assignment):
#If the constraints are still met, a recursive search is performed.
#Try to allocate colors.
recursive_result_assignment: Optional[Dict[str, str]] = \
backtracking_search(
current_color_assignment=copied_assignment)
#If no valid allocation condition is found in the search results,
#Of the following values in the domain
if recursive_result_assignment is None:
continue
return recursive_result_assignment
return None
def is_valid_assignment(assignment: Dict[str, str]) -> bool:
"""
Whether the target color allocation status meets all the constraints
Get the boolean value.
Parameters
----------
assignment : dict
Allocation status to each block. The key is the block name and the value is the color
A constant character string is set for each.
Returns
-------
result_bool : bool
True is set if all the constraints are met.
"""
for constraint in CONSTRAINTS:
satisfied: bool = constraint.satisfied(
current_color_assignment=assignment)
if not satisfied:
return False
return True
def get_unassigned_variables(
current_color_assignment: Dict[str, str]) -> List[str]:
"""
Get a list of unassigned variable names.
Parameters
----------
current_color_assignment : dict or None, default None
Current allocation status to each block. Block name on the key,
A character string of color constants is set for each value.
Returns
-------
unassigned_variables : list of str
A list containing the names of unassigned elements (variables).
"""
unassigned_variables: List[str] = []
for block_name in VARIABLES:
if block_name in current_color_assignment:
continue
unassigned_variables.append(block_name)
return unassigned_variables
I will actually move it
Try backtracking and see the color allocation results.
if __name__ == '__main__':
assignment: Optional[Dict[str, str]] = backtracking_search()
print(assignment)
{'①': 'Red', '②': 'Green', '③': 'Blue', '④': 'Red', '⑤': 'Green'}
You can see that the four blocks at both ends are assigned red and green, and the middle block is assigned the blue block. For the time being, it seems that it worked without problems.
Whole final code
from typing import Dict, List, Optional
BLOCK_NAME_1: str = '①'
BLOCK_NAME_2: str = '②'
BLOCK_NAME_3: str = '③'
BLOCK_NAME_4: str = '④'
BLOCK_NAME_5: str = '⑤'
COLOR_RED: str = 'Red'
COLOR_GREEN: str = 'Green'
COLOR_BLUE: str = 'Blue'
class ColoringConstraint:
def __init__(self, block_name_1: str, block_name_2: str) -> None:
"""
A class that handles one constraint of block color setting.
Parameters
----------
block_name_1 : str
The name of the first block between adjacent blocks (① to ⑤).
block_name_2 : str
The name of the second block between adjacent blocks (①-⑤).
"""
self.block_name_1: str = block_name_1
self.block_name_2: str = block_name_2
def satisfied(self, current_color_assignment: Dict[str, str]) -> bool:
"""
The boolean value of whether the current allocation status meets this constraint
get.
Parameters
----------
current_color_assignment : dict
Current allocation status to each block. Block name on the key,
A character string of color constants is set for each value.
Returns
-------
result_bool : bool
True and satisfying the constraint condition. Check under the following conditions
Will be executed.
-If in the assigned dictionary the first block or the second
If the block has not been allocated yet (target block)
True is set if the color has not yet been set to.
-Set if two blocks have already been assigned colors
True if the colors are not the same, otherwise
False is set (each of two adjacent blocks
True if different colors are set in.
"""
block_1_color_assigned: bool = \
self.block_name_1 in current_color_assignment
block_2_color_assigned: bool = \
self.block_name_2 in current_color_assignment
if not block_1_color_assigned or not block_2_color_assigned:
return True
color_1: str = current_color_assignment[self.block_name_1]
color_2: str = current_color_assignment[self.block_name_2]
if color_1 != color_2:
return True
return False
VARIABLES: List[str] = [
BLOCK_NAME_1,
BLOCK_NAME_2,
BLOCK_NAME_3,
BLOCK_NAME_4,
BLOCK_NAME_5,
]
DOMAINS: List[str] = [
COLOR_RED,
COLOR_GREEN,
COLOR_BLUE,
]
CONSTRAINTS: List[ColoringConstraint] = [
ColoringConstraint(
block_name_1=BLOCK_NAME_1,
block_name_2=BLOCK_NAME_2),
ColoringConstraint(
block_name_1=BLOCK_NAME_1,
block_name_2=BLOCK_NAME_3),
ColoringConstraint(
block_name_1=BLOCK_NAME_2,
block_name_2=BLOCK_NAME_3),
ColoringConstraint(
block_name_1=BLOCK_NAME_3,
block_name_2=BLOCK_NAME_4),
ColoringConstraint(
block_name_1=BLOCK_NAME_3,
block_name_2=BLOCK_NAME_5),
ColoringConstraint(
block_name_1=BLOCK_NAME_4,
block_name_2=BLOCK_NAME_5),
]
def backtracking_search(
current_color_assignment: Optional[Dict[str, str]]=None
) -> Optional[Dict[str, str]]:
"""
Solve the constraint satisfaction problem by backtracking.
Notes
-----
The search is recursively executed until all allocations are completed.
Parameters
----------
current_color_assignment : dict or None, default None
Current allocation status to each block. Block name on the key,
A character string of color constants is set for each value.
* If None is specified, it will be initialized with an empty dictionary.
Returns
-------
current_color_assignment : dict or None
A dictionary that stores the allocation values when the constraints are cleared.
"""
if current_color_assignment is None:
current_color_assignment = {}
#If you have already allocated the number of variables
#Return the dictionary and stop the process.
if len(current_color_assignment) == len(VARIABLES):
return current_color_assignment
unassigned_variables: List[str] = get_unassigned_variables(
current_color_assignment=current_color_assignment)
first_variable: str = unassigned_variables[0]
for domain_value in DOMAINS:
copied_assignment: Dict[str, str] = current_color_assignment.copy()
copied_assignment[first_variable] = domain_value
if is_valid_assignment(assignment=copied_assignment):
#If the constraints are still met, a recursive search is performed.
#Try to allocate colors.
recursive_result_assignment: Optional[Dict[str, str]] = \
backtracking_search(
current_color_assignment=copied_assignment)
#If no valid allocation condition is found in the search results,
#Of the following values in the domain
if recursive_result_assignment is None:
continue
return recursive_result_assignment
return None
def is_valid_assignment(assignment: Dict[str, str]) -> bool:
"""
Whether the target color allocation status meets all the constraints
Get the boolean value.
Parameters
----------
assignment : dict
Allocation status to each block. The key is the block name and the value is the color
A constant character string is set for each.
Returns
-------
result_bool : bool
True is set if all the constraints are met.
"""
for constraint in CONSTRAINTS:
satisfied: bool = constraint.satisfied(
current_color_assignment=assignment)
if not satisfied:
return False
return True
def get_unassigned_variables(
current_color_assignment: Dict[str, str]) -> List[str]:
"""
Get a list of unassigned variable names.
Parameters
----------
current_color_assignment : dict or None, default None
Current allocation status to each block. Block name on the key,
A character string of color constants is set for each value.
Returns
-------
unassigned_variables : list of str
A list containing the names of unassigned elements (variables).
"""
unassigned_variables: List[str] = []
for block_name in VARIABLES:
if block_name in current_color_assignment:
continue
unassigned_variables.append(block_name)
return unassigned_variables
if __name__ == '__main__':
assignment: Optional[Dict[str, str]] = backtracking_search()
print(assignment)
Digression
――Because I was originally a graduate of a school in the design field, please forgive Masakari who has a strong knowledge of computer science.
References / Reference Site Summary
- Classic Computer Science Problems in Python -[Constraint Satisfiation Problem-Wikipedia](https://ja.wikipedia.org/wiki/%E5%88%B6%E7%B4%84%E5%85%85%E8%B6%B3%E5%95% 8F% E9% A1% 8C) -[Backtracking --Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AF%E3%83%88%E3%83%A9 % E3% 83% 83% E3% 82% AD% E3% 83% B3% E3% 82% B0)
Recommended Posts