<jupyter_start><jupyter_text>CSC 421 - Constraint Satisfaction Problems Instructor: <NAME>  Problems can be solved by searching the state space. The state space is a representation of a problem where the nodes are states and the edges between them are actions. Domain-specific heuristics can be used to estimate the cost of reaching the goakl from a given state to make searching for solutions more efficient. The state representation is treated as a black box. **Constraint Satisfaction Problems** are a specific type of problem in which the state representation is **factored**. The state in such problems can be represented as a set of **variables** each of which has a **value** from a particular **domain**. A problem is solved when each varaible has a value that satisfies all the constrains that involve that variable.  Defining a CSP problem: * X is a set of variables {X1, X2, .. XN} * D is a set of domains {D1, ...., Dn} (one for each variable) * C is a set of constraints that specify allowable combinations of values Any contraint can be represented as an explicit set of tuples of values that satisfy the constraint or as a membership function (typically syntactic sugar). For example X1 and X2 with domain {1,2,3}. X1>X2 can be written as {(3,1),(3,2),(2,1)} A **consistent** assignment is an assignment of values to variables that does not violate any constraints. A **complete** assignment is an assignment of values to all variables. A **complete** and **consistent** assignment is called a **solution** to the CSP problem. A **partial** assignment is one that leaves some variables unassigned, and a **partial solution** is a partial assignment that is consistent. Solving a **CSP** problem is an NP-complete problem in general.   Classic example - map coloring   SA != WA Full enumeration {(SA,WA): (red, green), (red, blue), (green, red), (green,blue), (blue, red), (blue, green)}Many possible solutions. For example: {WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=red}  In CSP we can leverage information during search: * Partial assignment violates a constraint we can immediately discard further refinements of the partial assignment * We can see which variable violate a constraint and focus attention on the variables that matter   Historical Sidenote 1 The 4-color conjecture states that any planar graph can be colored with four or fewer colors. A planar graph is a graph that can be drawn on a place without the edges crossing each other. Probably first made by <NAME>, student of De Morgan in 1852. Despite efforts first proof in 1977 by Appel and Haken (with computer aid). This is a historic proof because it was the first widely accepted proof that was made by a computer system.   Historical Sidenote 2 CSP algorithms were used in SketchPad by <NAME> in 1963. Forerunner of pointer/display interaction, CAD, etc.   Generating rhythmic exercises at different levels of difficulty Joint work with <NAME>, <NAME>, and <NAME><jupyter_code># Recursive backtracking - start with an initial assignment (usually empty) and then select a variable and 
# assign it a value. If the current assignment is consistent with the constraints call recursively 


def recursive_backtracking(assignment, csp):
    if isComplete(assignment):
        return assignment
    var = select_unassigned_variable(csp["VARIABLES"], assignment)
    for value in csp["DOMAINS"]:
        assignment[var] = value
        if is_consistent(assignment, csp["CONSTRAINTS"]):
            result = recursive_backtracking(assignment, csp)
            if result != "FAILURE":
                return result
        assignment[var] = None
    return "FAILURE"<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.06834825061025224, 'fraction_numerical': 0.009221589368049905, 'mean_word_length': 4.423529411764706, 'pattern_counts': {'":': 1, '<': 11, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '349878', 'license': 'CC0-1.0', 'n_tokens_mistral': 947, 'n_tokens_neox': 890, 'n_words': 522, 'path': 'csc421_tzanetakis_csp.ipynb', 'repo_name': 'oscarsandford/csc421_tzanetakis', 'size': '3744'}