# CSP Notes * Three elements of a CSP solution: * The CSP model. * The search algorithm. * The heuristics. * A single CSP can have many possible models. Some models can be easier to solve than others. And an algorithm or strategy for one may not work for another. There is a paper that says that for crossword-filling, the choice of model, algorithm, and heuristics are mutually dependent, if you want the most efficient solution possible. * Can model constraints by using a **constraint graph**. * Nodes = variabes. * Edge = a constraint between two variables. * Simplest algorithm for solving a CSP is **depth-first search**. * The tree: Each non-root node is a choice for a variable, and each level contains all the possible choices for a given variable. * Using DFS, we have to get to the leaf nodes (solution candidates), before verifying if the solution is valid or not. * Instead, we want to backtrack early, if we detect that a constraint has been violated. * How to improve DFS? By adding backtracking. * The **Backtracking algorithm** is the standard algorithm for solving CSPs: 1. Pick a variable $V_1$ to start with. 1. Pick a possible value for $V_1$. 1. Pick a variable $V_2$, which is a "neighbour" of $V_1$. 1. Pick a possible value for $V_2$. * If it satisfies all constraints, then continue recursively, by picking $V_3$, a neighbour of $V_2$, etc. * If it fails any constraint, then we *backtrack* and try another possible value for $V_2$. 1. If no value worked for $V_2$, then we backtrack and try another possible value for $V_1$. * How do you decide in what order to choose the variables, and in what order to try the possible values for each variable? With **heuristics**. A good heuristic can reduce the time it takes to find a solution. * Examples of two heuristics: * Order of variables = longest clues first, since longest ones are hardest to fill. * Order of values to try = words with most vowels first, since words with vowels are more less likely to constrain the intersecting clues. * Generally, the goal is to find a single solution to the CSP. But you can easily modify the algorithm to keep going and find more or all (if possible) solutions. * There are some CSP solving algorithms that are not backtracking, like local search and hill-climbing search. But backtracking is the standard one that is used. * How to improve baktracking algorithm? By adding a **filtering algorithm**. These algorithms run inside of the backtracking algorithm. They prune bad domain values ahead-of-time, so that the backtracking algorithm doesn't have to check them in the usual way. (Seems like it's doing the same thing, so I guess it must just be an efficiency thing?) * Most filtering algorithms aim for **arc consistency**. An arc between two variables $V_1$ and $V_2$ is consistent, if: for every values in the domain of $V_1$, there is a value in the domain of $V_2$ that satisfies every constraint. * Filtering algorithms enforce arc consistency by removing the bad values from a variable's domain---ones fail some constraint, no matter what value you choose for the other variable. * Two common filtering algorithms, which are both called **lookahead** algorithms: * **Forward checking:** Enforce arc consistency between a single variable and its neighbours. "Neighbours" means the variables that it shares a constraint with. In the constraint graph, these are the nodes that the variable is connected to. * **AC-3:** Enforce arc consistency between a single variable and its neighbours. Then, repeat this process for any variables whose domain was reduced. This is essentially a recursive version of forward checking that results in every variable being arc consistent. * Our "lookahead" word suggestion algorithm uses forward checking. Because "lookahead" is a more general term, it would be more precise to call our algorithm a "forward checking" word suggestion algorithm. (But that is a mouthful.) ### New resources * [UofT lecture slides](https://www.cs.toronto.edu/~fbacchus/csc384/Lectures/csc384-Lecture03-BacktrackingSearch.pdf) * [CMU course notes](https://www.cs.cmu.edu/~15281/coursenotes/constraints/index.html) * [Berkley textbook](https://inst.eecs.berkeley.edu/~cs188/textbook/csp/csps.html)