{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# CONSTRAINT SATISFACTION PROBLEMS\n", "\n", "This IPy notebook acts as supporting material for topics covered in **Chapter 6 Constraint Satisfaction Problems** of the book* Artificial Intelligence: A Modern Approach*. We make use of the implementations in **csp.py** module. Even though this notebook includes a brief summary of the main topics, familiarity with the material present in the book is expected. We will look at some visualizations and solve some of the CSP problems described in the book. Let us import everything from the csp module to get started." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from csp import *\n", "from notebook import psource, pseudocode, plot_NQueens\n", "%matplotlib inline\n", "\n", "# Hide warnings in the matplotlib sections\n", "import warnings\n", "warnings.filterwarnings(\"ignore\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## CONTENTS\n", "\n", "* Overview\n", "* Graph Coloring\n", "* N-Queens\n", "* AC-3\n", "* Backtracking Search\n", "* Tree CSP Solver\n", "* Graph Coloring Visualization\n", "* N-Queens Visualization" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## OVERVIEW\n", "\n", "CSPs are a special kind of search problems. Here we don't treat the space as a black box but the state has a particular form and we use that to our advantage to tweak our algorithms to be more suited to the problems. A CSP State is defined by a set of variables which can take values from corresponding domains. These variables can take only certain values in their domains to satisfy the constraints. A set of assignments which satisfies all constraints passes the goal test. Let us start by exploring the CSP class which we will use to model our CSPs. You can keep the popup open and read the main page to get a better idea of the code." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "
\n", "class CSP(search.Problem):\n",
" """This class describes finite-domain Constraint Satisfaction Problems.\n",
" A CSP is specified by the following inputs:\n",
" variables A list of variables; each is atomic (e.g. int or string).\n",
" domains A dict of {var:[possible_value, ...]} entries.\n",
" neighbors A dict of {var:[var,...]} that for each variable lists\n",
" the other variables that participate in constraints.\n",
" constraints A function f(A, a, B, b) that returns true if neighbors\n",
" A, B satisfy the constraint when they have values A=a, B=b\n",
"\n",
" In the textbook and in most mathematical definitions, the\n",
" constraints are specified as explicit pairs of allowable values,\n",
" but the formulation here is easier to express and more compact for\n",
" most cases. (For example, the n-Queens problem can be represented\n",
" in O(n) space using this notation, instead of O(N^4) for the\n",
" explicit representation.) In terms of describing the CSP as a\n",
" problem, that's all there is.\n",
"\n",
" However, the class also supports data structures and methods that help you\n",
" solve CSPs by calling a search function on the CSP. Methods and slots are\n",
" as follows, where the argument 'a' represents an assignment, which is a\n",
" dict of {var:val} entries:\n",
" assign(var, val, a) Assign a[var] = val; do other bookkeeping\n",
" unassign(var, a) Do del a[var], plus other bookkeeping\n",
" nconflicts(var, val, a) Return the number of other variables that\n",
" conflict with var=val\n",
" curr_domains[var] Slot: remaining consistent values for var\n",
" Used by constraint propagation routines.\n",
" The following methods are used only by graph_search and tree_search:\n",
" actions(state) Return a list of actions\n",
" result(state, action) Return a successor of state\n",
" goal_test(state) Return true if all constraints satisfied\n",
" The following are just for debugging purposes:\n",
" nassigns Slot: tracks the number of assignments made\n",
" display(a) Print a human-readable representation\n",
" """\n",
"\n",
" def __init__(self, variables, domains, neighbors, constraints):\n",
" """Construct a CSP problem. If variables is empty, it becomes domains.keys()."""\n",
" variables = variables or list(domains.keys())\n",
"\n",
" self.variables = variables\n",
" self.domains = domains\n",
" self.neighbors = neighbors\n",
" self.constraints = constraints\n",
" self.initial = ()\n",
" self.curr_domains = None\n",
" self.nassigns = 0\n",
"\n",
" def assign(self, var, val, assignment):\n",
" """Add {var: val} to assignment; Discard the old value if any."""\n",
" assignment[var] = val\n",
" self.nassigns += 1\n",
"\n",
" def unassign(self, var, assignment):\n",
" """Remove {var: val} from assignment.\n",
" DO NOT call this if you are changing a variable to a new value;\n",
" just call assign for that."""\n",
" if var in assignment:\n",
" del assignment[var]\n",
"\n",
" def nconflicts(self, var, val, assignment):\n",
" """Return the number of conflicts var=val has with other variables."""\n",
" # Subclasses may implement this more efficiently\n",
" def conflict(var2):\n",
" return (var2 in assignment and\n",
" not self.constraints(var, val, var2, assignment[var2]))\n",
" return count(conflict(v) for v in self.neighbors[var])\n",
"\n",
" def display(self, assignment):\n",
" """Show a human-readable representation of the CSP."""\n",
" # Subclasses can print in a prettier way, or display with a GUI\n",
" print('CSP:', self, 'with assignment:', assignment)\n",
"\n",
" # These methods are for the tree and graph-search interface:\n",
"\n",
" def actions(self, state):\n",
" """Return a list of applicable actions: nonconflicting\n",
" assignments to an unassigned variable."""\n",
" if len(state) == len(self.variables):\n",
" return []\n",
" else:\n",
" assignment = dict(state)\n",
" var = first([v for v in self.variables if v not in assignment])\n",
" return [(var, val) for val in self.domains[var]\n",
" if self.nconflicts(var, val, assignment) == 0]\n",
"\n",
" def result(self, state, action):\n",
" """Perform an action and return the new state."""\n",
" (var, val) = action\n",
" return state + ((var, val),)\n",
"\n",
" def goal_test(self, state):\n",
" """The goal is to assign all variables, with all constraints satisfied."""\n",
" assignment = dict(state)\n",
" return (len(assignment) == len(self.variables)\n",
" and all(self.nconflicts(variables, assignment[variables], assignment) == 0\n",
" for variables in self.variables))\n",
"\n",
" # These are for constraint propagation\n",
"\n",
" def support_pruning(self):\n",
" """Make sure we can prune values from domains. (We want to pay\n",
" for this only if we use it.)"""\n",
" if self.curr_domains is None:\n",
" self.curr_domains = {v: list(self.domains[v]) for v in self.variables}\n",
"\n",
" def suppose(self, var, value):\n",
" """Start accumulating inferences from assuming var=value."""\n",
" self.support_pruning()\n",
" removals = [(var, a) for a in self.curr_domains[var] if a != value]\n",
" self.curr_domains[var] = [value]\n",
" return removals\n",
"\n",
" def prune(self, var, value, removals):\n",
" """Rule out var=value."""\n",
" self.curr_domains[var].remove(value)\n",
" if removals is not None:\n",
" removals.append((var, value))\n",
"\n",
" def choices(self, var):\n",
" """Return all values for var that aren't currently ruled out."""\n",
" return (self.curr_domains or self.domains)[var]\n",
"\n",
" def infer_assignment(self):\n",
" """Return the partial assignment implied by the current inferences."""\n",
" self.support_pruning()\n",
" return {v: self.curr_domains[v][0]\n",
" for v in self.variables if 1 == len(self.curr_domains[v])}\n",
"\n",
" def restore(self, removals):\n",
" """Undo a supposition and all inferences from it."""\n",
" for B, b in removals:\n",
" self.curr_domains[B].append(b)\n",
"\n",
" # This is for min_conflicts search\n",
"\n",
" def conflicted_vars(self, current):\n",
" """Return a list of variables in current assignment that are in conflict"""\n",
" return [var for var in self.variables\n",
" if self.nconflicts(var, current[var], current) > 0]\n",
"
def different_values_constraint(A, a, B, b):\n",
" """A constraint saying two neighboring variables must differ in value."""\n",
" return a != b\n",
"
def MapColoringCSP(colors, neighbors):\n",
" """Make a CSP for the problem of coloring a map with different colors\n",
" for any two adjacent regions. Arguments are a list of colors, and a\n",
" dict of {region: [neighbor,...]} entries. This dict may also be\n",
" specified as a string of the form defined by parse_neighbors."""\n",
" if isinstance(neighbors, str):\n",
" neighbors = parse_neighbors(neighbors)\n",
" return CSP(list(neighbors.keys()), UniversalDict(colors), neighbors,\n",
" different_values_constraint)\n",
"
def queen_constraint(A, a, B, b):\n",
" """Constraint is satisfied (true) if A, B are really the same variable,\n",
" or if they are not in the same row, down diagonal, or up diagonal."""\n",
" return A == B or (a != b and A + a != B + b and A - a != B - b)\n",
"
class NQueensCSP(CSP):\n",
" """Make a CSP for the nQueens problem for search with min_conflicts.\n",
" Suitable for large n, it uses only data structures of size O(n).\n",
" Think of placing queens one per column, from left to right.\n",
" That means position (x, y) represents (var, val) in the CSP.\n",
" The main structures are three arrays to count queens that could conflict:\n",
" rows[i] Number of queens in the ith row (i.e val == i)\n",
" downs[i] Number of queens in the \\ diagonal\n",
" such that their (x, y) coordinates sum to i\n",
" ups[i] Number of queens in the / diagonal\n",
" such that their (x, y) coordinates have x-y+n-1 = i\n",
" We increment/decrement these counts each time a queen is placed/moved from\n",
" a row/diagonal. So moving is O(1), as is nconflicts. But choosing\n",
" a variable, and a best value for the variable, are each O(n).\n",
" If you want, you can keep track of conflicted variables, then variable\n",
" selection will also be O(1).\n",
" >>> len(backtracking_search(NQueensCSP(8)))\n",
" 8\n",
" """\n",
"\n",
" def __init__(self, n):\n",
" """Initialize data structures for n Queens."""\n",
" CSP.__init__(self, list(range(n)), UniversalDict(list(range(n))),\n",
" UniversalDict(list(range(n))), queen_constraint)\n",
"\n",
" self.rows = [0]*n\n",
" self.ups = [0]*(2*n - 1)\n",
" self.downs = [0]*(2*n - 1)\n",
"\n",
" def nconflicts(self, var, val, assignment):\n",
" """The number of conflicts, as recorded with each assignment.\n",
" Count conflicts in row and in up, down diagonals. If there\n",
" is a queen there, it can't conflict with itself, so subtract 3."""\n",
" n = len(self.variables)\n",
" c = self.rows[val] + self.downs[var+val] + self.ups[var-val+n-1]\n",
" if assignment.get(var, None) == val:\n",
" c -= 3\n",
" return c\n",
"\n",
" def assign(self, var, val, assignment):\n",
" """Assign var, and keep track of conflicts."""\n",
" oldval = assignment.get(var, None)\n",
" if val != oldval:\n",
" if oldval is not None: # Remove old val if there was one\n",
" self.record_conflict(assignment, var, oldval, -1)\n",
" self.record_conflict(assignment, var, val, +1)\n",
" CSP.assign(self, var, val, assignment)\n",
"\n",
" def unassign(self, var, assignment):\n",
" """Remove var from assignment (if it is there) and track conflicts."""\n",
" if var in assignment:\n",
" self.record_conflict(assignment, var, assignment[var], -1)\n",
" CSP.unassign(self, var, assignment)\n",
"\n",
" def record_conflict(self, assignment, var, val, delta):\n",
" """Record conflicts caused by addition or deletion of a Queen."""\n",
" n = len(self.variables)\n",
" self.rows[val] += delta\n",
" self.downs[var + val] += delta\n",
" self.ups[var - val + n - 1] += delta\n",
"\n",
" def display(self, assignment):\n",
" """Print the queens and the nconflicts values (for debugging)."""\n",
" n = len(self.variables)\n",
" for val in range(n):\n",
" for var in range(n):\n",
" if assignment.get(var, '') == val:\n",
" ch = 'Q'\n",
" elif (var + val) % 2 == 0:\n",
" ch = '.'\n",
" else:\n",
" ch = '-'\n",
" print(ch, end=' ')\n",
" print(' ', end=' ')\n",
" for var in range(n):\n",
" if assignment.get(var, '') == val:\n",
" ch = '*'\n",
" else:\n",
" ch = ' '\n",
" print(str(self.nconflicts(var, val, assignment)) + ch, end=' ')\n",
" print()\n",
"
def min_conflicts(csp, max_steps=100000):\n",
" """Solve a CSP by stochastic hillclimbing on the number of conflicts."""\n",
" # Generate a complete assignment for all variables (probably with conflicts)\n",
" csp.current = current = {}\n",
" for var in csp.variables:\n",
" val = min_conflicts_value(csp, var, current)\n",
" csp.assign(var, val, current)\n",
" # Now repeatedly choose a random conflicted variable and change it\n",
" for i in range(max_steps):\n",
" conflicted = csp.conflicted_vars(current)\n",
" if not conflicted:\n",
" return current\n",
" var = random.choice(conflicted)\n",
" val = min_conflicts_value(csp, var, current)\n",
" csp.assign(var, val, current)\n",
" return None\n",
"
def AC3(csp, queue=None, removals=None):\n",
" """[Figure 6.3]"""\n",
" if queue is None:\n",
" queue = {(Xi, Xk) for Xi in csp.variables for Xk in csp.neighbors[Xi]}\n",
" csp.support_pruning()\n",
" while queue:\n",
" (Xi, Xj) = queue.pop()\n",
" if revise(csp, Xi, Xj, removals):\n",
" if not csp.curr_domains[Xi]:\n",
" return False\n",
" for Xk in csp.neighbors[Xi]:\n",
" if Xk != Xj:\n",
" queue.add((Xk, Xi))\n",
" return True\n",
"
def revise(csp, Xi, Xj, removals):\n",
" """Return true if we remove a value."""\n",
" revised = False\n",
" for x in csp.curr_domains[Xi][:]:\n",
" # If Xi=x conflicts with Xj=y for every possible y, eliminate Xi=x\n",
" if all(not csp.constraints(Xi, x, Xj, y) for y in csp.curr_domains[Xj]):\n",
" csp.prune(Xi, x, removals)\n",
" revised = True\n",
" return revised\n",
"
def mrv(assignment, csp):\n",
" """Minimum-remaining-values heuristic."""\n",
" return argmin_random_tie(\n",
" [v for v in csp.variables if v not in assignment],\n",
" key=lambda var: num_legal_values(csp, var, assignment))\n",
"
def num_legal_values(csp, var, assignment):\n",
" if csp.curr_domains:\n",
" return len(csp.curr_domains[var])\n",
" else:\n",
" return count(csp.nconflicts(var, val, assignment) == 0\n",
" for val in csp.domains[var])\n",
"
def nconflicts(self, var, val, assignment):\n",
" """Return the number of conflicts var=val has with other variables."""\n",
" # Subclasses may implement this more efficiently\n",
" def conflict(var2):\n",
" return (var2 in assignment and\n",
" not self.constraints(var, val, var2, assignment[var2]))\n",
" return count(conflict(v) for v in self.neighbors[var])\n",
"
def lcv(var, assignment, csp):\n",
" """Least-constraining-values heuristic."""\n",
" return sorted(csp.choices(var),\n",
" key=lambda val: csp.nconflicts(var, val, assignment))\n",
"
def tree_csp_solver(csp):\n",
" """[Figure 6.11]"""\n",
" assignment = {}\n",
" root = csp.variables[0]\n",
" X, parent = topological_sort(csp, root)\n",
"\n",
" csp.support_pruning()\n",
" for Xj in reversed(X[1:]):\n",
" if not make_arc_consistent(parent[Xj], Xj, csp):\n",
" return None\n",
"\n",
" assignment[root] = csp.curr_domains[root][0]\n",
" for Xi in X[1:]:\n",
" assignment[Xi] = assign_value(parent[Xi], Xi, csp, assignment)\n",
" if not assignment[Xi]:\n",
" return None\n",
" return assignment\n",
"
Failed to display Jupyter Widget of type interactive
.
\n", " If you're reading this message in the Jupyter Notebook or JupyterLab Notebook, it may mean\n", " that the widgets JavaScript is still loading. If this message persists, it\n", " likely means that the widgets JavaScript library is either not installed or\n", " not enabled. See the Jupyter\n", " Widgets Documentation for setup instructions.\n", "
\n", "\n", " If you're reading this message in another frontend (for example, a static\n", " rendering on GitHub or NBViewer),\n", " it may mean that your frontend doesn't currently support widgets.\n", "
\n" ], "text/plain": [ "interactive(children=(IntSlider(value=0, description='iteration', max=20), Output()), _dom_classes=('widget-interact',))" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "869965d6473f46d8bc62a32995091d1e", "version_major": 2, "version_minor": 0 }, "text/html": [ "Failed to display Jupyter Widget of type interactive
.
\n", " If you're reading this message in the Jupyter Notebook or JupyterLab Notebook, it may mean\n", " that the widgets JavaScript is still loading. If this message persists, it\n", " likely means that the widgets JavaScript library is either not installed or\n", " not enabled. See the Jupyter\n", " Widgets Documentation for setup instructions.\n", "
\n", "\n", " If you're reading this message in another frontend (for example, a static\n", " rendering on GitHub or NBViewer),\n", " it may mean that your frontend doesn't currently support widgets.\n", "
\n" ], "text/plain": [ "interactive(children=(ToggleButton(value=False, description='Visualize'), ToggleButtons(description='Extra Delay:', options=('0', '0.1', '0.2', '0.5', '0.7', '1.0'), value='0'), Output()), _dom_classes=('widget-interact',))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import ipywidgets as widgets\n", "from IPython.display import display\n", "\n", "iteration_slider = widgets.IntSlider(min=0, max=len(coloring_problem1.assignment_history)-1, step=1, value=0)\n", "w=widgets.interactive(step_func,iteration=iteration_slider)\n", "display(w)\n", "\n", "visualize_callback = make_visualize(iteration_slider)\n", "\n", "visualize_button = widgets.ToggleButton(description = \"Visualize\", value = False)\n", "time_select = widgets.ToggleButtons(description='Extra Delay:',options=['0', '0.1', '0.2', '0.5', '0.7', '1.0'])\n", "\n", "a = widgets.interactive(visualize_callback, Visualize = visualize_button, time_step=time_select)\n", "display(a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## N-QUEENS VISUALIZATION\n", "\n", "Just like the Graph Coloring Problem, we will start with defining a few helper functions to help us visualize the assignments as they evolve over time. The **make_plot_board_step_function** behaves similar to the **make_update_step_function** introduced earlier. It initializes a chess board in the form of a 2D grid with alternating 0s and 1s. This is used by **plot_board_step** function which draws the board using matplotlib and adds queens to it. This function also calls the **label_queen_conflicts** which modifies the grid placing a 3 in any position where there is a conflict." ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [], "source": [ "def label_queen_conflicts(assignment,grid):\n", " ''' Mark grid with queens that are under conflict. '''\n", " for col, row in assignment.items(): # check each queen for conflict\n", " conflicts = {temp_col:temp_row for temp_col,temp_row in assignment.items() \n", " if (temp_row == row and temp_col != col)\n", " or (temp_row+temp_col == row+col and temp_col != col)\n", " or (temp_row-temp_col == row-col and temp_col != col)}\n", " \n", " # Place a 3 in positions where this is a conflict\n", " for col, row in conflicts.items():\n", " grid[col][row] = 3\n", "\n", " return grid\n", "\n", "def make_plot_board_step_function(instru_csp):\n", " '''ipywidgets interactive function supports\n", " single parameter as input. This function\n", " creates and return such a function by taking\n", " in input other parameters.\n", " '''\n", " n = len(instru_csp.variables)\n", " \n", " \n", " def plot_board_step(iteration):\n", " ''' Add Queens to the Board.'''\n", " data = instru_csp.assignment_history[iteration]\n", " \n", " grid = [[(col+row+1)%2 for col in range(n)] for row in range(n)]\n", " grid = label_queen_conflicts(data, grid) # Update grid with conflict labels.\n", " \n", " # color map of fixed colors\n", " cmap = matplotlib.colors.ListedColormap(['white','lightsteelblue','red'])\n", " bounds=[0,1,2,3] # 0 for white 1 for black 2 onwards for conflict labels (red).\n", " norm = matplotlib.colors.BoundaryNorm(bounds, cmap.N)\n", " \n", " fig = plt.imshow(grid, interpolation='nearest', cmap = cmap,norm=norm)\n", "\n", " plt.axis('off')\n", " fig.axes.get_xaxis().set_visible(False)\n", " fig.axes.get_yaxis().set_visible(False)\n", "\n", " # Place the Queens Unicode Symbol\n", " for col, row in data.items():\n", " fig.axes.text(row, col, u\"\\u265B\", va='center', ha='center', family='Dejavu Sans', fontsize=32)\n", " plt.show()\n", " \n", " return plot_board_step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let us visualize a solution obtained via backtracking. We make use of the previosuly defined **make_instru** function for keeping a history of steps." ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [], "source": [ "twelve_queens_csp = NQueensCSP(12)\n", "backtracking_instru_queen = make_instru(twelve_queens_csp)\n", "result = backtracking_search(backtracking_instru_queen)" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [], "source": [ "backtrack_queen_step = make_plot_board_step_function(backtracking_instru_queen) # Step Function for Widgets" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now finally we set some matplotlib parameters to adjust how our plot will look like. The font is necessary because the Black Queen Unicode character is not a part of all fonts. You can move the slider to experiment and observe how the queens are assigned. It is also possible to move the slider using arrow keys or to jump to the value by directly editing the number with a double click. The **Visualize Button** will automatically animate the slider for you. The **Extra Delay Box** allows you to set time delay in seconds of upto one second for each time step." ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "c634be8e964042ff8f6e0696dca7968d", "version_major": 2, "version_minor": 0 }, "text/html": [ "Failed to display Jupyter Widget of type interactive
.
\n", " If you're reading this message in the Jupyter Notebook or JupyterLab Notebook, it may mean\n", " that the widgets JavaScript is still loading. If this message persists, it\n", " likely means that the widgets JavaScript library is either not installed or\n", " not enabled. See the Jupyter\n", " Widgets Documentation for setup instructions.\n", "
\n", "\n", " If you're reading this message in another frontend (for example, a static\n", " rendering on GitHub or NBViewer),\n", " it may mean that your frontend doesn't currently support widgets.\n", "
\n" ], "text/plain": [ "interactive(children=(IntSlider(value=0, description='iteration', max=473, step=0), Output()), _dom_classes=('widget-interact',))" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "c1fa4f8e573f4c44a648f6ad24a04eb1", "version_major": 2, "version_minor": 0 }, "text/html": [ "Failed to display Jupyter Widget of type interactive
.
\n", " If you're reading this message in the Jupyter Notebook or JupyterLab Notebook, it may mean\n", " that the widgets JavaScript is still loading. If this message persists, it\n", " likely means that the widgets JavaScript library is either not installed or\n", " not enabled. See the Jupyter\n", " Widgets Documentation for setup instructions.\n", "
\n", "\n", " If you're reading this message in another frontend (for example, a static\n", " rendering on GitHub or NBViewer),\n", " it may mean that your frontend doesn't currently support widgets.\n", "
\n" ], "text/plain": [ "interactive(children=(ToggleButton(value=False, description='Visualize'), ToggleButtons(description='Extra Delay:', options=('0', '0.1', '0.2', '0.5', '0.7', '1.0'), value='0'), Output()), _dom_classes=('widget-interact',))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "matplotlib.rcParams['figure.figsize'] = (8.0, 8.0)\n", "matplotlib.rcParams['font.family'].append(u'Dejavu Sans')\n", "\n", "iteration_slider = widgets.IntSlider(min=0, max=len(backtracking_instru_queen.assignment_history)-1, step=0, value=0)\n", "w=widgets.interactive(backtrack_queen_step,iteration=iteration_slider)\n", "display(w)\n", "\n", "visualize_callback = make_visualize(iteration_slider)\n", "\n", "visualize_button = widgets.ToggleButton(description = \"Visualize\", value = False)\n", "time_select = widgets.ToggleButtons(description='Extra Delay:',options=['0', '0.1', '0.2', '0.5', '0.7', '1.0'])\n", "\n", "a = widgets.interactive(visualize_callback, Visualize = visualize_button, time_step=time_select)\n", "display(a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let us finally repeat the above steps for **min_conflicts** solution." ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [], "source": [ "conflicts_instru_queen = make_instru(twelve_queens_csp)\n", "result = min_conflicts(conflicts_instru_queen)" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [], "source": [ "conflicts_step = make_plot_board_step_function(conflicts_instru_queen)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This visualization has same features as the one above; however, this one also highlights the conflicts by labeling the conflicted queens with a red background." ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "4174e28bef63440391eb2048d4851e8a", "version_major": 2, "version_minor": 0 }, "text/html": [ "Failed to display Jupyter Widget of type interactive
.
\n", " If you're reading this message in the Jupyter Notebook or JupyterLab Notebook, it may mean\n", " that the widgets JavaScript is still loading. If this message persists, it\n", " likely means that the widgets JavaScript library is either not installed or\n", " not enabled. See the Jupyter\n", " Widgets Documentation for setup instructions.\n", "
\n", "\n", " If you're reading this message in another frontend (for example, a static\n", " rendering on GitHub or NBViewer),\n", " it may mean that your frontend doesn't currently support widgets.\n", "
\n" ], "text/plain": [ "interactive(children=(IntSlider(value=0, description='iteration', max=66, step=0), Output()), _dom_classes=('widget-interact',))" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "f56863b054214f3b94e35693f9e11d0c", "version_major": 2, "version_minor": 0 }, "text/html": [ "Failed to display Jupyter Widget of type interactive
.
\n", " If you're reading this message in the Jupyter Notebook or JupyterLab Notebook, it may mean\n", " that the widgets JavaScript is still loading. If this message persists, it\n", " likely means that the widgets JavaScript library is either not installed or\n", " not enabled. See the Jupyter\n", " Widgets Documentation for setup instructions.\n", "
\n", "\n", " If you're reading this message in another frontend (for example, a static\n", " rendering on GitHub or NBViewer),\n", " it may mean that your frontend doesn't currently support widgets.\n", "
\n" ], "text/plain": [ "interactive(children=(ToggleButton(value=False, description='Visualize'), ToggleButtons(description='Extra Delay:', options=('0', '0.1', '0.2', '0.5', '0.7', '1.0'), value='0'), Output()), _dom_classes=('widget-interact',))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "iteration_slider = widgets.IntSlider(min=0, max=len(conflicts_instru_queen.assignment_history)-1, step=0, value=0)\n", "w=widgets.interactive(conflicts_step,iteration=iteration_slider)\n", "display(w)\n", "\n", "visualize_callback = make_visualize(iteration_slider)\n", "\n", "visualize_button = widgets.ToggleButton(description = \"Visualize\", value = False)\n", "time_select = widgets.ToggleButtons(description='Extra Delay:',options=['0', '0.1', '0.2', '0.5', '0.7', '1.0'])\n", "\n", "a = widgets.interactive(visualize_callback, Visualize = visualize_button, time_step=time_select)\n", "display(a)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.5" } }, "nbformat": 4, "nbformat_minor": 1 }