arc_consistency


4.4 Consistency Algorithms

About

A more advanced technique for solving Constraint Satisfaction Problems (CSPs) is to use arc consistency to prune domains first. In the best case, this will find a unique solution; otherwise, we can perform domain splitting or use search on the simpler problem.

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)

You can click on an inconsistent arc to make it consistent, or click buttons such as "Step" to randomly select an arc to make consistent. After all arcs are consistent, you can click on a variable with more than one value in its domain to split it.


In [ ]:
from aipython.cspConsistency import Con_solver

con_solver = Con_solver(csp=csp_simple1)

# Visualization options
# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options
con_solver.sleep_time = 0.2 # The time, in seconds, between each step in auto solving
con_solver.line_width = 2.0 # The thickness of edges
con_solver.text_size = 13 # The fontsize of the text
con_solver.detail_level = 2 # 0=no text, 1=truncated text, 2=full text

# Display the widget
display(con_solver)
con_solver.solve_one()

In [ ]: