backtrack search algorithm in python

README.md

Backtrack Searching in Python

This program basically uses backtrack searching to assign variables to domain values given a few sets of constraints. Its pretty straightforward. Modifications to the constraints can be made to experiment with this program. For the given sets we get the expected output:

{'A': 'Monday', 'B': 'Tuesday', 'C': 'Wednesday', 'D': 'Wednesday', 'E': 'Monday', 'F': 'Tuesday', 'G': 'Wednesday'}

Main.py

"""
    Naive backtrack searching without any heuristics or inference
"""

VARIABLES = ["A", "B", "C", "D", "E", "F", "G"]
DOMAIN_VALUES = ["Monday", "Tuesday", "Wednesday"]
CONSTRAINTS = [
    ("A", "B"),
    ("A", "C"),
    ("B", "C"),
    ("B", "D"),
    ("B", "E"),
    ("D", "E"),
    ("C", "E"),
    ("C", "F"),
    ("E", "F"),
    ("E", "G"),
    ("F", "G"),
]

def BACKTRACK(assignment):
    if len(assignment) == len(VARIABLES):
        return assignment
    
    var = SELECT_UNASSIGNED_VAR(assignment)

    for value in DOMAIN_VALUES:
        if consistent(var, value, assignment):
            assignment[var] = value
            result = BACKTRACK(assignment)
            if result is not None:
                return result
        
        if var in assignment:
            del assignment[var]

    return None
    
    
def SELECT_UNASSIGNED_VAR(assignment):
    for variable in VARIABLES:
        if variable not in assignment:
            return variable
    return None

def consistent(var, value, assignment):
    for (x, y) in CONSTRAINTS:
        if var == x and y in assignment and assignment[y] == value:
            return False
        if var == y and x in assignment and assignment[x] == value:
            return False
    return True


solution = BACKTRACK(dict())
print(solution)