We can already solve CSPs by using the search methods we learnt before. The search space is partial assignments to the variables in the CSP.
For example, imagine a CSP with two variables, A and B, and domains both \{1,2,3\}. We start with the root node, {}, and fill in its children at the first level: {A:1}, {A:2}, and {A:3}. Then each of those nodes have several children, merging its own values with the values of the next variable. For example, the children of {A:1} are {A:1, B:1}, {A:1, B:2}, and {A:1, B:3}. For the sake of simplicity, in the second level we will just show {B:1}, {B:2}, and {B:3} but the user can figure out the assignment of variable A by tracking the node's parent. The tree goes deeper and deeper in this manner.
Because we are interested in whether there is a solution, rather than the path to the solution (notice that all solutions have the same length), and because the search space is acyclic, we can use depth-first search (with branch-and-bound technique to improve the performance). As an optimization, before generating the neighboring nodes, we check if those nodes satisfy the constraints; if not, there is no point in going on further, as it will never lead to a solution.
In order to use search algorithms on our CSP, we must first convert it into a search problem by using the class Search_from_CSP.
You can run each cell by selecting it and pressing Ctrl+Enter in Windows or Shift+Return in MacOS. Alternatively, you can click the Play button in the toolbar, to the left of the stop button. For more information, check out our AISpace2 Tutorial.
Feel free to modify our codes either in this notebook or somewhere outside (e.g. python files in /aipython/). If you want to modify our codes outside, you might find this helpful for how your changes can take effect.
You need to run the following command to import our pre-defined problems.
In [ ]:
# Run this to import pre-defined problems
from aipython.cspProblem import csp_simple1, csp_simple2, csp_simple3, csp_extended1, csp_extended2, csp_extended3, csp_crossword1, csp_crossword2, csp_crossword3, csp_crossword2d, csp_five_queens, csp_eight_queens
You can also define your own problems (how?).
You need to run the following command to import utilities that support your self-defined problems.
In [ ]:
# Run this to import utilities that support self-defined problems
from aipython.cspProblem import (AND, CSP, FALSE, IMPLIES, NOT, OR, TRUE, XOR,
Constraint, Equals, GreaterThan, IsFalse,
IsTrue, LessThan, meet_at)
In [ ]:
from aipython.searchBranchAndBound import DF_branch_and_bound
from aipython.cspSearch import Search_from_CSP
search_csp = DF_branch_and_bound(problem=Search_from_CSP(csp=csp_simple1))
# Visualization options
# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options
search_csp.sleep_time = 0.2 # The time, in seconds, between each step in auto solving
search_csp.line_width = 2.0 # The thickness of edges
search_csp.text_size = 13 # The fontsize of the text
search_csp.detail_level = 2 # 0=no text, 1=truncated text, 2=full text
search_csp.show_edge_costs = False
# Display the widget
display(search_csp)
search_csp.search()
In [ ]: