csp.ipynb

{
 "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": {
    "collapsed": true
   },
   "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",
    "* 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": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "psource(CSP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The __ _ _init_ _ __ method parameters specify the CSP. Variable can be passed as a list of strings or integers. Domains are passed as dict where key specify the variables and value specify the domains. The variables are passed as an empty list. Variables are extracted from the keys of the domain dictionary. Neighbor is a dict of variables that essentially describes the constraint graph. Here each variable key has a list its value which are the variables that are constraint along with it. The constraint parameter should be a function **f(A, a, B, b**) that **returns true** if neighbors A, B **satisfy the constraint** when they have values **A=a, B=b**. We have additional parameters like nassings which is incremented each time an assignment is made when calling the assign method. You can read more about the methods and parameters in the class doc string. We will talk more about them as we encounter their use. Let us jump to an example."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## GRAPH COLORING\n",
    "\n",
    "We use the graph coloring problem as our running example for demonstrating the different algorithms in the **csp module**. The idea of map coloring problem is that the adjacent nodes (those connected by edges) should not have the same color throughout the graph. The graph can be colored using a fixed number of colors. Here each node is a variable and the values are the colors that can be assigned to them. Given that the domain will be the same for all our nodes we use a custom dict defined by the **UniversalDict** class. The **UniversalDict** Class takes in a parameter which it returns as value for all the keys of the dict. It is very similar to **defaultdict** in Python except that it does not support item assignment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['R', 'G', 'B']"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = UniversalDict(['R','G','B'])\n",
    "s[5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For our CSP we also need to define a constraint function **f(A, a, B, b)**. In this what we need is that the neighbors must not have the same color. This is defined in the function **different_values_constraint** of the module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "psource(different_values_constraint)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The CSP class takes neighbors in the form of a Dict. The module specifies a simple helper function named **parse_neighbors** which allows us to take input in the form of strings and return a Dict of a form compatible with the **CSP Class**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%pdoc parse_neighbors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **MapColoringCSP** function creates and returns a CSP with the above constraint function and states. The variables are the keys of the neighbors dict and the constraint is the one specified by the **different_values_constratint** function. **australia**, **usa** and **france** are three CSPs that have been created using **MapColoringCSP**. **australia** corresponds to ** Figure 6.1 ** in the book."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "psource(MapColoringCSP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(<csp.CSP at 0x22a22ebc9e8>,\n",
       " <csp.CSP at 0x22a230355f8>,\n",
       " <csp.CSP at 0x22a23036b00>)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "australia, usa, france"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## N-QUEENS\n",
    "\n",
    "The N-queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Here N is a natural number. Like the graph coloring problem, NQueens is also implemented in the csp module. The **NQueensCSP** class inherits from the **CSP** class. It makes some modifications in the methods to suit the particular problem. The queens are assumed to be placed one per column, from left to right. That means position (x, y) represents (var, val) in the CSP. The constraint that needs to be passed on the CSP is defined in the **queen_constraint** function. The constraint is satisfied (true) if A, B are really the same variable, or if they are not in the same row, down diagonal, or up diagonal. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
       "span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
       "pre { line-height: 125%; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body  { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">queen_constraint</span><span class=\"p\">(</span><span class=\"n\">A</span><span class=\"p\">,</span> <span class=\"n\">a</span><span class=\"p\">,</span> <span class=\"n\">B</span><span class=\"p\">,</span> <span class=\"n\">b</span><span class=\"p\">):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;Constraint is satisfied (true) if A, B are really the same variable,</span>\n",
       "<span class=\"sd\">    or if they are not in the same row, down diagonal, or up diagonal.&quot;&quot;&quot;</span>\n",
       "    <span class=\"k\">return</span> <span class=\"n\">A</span> <span class=\"o\">==</span> <span class=\"n\">B</span> <span class=\"ow\">or</span> <span class=\"p\">(</span><span class=\"n\">a</span> <span class=\"o\">!=</span> <span class=\"n\">b</span> <span class=\"ow\">and</span> <span class=\"n\">A</span> <span class=\"o\">+</span> <span class=\"n\">a</span> <span class=\"o\">!=</span> <span class=\"n\">B</span> <span class=\"o\">+</span> <span class=\"n\">b</span> <span class=\"ow\">and</span> <span class=\"n\">A</span> <span class=\"o\">-</span> <span class=\"n\">a</span> <span class=\"o\">!=</span> <span class=\"n\">B</span> <span class=\"o\">-</span> <span class=\"n\">b</span><span class=\"p\">)</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(queen_constraint)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **NQueensCSP** method implements methods that support solving the problem via **min_conflicts** which is one of the techniques for solving CSPs. Because **min_conflicts** hill climbs the number of conflicts to solve, the CSP **assign** and **unassign** are modified to record conflicts. More details about the structures **rows**, **downs**, **ups** which help in recording conflicts are explained in the docstring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
       "span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
       "pre { line-height: 125%; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body  { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">NQueensCSP</span><span class=\"p\">(</span><span class=\"n\">CSP</span><span class=\"p\">):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;Make a CSP for the nQueens problem for search with min_conflicts.</span>\n",
       "<span class=\"sd\">    Suitable for large n, it uses only data structures of size O(n).</span>\n",
       "<span class=\"sd\">    Think of placing queens one per column, from left to right.</span>\n",
       "<span class=\"sd\">    That means position (x, y) represents (var, val) in the CSP.</span>\n",
       "<span class=\"sd\">    The main structures are three arrays to count queens that could conflict:</span>\n",
       "<span class=\"sd\">        rows[i]      Number of queens in the ith row (i.e val == i)</span>\n",
       "<span class=\"sd\">        downs[i]     Number of queens in the \\ diagonal</span>\n",
       "<span class=\"sd\">                     such that their (x, y) coordinates sum to i</span>\n",
       "<span class=\"sd\">        ups[i]       Number of queens in the / diagonal</span>\n",
       "<span class=\"sd\">                     such that their (x, y) coordinates have x-y+n-1 = i</span>\n",
       "<span class=\"sd\">    We increment/decrement these counts each time a queen is placed/moved from</span>\n",
       "<span class=\"sd\">    a row/diagonal. So moving is O(1), as is nconflicts.  But choosing</span>\n",
       "<span class=\"sd\">    a variable, and a best value for the variable, are each O(n).</span>\n",
       "<span class=\"sd\">    If you want, you can keep track of conflicted variables, then variable</span>\n",
       "<span class=\"sd\">    selection will also be O(1).</span>\n",
       "<span class=\"sd\">    &gt;&gt;&gt; len(backtracking_search(NQueensCSP(8)))</span>\n",
       "<span class=\"sd\">    8</span>\n",
       "<span class=\"sd\">    &quot;&quot;&quot;</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">n</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Initialize data structures for n Queens.&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">CSP</span><span class=\"o\">.</span><span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">)),</span> <span class=\"n\">UniversalDict</span><span class=\"p\">(</span><span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">))),</span>\n",
       "                     <span class=\"n\">UniversalDict</span><span class=\"p\">(</span><span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">))),</span> <span class=\"n\">queen_constraint</span><span class=\"p\">)</span>\n",
       "\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">rows</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span><span class=\"o\">*</span><span class=\"n\">n</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">ups</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span><span class=\"o\">*</span><span class=\"p\">(</span><span class=\"mi\">2</span><span class=\"o\">*</span><span class=\"n\">n</span> <span class=\"o\">-</span> <span class=\"mi\">1</span><span class=\"p\">)</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">downs</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span><span class=\"o\">*</span><span class=\"p\">(</span><span class=\"mi\">2</span><span class=\"o\">*</span><span class=\"n\">n</span> <span class=\"o\">-</span> <span class=\"mi\">1</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">nconflicts</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;The number of conflicts, as recorded with each assignment.</span>\n",
       "<span class=\"sd\">        Count conflicts in row and in up, down diagonals. If there</span>\n",
       "<span class=\"sd\">        is a queen there, it can&#39;t conflict with itself, so subtract 3.&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">n</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">variables</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">c</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">rows</span><span class=\"p\">[</span><span class=\"n\">val</span><span class=\"p\">]</span> <span class=\"o\">+</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">downs</span><span class=\"p\">[</span><span class=\"n\">var</span><span class=\"o\">+</span><span class=\"n\">val</span><span class=\"p\">]</span> <span class=\"o\">+</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">ups</span><span class=\"p\">[</span><span class=\"n\">var</span><span class=\"o\">-</span><span class=\"n\">val</span><span class=\"o\">+</span><span class=\"n\">n</span><span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">]</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">assignment</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"bp\">None</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"n\">val</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">c</span> <span class=\"o\">-=</span> <span class=\"mi\">3</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">c</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">assign</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Assign var, and keep track of conflicts.&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">oldval</span> <span class=\"o\">=</span> <span class=\"n\">assignment</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"bp\">None</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">val</span> <span class=\"o\">!=</span> <span class=\"n\">oldval</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">if</span> <span class=\"n\">oldval</span> <span class=\"ow\">is</span> <span class=\"ow\">not</span> <span class=\"bp\">None</span><span class=\"p\">:</span>  <span class=\"c1\"># Remove old val if there was one</span>\n",
       "                <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">record_conflict</span><span class=\"p\">(</span><span class=\"n\">assignment</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">oldval</span><span class=\"p\">,</span> <span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">)</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">record_conflict</span><span class=\"p\">(</span><span class=\"n\">assignment</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"o\">+</span><span class=\"mi\">1</span><span class=\"p\">)</span>\n",
       "            <span class=\"n\">CSP</span><span class=\"o\">.</span><span class=\"n\">assign</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">unassign</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Remove var from assignment (if it is there) and track conflicts.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">var</span> <span class=\"ow\">in</span> <span class=\"n\">assignment</span><span class=\"p\">:</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">record_conflict</span><span class=\"p\">(</span><span class=\"n\">assignment</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">[</span><span class=\"n\">var</span><span class=\"p\">],</span> <span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">CSP</span><span class=\"o\">.</span><span class=\"n\">unassign</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">record_conflict</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">delta</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Record conflicts caused by addition or deletion of a Queen.&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">n</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">variables</span><span class=\"p\">)</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">rows</span><span class=\"p\">[</span><span class=\"n\">val</span><span class=\"p\">]</span> <span class=\"o\">+=</span> <span class=\"n\">delta</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">downs</span><span class=\"p\">[</span><span class=\"n\">var</span> <span class=\"o\">+</span> <span class=\"n\">val</span><span class=\"p\">]</span> <span class=\"o\">+=</span> <span class=\"n\">delta</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">ups</span><span class=\"p\">[</span><span class=\"n\">var</span> <span class=\"o\">-</span> <span class=\"n\">val</span> <span class=\"o\">+</span> <span class=\"n\">n</span> <span class=\"o\">-</span> <span class=\"mi\">1</span><span class=\"p\">]</span> <span class=\"o\">+=</span> <span class=\"n\">delta</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">display</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Print the queens and the nconflicts values (for debugging).&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">n</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">variables</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">val</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">):</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">var</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">):</span>\n",
       "                <span class=\"k\">if</span> <span class=\"n\">assignment</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"s1\">&#39;&#39;</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"n\">val</span><span class=\"p\">:</span>\n",
       "                    <span class=\"n\">ch</span> <span class=\"o\">=</span> <span class=\"s1\">&#39;Q&#39;</span>\n",
       "                <span class=\"k\">elif</span> <span class=\"p\">(</span><span class=\"n\">var</span> <span class=\"o\">+</span> <span class=\"n\">val</span><span class=\"p\">)</span> <span class=\"o\">%</span> <span class=\"mi\">2</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "                    <span class=\"n\">ch</span> <span class=\"o\">=</span> <span class=\"s1\">&#39;.&#39;</span>\n",
       "                <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                    <span class=\"n\">ch</span> <span class=\"o\">=</span> <span class=\"s1\">&#39;-&#39;</span>\n",
       "                <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">ch</span><span class=\"p\">,</span> <span class=\"n\">end</span><span class=\"o\">=</span><span class=\"s1\">&#39; &#39;</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">&#39;    &#39;</span><span class=\"p\">,</span> <span class=\"n\">end</span><span class=\"o\">=</span><span class=\"s1\">&#39; &#39;</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">var</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">):</span>\n",
       "                <span class=\"k\">if</span> <span class=\"n\">assignment</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"s1\">&#39;&#39;</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"n\">val</span><span class=\"p\">:</span>\n",
       "                    <span class=\"n\">ch</span> <span class=\"o\">=</span> <span class=\"s1\">&#39;*&#39;</span>\n",
       "                <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                    <span class=\"n\">ch</span> <span class=\"o\">=</span> <span class=\"s1\">&#39; &#39;</span>\n",
       "                <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">nconflicts</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">))</span> <span class=\"o\">+</span> <span class=\"n\">ch</span><span class=\"p\">,</span> <span class=\"n\">end</span><span class=\"o\">=</span><span class=\"s1\">&#39; &#39;</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">print</span><span class=\"p\">()</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(NQueensCSP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The _ ___init___ _ method takes only one parameter **n** the size of the problem. To create an instance we just pass the required n into the constructor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "eight_queens = NQueensCSP(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have defined our CSP. \n",
    "We now need to solve this.\n",
    "\n",
    "### Min-conflicts\n",
    "As stated above, the `min_conflicts` algorithm is an efficient method to solve such a problem.\n",
    "<br>\n",
    "To begin with, all the variables of the CSP are _randomly_ initialized. \n",
    "<br>\n",
    "The algorithm then randomly selects a variable that has conflicts and violates some constraints of the CSP.\n",
    "<br>\n",
    "The selected variable is then assigned a value that _minimizes_ the number of conflicts.\n",
    "<br>\n",
    "This is a simple stochastic algorithm which works on a principle similar to **Hill-climbing**.\n",
    "The conflicting state is repeatedly changed into a state with fewer conflicts in an attempt to reach an approximate solution.\n",
    "<br>\n",
    "This algorithm sometimes benefits from having a good initial assignment.\n",
    "Using greedy techniques to get a good initial assignment and then using `min_conflicts` to solve the CSP can speed up the procedure dramatically, especially for CSPs with a large state space."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
       "span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
       "pre { line-height: 125%; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body  { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">min_conflicts</span><span class=\"p\">(</span><span class=\"n\">csp</span><span class=\"p\">,</span> <span class=\"n\">max_steps</span><span class=\"o\">=</span><span class=\"mi\">100000</span><span class=\"p\">):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;Solve a CSP by stochastic hillclimbing on the number of conflicts.&quot;&quot;&quot;</span>\n",
       "    <span class=\"c1\"># Generate a complete assignment for all variables (probably with conflicts)</span>\n",
       "    <span class=\"n\">csp</span><span class=\"o\">.</span><span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"p\">{}</span>\n",
       "    <span class=\"k\">for</span> <span class=\"n\">var</span> <span class=\"ow\">in</span> <span class=\"n\">csp</span><span class=\"o\">.</span><span class=\"n\">variables</span><span class=\"p\">:</span>\n",
       "        <span class=\"n\">val</span> <span class=\"o\">=</span> <span class=\"n\">min_conflicts_value</span><span class=\"p\">(</span><span class=\"n\">csp</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">current</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">csp</span><span class=\"o\">.</span><span class=\"n\">assign</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">current</span><span class=\"p\">)</span>\n",
       "    <span class=\"c1\"># Now repeatedly choose a random conflicted variable and change it</span>\n",
       "    <span class=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">max_steps</span><span class=\"p\">):</span>\n",
       "        <span class=\"n\">conflicted</span> <span class=\"o\">=</span> <span class=\"n\">csp</span><span class=\"o\">.</span><span class=\"n\">conflicted_vars</span><span class=\"p\">(</span><span class=\"n\">current</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">conflicted</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">current</span>\n",
       "        <span class=\"n\">var</span> <span class=\"o\">=</span> <span class=\"n\">random</span><span class=\"o\">.</span><span class=\"n\">choice</span><span class=\"p\">(</span><span class=\"n\">conflicted</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">val</span> <span class=\"o\">=</span> <span class=\"n\">min_conflicts_value</span><span class=\"p\">(</span><span class=\"n\">csp</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">current</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">csp</span><span class=\"o\">.</span><span class=\"n\">assign</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">current</span><span class=\"p\">)</span>\n",
       "    <span class=\"k\">return</span> <span class=\"bp\">None</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(min_conflicts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's use this algorithm  to solve the `eight_queens` CSP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "solution = min_conflicts(eight_queens)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is indeed a valid solution. \n",
    "<br>\n",
    "`notebook.py` has a helper function to visualize the solution space."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAewAAAHwCAYAAABkPlyAAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAIABJREFUeJzt3X+4FNWd7/vPd9gbEMOvDRtMgGtg\nkifnTowY2SPOELnEkDEgGD137gxco0dzczk39xiC4GRGnmeemDwnmqsCIXHu5OTIgOeMAc04RtRE\niUYwYNTZMMrEZOY+BkxE5McWCCgmAmfdP2q3u7t3VXV1d1VXV9X79Tz9dHfVqrVW92Lz7bVq1Spz\nzgkAALS330u7AgAAoDYCNgAAGUDABgAgAwjYAABkAAEbAIAMIGADAJABBGwAADKAgA0AQAYQsIE2\nY2bvN7MfmNlRMztgZneZWUdI+jFm9rf9aU+a2b+Y2X9oZZ0BJI+ADbSf/1fSIUnvlXSBpP9F0v/t\nl9DMhkp6QtK5kv5I0mhJfyHpdjNb2pLaAmgJAjbQfqZKut8591vn3AFJj0n6cEDaayT9T5L+N+fc\nXufcKefcY5KWSvrPZjZSkszMmdkHSgeZ2QYz+89l7xeY2QtmdszMnjGz88v2vc/MHjCzw2a2t/yH\ngJndYmb3m9l/M7MTZvaSmfWU7f9LM3utf9+/mdkn4vmKgOIhYAPtZ62kRWY2wswmSZonL2j7+aSk\nHzrn3qra/oCkEZIurlWYmV0o6e8k/UdJ4yT9F0mbzWyYmf2epIclvShpkqRPSFpmZpeVZXGFpE2S\nxkjaLOmu/nw/JOkGSX/onBsp6TJJr9SqDwB/BGyg/WyT16M+LmmfpF5J3w9IO17S69UbnXOnJfVJ\n6o5Q3v8p6b84555zzp1xzt0j6Xfygv0fSup2zn3VOfeOc26PpP8qaVHZ8dudcz9wzp2R9N8lTe/f\nfkbSMEl/YGadzrlXnHO/jFAfAD4I2EAb6e/RPi7pHyWdLS8gj5X0/wQc0ifvXHd1Ph39xx6OUOy5\nklb0D4cfM7NjkqZIel//vvdV7VspaWLZ8QfKXp+UNNzMOpxzL0taJukWSYfMbJOZvS9CfQD4IGAD\n7aVLXrC8yzn3O+fcG5LWS5ofkP4JSfPM7Oyq7f+rpFOSnu9/f1LeEHnJOWWvX5X0NefcmLLHCOfc\nxv59e6v2jXTOBdWngnPuu865j8kL/E7BPzwA1EDABtqIc65P0l5JnzezDjMbI+k/yDuH7Oe/yxs2\n/17/5WCd/eeXvynpdufcb/rTvSDpfzezIWb2KXkzz0v+q6T/y8xmmudsM7u8f8La85KO908eO6v/\n+PPM7A9rfRYz+5CZXWpmwyT9VtLb8obJATSAgA20n38v6VPyhrNflnRa0o1+CZ1zv5M0V15P+Dl5\nQfExSd+Q9JWypF+UtFDSMUlXq+ycuHOuV9557LskHe0v87r+fWf6j7tA3g+JPkl3y7t8rJZhkr7e\nf8wBSRPkDacDaIA559KuA4CYmFmnpB9Kek3SdY4/cCA36GEDOeKcOyXv/PUvJX0o5eoAiBE9bAAA\nMoAeNgAAGRB4Q4FWGT9+vHv/+9+fdjUSs3PnzrSrkKgZM2akXYXE0YbZRvtlX97bUFKfc67mIkep\nD4n39PS43t7eVOuQJDNLuwqJivXfz84YvqsZ8f97pg2zjfbLvry3oaSdzrmeWokYEke6Dt7hBeo4\ngrU0kNfBVfHkBwBtgoCNdJx6wwus+76UTP77bvLyP3UwmfwBoMVSP4eNAoqrNx3F7v4VOBMYKgeA\nVqKHjdZqZbBuh3IBICYEbLTGrmHpB82dJh3ZlG4dAKBBBGwkb6dJ7p2ms7nh9hjqsndx+j8cAKAB\nnMNGsnYNbzoLK7vY4W/u955ds1cC7homXfi7JjMBgNahh41kudpBsXuudO8P/fdZwJWJQdsji6HH\nDwCtRMBGcmoMPVuP9+g7Jn3mr5sPwqX8So/z/qy5+gFAOyFgIxk1guG37vPf3mjQ9jvupT0RDiRo\nA8gIAjbid/pQzSRL72hBPRTxB8DpvsTrAQDNImAjfi9OjC2roMllTU86K/dizTX3ASB1zBJHvF4f\nuPbKr3dbCrSuN/rwt+uVTpyURs2Wjj8tjRwRvTrrvzzwOqw+OrBGOufG6BkDQIvRw0a89v+lpOBg\nvK9stHzW9MH7g3rOpSAdFKyDjrtuoff86wP++9+t52vL/RMAQJsgYKOlpswfeL19XWWgDRvm/uBV\n3vO4S4PTVOdV/v7cBfXVEwDaDQEb8WlyxvVrIXPVXn7Vez5yPDhN2L5ImDEOoI0RsNFS82cF75s8\nP3hfFGG97wWXNJc3AKSNgI1EnNzhv/3Rta2tR8nDa/y3v/1Ma+sBAI0iYCMepypndZ01zDuHfNaw\ngW1RLsXa8HBjxT+0rXaa8vJHDPfeDx9alejU4cYqAAAJI2AjHrvf67v55A7p1HPe6yiXcV3/lcHb\nTp+pfN93bHCaK1fUzrtU/rGt0lvbAxLtnlA7IwBIAQEbiesY0tzxQy+ufN89t7n8Rr+nueMBIA0E\nbLRUlF72opWV750LT//Zr8ZTLgC0MwI22s59W+pLv35zMvUAgHaSSMA2s0+Z2b+Z2ctm9ldJlIH2\nsnx19LSt7u3WU149nwMAWin2gG1mQyT9jaR5kv5A0mIz+4O4y0F7WR3zyp6fvy1aurjv+hX35wCA\nuCTRw75I0svOuT3OuXckbZL06QTKQYYtWBa+/9sPeM/bdvnv3/y09xx0X+2S6tnj115eu24A0I6S\nCNiTJL1a9n5f/7Z3mdkSM+s1s97Dh7nutQimvq/y/aNBl1VVmbPEf/unI/aEq6/PvsfnsjEAyIIk\nArbfgswV83ydc99xzvU453q6u7kXcRH85O7B2+YtDT+mK2SpUUka+/Hw/ctWhe8HgCxJImDvkzSl\n7P1kSfsTKAftZHr4SMkkn/VIHquxLOjRGjfzOHYifP/ajeH7fZ3f18BBAJC8JAL2P0n6oJlNNbOh\nkhZJ4sKbvOsY39BhSc0Yv+qmBg/sHBdrPQAgLh1xZ+icO21mN0h6XNIQSX/nnHsp7nKAMN/fmnYN\nACBesQdsSXLO/UDSD5LIG9k1sUs6eCS98meel17ZANAsVjpDfGaEryF6oM4VzMp95APS3Iuk35/c\neB7PbqiRoEb9ASBNifSwgSCuN/i89fxZzd0v+7IbpC3PBpcLAFlGwEa8Jt8p7Quf8XVsqzRmjvf6\n4BZpQlfl/utuke55JHqRs6ZL29dJj981sG3vfmnaFd7rSD37Kd+MXiAApIAhccRrYu0bU5dub+l6\nvWC9aYvX6y496gnWkrTjxcrjNz7uLdRS6lVP7Ao/XpI04Qv1FQoALWau1r0LE9bT0+N6e/M7Xmnm\nt45Mfvj++zl1WNrtc+F1laiXdC2cLV2/UJozQzp6QvrpbunW9dLP90SoX5R/Wuf3hV7OVcg2zBHa\nL/vy3oaSdjrnav6PyJA44tfZ+Op1m1d7ATrI2FHStEnS1fMqt29/Qbrkcw0WyrXXADKAgI1kzHDS\nzvBfxaUJaJ0d0jtVk8XqWVDF9Uofu2CgN905Uzp9JmLvmpnhADKCgI3kRAja0kCwbnTVs/Ljzjwv\nnXouYl4EawAZwqQzJGtq7QW9S5PF/NyyRDr6lNdbLj1O7vC2+xlyUcRgPfV7ERIBQPtg0lnC8j5Z\nItK/n4BednVgvXKO9OCdjddl8Upvxnm5wGHxOnrXtGG20X7Zl/c2FJPO0DZmOGnXCMm9PWhX35PS\nuNGV20bOlt48GT37rlHSGz+WNt7qPSTp6xukm+/ySTx1o9S1KHrmANAmCNhojQv7I3BVb7tjiDT1\nCumVJm7AeuR4ZW/9V48M7mlL4pw1gEzjHDZaqyxoul7poW3NBWs/5y7wrtuuGA4nWAPIOHrYaL0Z\nTjp1RNo9TtdeLl17eYJlnX+oqevCAaBd0MNGOjq7vMA9ZU0y+U9Z6+VPsAaQE/Swka4Jy7yHFOma\n7ZoY+gaQU/Sw0T5muIHH9KODdq/w64yf/3rlcQCQU/Sw0Z46xgwKwKv+PqW6AEAboIcNAEAGELAB\nAMgAAjYAABlAwAYAIANSv/mHmeV6am/a32/SCrAoP22YcbRf9hWgDSPd/IMeNoBEjBlZeVtU1yst\nv3rwtnPGpV1TIBvoYScs7e83afy6z7442zDwdqZ1iHQ/8zrQftlXgDakhw0geTddM9BbjkN5bxzA\nAHrYCUv7+00av+6zr9E2LN2HPGkT/0Q6dKTx42m/7CtAG0bqYbPSGYC6xdWbjuJg/73N4x4qB7KG\nIXEAdWllsG6HcoF2QcAGEMlvn0k/aLpe6c8/mW4dgLQQsAHU5HqlYUObz+eG25vPY9Nt6f9wANLA\npLOEpf39Jo0JL9lXqw3f3iENH9ZkGT7nn5sNur97Rxr+x7XTFb398qAAbchlXQCaFyVYd8+V7v2h\n/76gyWLNTiKLo8cPZAk97ISl/f0mjV/32RfWhrV6wVF6zmGBuVbaD0+TfnZ//XWoKKPA7ZcXBWhD\netgAGlcrWH/rPv/tjfac/Y57aU/t4zifjaIgYAMYpLurdpqldyRfDynaD4Bxo5OvB5A2AjaAQQ5t\niS+voB5wnD3jvifjywtoV6x0BqDCX1wz8DrsHLXrjT787XqlEyelUbOl409LI0dEr8/6L0erz7LF\n0jc2Rs8XyBp62AAq3P5F7zkoGO87NPB61vTB+4N6zqUgHRSsg467bqH3/OsD/vtL9Vyzwn8/kBcE\nbAB1mTJ/4PX2dZWBNmyY+4NXec/jLg1OU51X+ftzF9RXTyBvCNgA3tXseeXXDgXve/lV7/nI8eA0\nYfuiYMY48oyADaAu82cF75s8P3hfFGG97wWXNJc3kHUEbAC+Tu7w3/7o2tbWo+ThNf7b336mtfUA\n0kLABiBJmjiu8v1Zw7wh5rPKliaNMuS84eHGyn9oW+005eWPGO69H161ROn4MY2VD7Q7liZNWNrf\nb9JYFjH7Sm0YFoxPn5E6ZyowXfWM8uo05cdL0uEnBgfWWnmUpzm2VRr9nuD6ludVlPbLswK0IUuT\nAohHx5Dmjh96ceX77rnN5RcWrIG8ImADqEuUxVIWrax8X6uD9NmvxlMukGexB2wz+zszO2RmP4s7\nbwDZcF+dS5uu35xMPYA8SaKHvUHSpxLIF0CClq+OnrbVvd16yqvncwBZEnvAds49LelI3PkCSNbq\n5fHm9/nboqWL+65fcX8OoF1wDhtAQxYsC9//7Qe85227/Pdvftp7DrqvdsmVVWuEX3t57boBeZRK\nwDazJWbWa2YsJAhkxNT3Vb5/dHu04+Ys8d/+6Yg94errs+/5SrTjgLxJJWA7577jnOuJct0ZgPbw\nk7sHb5u3NPyYrpClRiVp7MfD9y9bFb4fKBKGxAFIksZ/Inz/pAmDtz1WY1nQozVu5nHsRPj+tQ3c\n3zpsPXIgy5K4rGujpJ9K+pCZ7TOz/yPuMgDE743fNHZcUjPGr7qpseOaveMX0K464s7QObc47jwB\nFM/3t6ZdA6C9MCQOILKJXemWP/O8dMsH0sTNPxKW9vebNG48kH3VbVjrjlyNDoF/5ANewN+7X/rl\nvsbyaKRuRWu/PCpAG0a6+UfsQ+IA8s31Bgft+bOau1/2ZTdIW54NLhcoMgI2gAor1kirbgxPc2yr\nNGaO9/rgFmlC1VD5dbdI9zwSvcxZ06Xt66TH7xrYtne/NO0K7/WBCGuTfyHmFdOAdsOQeMLS/n6T\nxnBc9vm1YZTerPUMpNu0RVq8Mjx9Pb77NWnxZYPLqVUfP0Vsv7wpQBtGGhInYCcs7e83afxnkX1+\nbTh+jHT4iQjHRjyfvXC2dP1Cac4M6egJ6ae7pVvXSz/fU/vYKMF63KXBl3MVsf3ypgBtyDlsAI3p\nO9b4sZtXewE6yNhR0rRJ0tXzKrdvf0G65HONlcm11ygCetgJS/v7TRq/7rMvrA2jDkV3dkjvPDt4\ne1TV5XTOlE6faW4o/N28C9x+eVGANqSHDaA5Uc8fl4J1o5d8lR935nnp1HPR8mr1fbmBNLFwCoBQ\ni26uncZ6goPnLUuko095gb/0OLnD2+5nyEXRAvGffql2GiBPGBJPWNrfb9IYjsu+KG0Y1MuuDqxX\nzpEevLPxuixe6c04b6TsILRf9hWgDZkl3g7S/n6Txn8W2Re1Dd/aLo0YXnVsj9T3pDRudOX2kbOl\nN09Gr0PXKOmNH1du+/oG6ea7BgfsRTdL9/0oet60X/YVoA05hw0gPmd/zHuuDqAdQ6SpV0iv7G88\n7yPHK3vMv3pkcE9b4pw1io1z2ADqUh40Xa/00LbmgrWfcxd4122X/zggWKPoGBJPWNrfb9IYjsu+\nRttw7EjpyFMxV8ZH99zmrgun/bKvAG0YaUicHjaAhhw94fV6l61KJv+ld/SfI28iWAN5Qg87YWl/\nv0nj1332xdmGcdxRK+6hb9ov+wrQhvSwAbRW6Xps6xm4m1e5FWsGbzvnssrjAPijh52wtL/fpPHr\nPvvy3oa0X/YVoA3pYQMAkBcEbAAAMoCADQBABqS+0tmMGTPU2xvD1NI2lffzS3k/tyTRhllH+2Vf\n3tswKnrYAABkQOo9bAAAWqUd1wqIih42ACDXbrpm4F7scSjltfzqePKLioANAMilrlFeYL3ji8nk\nv+pGL/8JXcnkX40hcQBA7sTVm47iYP+tYJMeKqeHDQDIlVYG61aWS8AGAOTCb59JL1iXuF7pzz+Z\nTN4EbABA5rleadjQ5vO54fbm89h0WzI/HDiHDQDItLd3NJ9H+fnnv7nfe2426P72GWn4HzeXRzl6\n2ACATBs+rHaa7rnSvT/03xc0WazZSWRx9PjLEbABAJlVqxdcus963zHpM3/dfBAuv3e79Ujn/Vlz\n9asHARsAkEm1guG37vPf3mjQ9jvupT21j4sraBOwAQCZ0x1hsZKldyRfDynaD4Bxo5svh4ANAMic\nQ1viyyuoBxzncHbfk83nwSxxAECm/MU1A6/9erelQOt6ow9/u17pxElp1Gzp+NPSyBHR67P+y9Hq\ns2yx9I2N0fOtRg8bAJApt/evDR4UjPcdGng9a/rg/UE951KQDgrWQcddt9B7/vUB//2leq5Z4b8/\nKgI2ACBXpswfeL19XWWgDRvm/uBV3vO4S4PTVOdV/v7cBfXVs14EbABAZjR7Xvm1Q8H7Xn7Vez5y\nPDhN2L4omqk/ARsAkCvzZwXvmzw/eF8UYb3vBZc0l3ctBGwAQCadDFiS9NG1ra1HycNr/Le//Uw8\n+ROwAQCZMHFc5fuzhnlDzGeVLU0aZch5w8ONlf/QttppyssfMdx7P7xqidLxYxorn4ANAMiEA4/7\nbz+5Qzr1nPc6ymVc139l8LbTZyrf9x0bnObKCLO8S+Uf2yq9td0/zeEnaufjh4ANAMi8jiHNHT/0\n4sr33XOby2/0e5o73g8BGwCQK1F62YtWVr53Ljz9Z78aT7nNIGADAArnvjqXNl2/OZl61CP2gG1m\nU8zsKTP7hZm9ZGZfjLsMAEDxLF8dPW3Svd1myqvnc5RLood9WtIK59z/LOliSf/JzP4ggXIAAAWy\nenm8+X3+tmjp4r7rV6OfI/aA7Zx73Tm3q//1CUm/kDQp7nIAAAizYFn4/m8/4D1v2+W/f/PT3nPQ\nfbVLqmePX3t57bo1ItFz2Gb2fkkflfRc1fYlZtZrZr2HDx9OsgoAgIKY+r7K948GXFZVbc4S/+2f\njtgTrr4++x6fy8bikFjANrP3SHpA0jLnXMXqq8657zjnepxzPd3d3UlVAQBQID+5e/C2eUvDj+kK\nWWpUksZ+PHz/slXh++OUSMA2s055wfpe59w/JlEGAKBYxn8ifP+kCYO3PVZjWdCjNW7mcexE+P61\nDdzfOmw98jBJzBI3Sesk/cI51+BcOAAAKr3xm8aOS2rG+FU3NXZco3f8SqKHPUvSNZIuNbMX+h9N\n3h8FAID28v2trS2vI+4MnXPbJVnc+QIAUMvELungkfTKn3lecnmz0hkAIDNqDW8fqHMFs3If+YA0\n9yLp9yc3nsezG8L3NzM8H3sPGwCANLne4MA4f1Zz98u+7AZpy7PB5SaJgA0AyJQVa6RVN4anObZV\nGjPHe31wizShq3L/dbdI9zwSvcxZ06Xt66TH7xrYtne/NO0K73WUnv0XmlwxzVytW5QkrKenx/X2\nJvyzJEXepPn8SvvfTyvQhtlG+2WfXxtG6c1az0C6TVukxSvD09fju1+TFl82uJxa9Qmw0zlXc7Cc\ngJ0w/rPIPtow22i/7PNrw/FjpMNPRDg24jnjhbOl6xdKc2ZIR09IP90t3bpe+vme2sdGCdbjLg29\nnCtSwGZIHACQOX3HGj9282ovQAcZO0qaNkm6el7l9u0vSJd8rrEyG732uhwBGwCQSVGGoksT0Do7\npHeqJovVM2Pb9Uofu2CgvM6Z0ukzTQ+F14WADQDIrKjnj0vButHgWX7cmeelU89FyyvOVda4DhsA\nkGmLbq6dxnqCg+ctS6SjT3mBv/Q4ucPb7mfIRdEC8Z9+qXaaejDpLGFMeMk+2jDbaL/si9KGQb3s\n6sB65RzpwTsbr8vild6M80bKDsGkMwBAMViP9NZ2acTwwfv6npTGja7cNnK29ObJ6Pl3jZLe+LG0\n8VbvIUlf3yDdfNfgtItulu77UfS8oyJgAwBy4eyPec/VPd6OIdLUK6RX9jee95HjlT3mXz0yuKct\nJXdnMIlz2ACAnCkPmq5Xemhbc8Haz7kLvOu2y38cJBmsJXrYAIAcsh5p7EjpyFPStZd7j6R0z23u\nuvCo6GEDAHLp6AkvcC9blUz+S+/w8m9FsJboYQMAcm7tRu8hxXNHraSHvoPQwwYAFEbpemzrGbib\nV7kVawZvO+eyyuPSQg8bAFBIv3nTPwCvvrf1dYmCHjYAABlAwAYAIAMI2AAAZAABGwCADEj95h9m\nluuV69P+fpOW9xsrSLRh1tF+2VeANuTmH0DbOnNUeqGrYtOKNdKqG6vSnb9f6nxv6+oFoG3Rw05Y\n2t9v0vh1X4edMXxXM+L/95T3NuRvMPsK0IaReticwwaSdPAOL1DHEaylgbwOJrTWIoC2RQ87YWl/\nv0nj132AU29Iu8fHX5lq5x+QOic2lUXe25C/wewrQBtyDhtIRVy96Sh2n+M9JzBUDqC9MCQOxKmV\nwbodygXQMgRsIA67hqUfNHeadGRTunUAkBgCNtCsnSa5d5rO5obbY6jL3sXp/3AAkAgmnSUs7e83\naYWf8LJruOR+11T+fncLavqevTZUujBavfLehvwNZl8B2pDLuoDERQjW3XOle3/ovy/o3rpN33M3\nhh4/gPZCDzthaX+/SSv0r/saQ89Res5hgblW2g9Pk352f2gVIs0ez3sb8jeYfQVoQ3rYQGJqBOtv\n3ee/vdGes99xL+2JcCDns4HcIGAD9Tp9qGaSpXe0oB6K+APgdF/i9QCQPAI2UK8Xm1tZrFzQ5LKm\nJ52Ve7E7xswApIWVzoB6vD5w7VXYOWrXG3342/VKJ05Ko2ZLx5+WRo6IXp31Xx54HXrO/MAa6Zzq\nW4EByBJ62EA99v+lpOBgvK9stHzW9MH7g3rOpSAdFKyDjrtuoff86wP++9+t52vL/RMAyAwCNhCj\nKfMHXm9fVxlow4a5P3iV9zzu0uA01XmVvz93QX31BJA9BGwgqiZnXL8WMlft5Ve95yPHg9OE7YuE\nGeNAphGwgRjNnxW8b/L84H1RhPW+F1zSXN4A2h8BG2jAyR3+2x9d29p6lDy8xn/728+0th4AkkPA\nBqI4VTmr66xh3jnks4YNbItyKdaGhxsr/qFttdOUlz9iuPd++NCqRKcON1YBAKljadKEpf39Jq0w\nyyKGnP89fUbqnNmf1idoV88or05TfrwkHX5CGj+mvjzK0xzbKo1+T2B1By1Xmvc25G8w+wrQhixN\nCrRCx5Dmjh96ceX77rnN5RcarAFkFgEbiFGUxVIWrax8X6vz8NmvxlMugGyLPWCb2XAze97MXjSz\nl8zsK3GXAWTZfVvqS79+czL1AJAtSfSwfyfpUufcdEkXSPqUmV1c4xigrS1fHT1tq3u79ZRXz+cA\n0F5iD9jO82b/287+R75nDCD3Vse8sufnb4uWLu67fsX9OQC0TiLnsM1siJm9IOmQpB85556r2r/E\nzHrNLM57EgFtY8Gy8P3ffsB73rbLf//mp73noPtql1y5ovL9tZfXrhuAbEr0si4zGyPpQUlfcM79\nLCBNrnvfBbgcIe0qJK7WZV2SNO0Kae/+quP6f44GDVnXuqNX2P6gvCPdlpPLunIl7+0nFaIN07+s\nyzl3TNJWSZ9KshwgbT+5e/C2eUvDj+kKWWpUksZ+PHz/slXh+wHkSxKzxLv7e9Yys7MkzZX0r3GX\nA7TU9PAVwiZNGLztsRrLgh6tcTOPYyfC96/dGL7f1/l9DRwEoB10JJDneyXdY2ZD5P0guN8590gC\n5QCt0zG+ocOSmjF+1U0NHtg5LtZ6AGid2AO2c263pI/GnS+AAd/fmnYNALQaK50BMZnYlW75M89L\nt3wAyeLmHwlL+/tNWuFmqNaYLd7oEPhHPuAF/L37pV/uayyPmjPEZ/j/W8x7G/I3mH0FaMNIs8ST\nOIcNFFbYpVjzZzV3v+zLbpC2PBtcLoB8I2AD9Zh8p7QvfMbXsa3SmDne64NbpAlVQ+XX3SLdU8c0\nzFnTpe3rpMfvGti2d7937bckHYiyNvmUb0YvEEBbYkg8YWl/v0kr5HBcjWFxyetll3q9m7ZIi1eG\np6/Hd78mLb5scDmhAobDpfy3IX+D2VeANow0JE7ATlja32/SCvmfxanD0m6fC6+rRD2fvXC2dP1C\nac4M6egJ6ae7pVvXSz/fE6FuUYL1+X2hl3PlvQ35G8y+ArQh57CBRHR2N3zo5tVegA4ydpQ0bZJ0\n9bzK7dtfkC75XIOFcu01kAv0sBOW9vebtEL/uo84NN7ZIb3z7ODtkcuv6kV3zpROn2l+KPzduuS8\nDfkbzL4CtCE9bCBRM2rfFEQaCNaNXvJVftyZ56VTz0XMK0KwBpAdLJwCNGNq7QW9rSc4wN6yRDr6\nlNdbLj1O7vC2+xlyUcRgPfWUmjVSAAAgAElEQVR7ERIByBKGxBOW9vebNIbjFNjLrg6sV86RHryz\n8XosXunNOK+oW9CweB2967y3IX+D2VeANmSWeDtI+/tNGv9Z9Ns1QnJvV2yyHqnvSWnc6MqkI2dL\nb56MXn7XKOmNH1du+/oG6ea7fAL21I1S16LomSv/bcjfYPYVoA05hw20zIX9Ebiqt90xRJp6hfTK\n/sazPnK8srf+q0cG97Qlcc4ayDnOYQNxKguarld6aFtzwdrPuQu867YretcEayD3GBJPWNrfb9IY\njgtw6oi0uwXXP59/qKnrwqX8tyF/g9lXgDaMNCRODxtIQmeX1+udsiaZ/Kes9fJvMlgDyA562AlL\n+/tNGr/u6xDhmu2aEhj6znsb8jeYfQVoQ3rYQFuZ4QYe048O2r3CrzN+/uuVxwEoLHrYCUv7+00a\nv+6zL+9tSPtlXwHakB42AAB5QcAGACADCNgAAGRA6iudzZgxQ729Ue4TmE15P7+U93NLEm2YdbRf\n9uW9DaOihw0AQAak3sOOTZte4woAQByy3cM+eIcXqOMI1tJAXgdXxZMfAAAxyWbAPvWGF1j3fSmZ\n/Pfd5OV/6mAy+QMAUKfsDYnH1ZuOYvc53jND5QCAlGWrh93KYN0O5QIA0C8bAXvXsPSD5k6TjmxK\ntw4AgMJq/4C90yT3TtPZ3HB7DHXZuzj9Hw4AgEJq73PYu4Y3nYWVLaf+N/d7z67ZdVp2DZMu/F2T\nmQAAEF1797Bd7aDYPVe694f++yzg3idB2yOLoccPAEA92jdg1xh6th7v0XdM+sxfNx+ES/mVHuf9\nWXP1AwAgTu0ZsGsEw2/d57+90aDtd9xLeyIcSNAGALRI+wXs04dqJll6RwvqoYg/AE73JV4PAADa\nL2C/ODG2rIImlzU96azci90xZgYAgL/2miX++sC1V36921Kgdb3Rh79dr3TipDRqtnT8aWnkiOjV\nWf/lgddh9dGBNdI5N0bPGACAOrVXD3v/X0oKDsb7ykbLZ00fvD+o51wK0kHBOui46xZ6z78+4L//\n3Xq+ttw/AQAAMWmvgF3DlPkDr7evqwy0YcPcH7zKex53aXCa6rzK35+7oL56AgAQt/YJ2E3OuH4t\nZK7ay696z0eOB6cJ2xcJM8YBAAlqn4AdwfxZwfsmzw/eF0VY73vBJc3lDQBAs9oyYJ/c4b/90bWt\nrUfJw2v8t7/9TGvrAQAorvYI2KcqZ3WdNcw7h3zWsIFtUS7F2vBwY8U/tK12mvLyRwz33g8fWpXo\n1OHGKgAAQA3tEbB3v9d388kd0qnnvNdRLuO6/iuDt50+U/m+79jgNFeuqJ13qfxjW6W3tgck2j2h\ndkYAADSgPQJ2iI4hzR0/9OLK991zm8tv9HuaOx4AgEa0fcAuF6WXvWhl5XvnwtN/9qvxlAsAQJIS\nCdhmNsTM/tnMHkki/zD3bakv/frNydQDAIA4JdXD/qKkX0RNvHx19Ixb3dutp7x6PgcAAPWIPWCb\n2WRJl0u6O+oxq2Ne2fPzt0VLF/ddv+L+HAAAlCTRw/6GpC9J+h9BCcxsiZn1mlnv4cP1Xwq1YFn4\n/m8/4D1v2+W/f/PT3nPQfbVLqmePX3t57boBAJCEWAO2mS2QdMg5tzMsnXPuO865HudcT3d37dtT\nTn1f5ftHgy6rqjJnif/2T0fsCVdfn32Pz2VjAAC0Qtw97FmSrjCzVyRtknSpmf19s5n+xGdwfd7S\n8GO6QpYalaSxHw/fv2xV+H4AAFop1oDtnLvZOTfZOfd+SYsk/dg595maB04PHxaf5LMeyWM1lgU9\nWuNmHsdOhO9fuzF8v6/z+xo4CACA2trjOuyO8Q0dltSM8atuavDAznGx1gMAgJKOpDJ2zm2VtDWp\n/JP0/a1p1wAAgErt0cOOYGJXuuXPPC/d8gEAxdY+AXtG+BqiB+pcwazcRz4gzb1I+v3Jjefx7IYa\nCWrUHwCAZiQ2JJ4E1xt83nr+rObul33ZDdKWZ4PLBQAgTe0VsCffKe0Ln/F1bKs0Zo73+uAWaULV\nUPl1t0j31LGC+azp0vZ10uN3DWzbu1+adoX3OlLPfso3oxcIAEAD2mdIXJIm1r4xden2lq7XC9ab\ntni97tKjnmAtSTterDx+4+PeQi2lXnWkc+cTvlBfoQAA1MlcrftPJqynp8f19paNOZ86LO32ufC6\nStRLuhbOlq5fKM2ZIR09If10t3Treunne2ofG2ko/Py+0Mu5zCxaRTMq7X8/rUAbZhvtl315b0NJ\nO51zNaNaew2JS1Jn7aVKg2xe7QXoIGNHSdMmSVfPq9y+/QXpks81WCjXXgMAWqD9ArbkzbjeGf6L\nqjQBrbNDeqdqslg9C6q4XuljFwz0pjtnSqfPROxdMzMcANAi7RmwpUhBWxoI1o2uelZ+3JnnpVPP\nRcyLYA0AaKH2mnRWbWrtBb1Lk8X83LJEOvqU11suPU7u8Lb7GXJRxGA99XsREgEAEJ/2m3RWLaCX\nXR1Yr5wjPXhn4/VYvNKbcV4ucFi8jt513idLpP3vpxVow2yj/bIv722ozE46qzbDSbtGSO7tQbv6\nnpTGja7cNnK29ObJ6Nl3jZLe+LG08VbvIUlf3yDdfJdP4qkbpa5F0TMHACAm7R+wJenC/ghc1dvu\nGCJNvUJ6ZX/jWR85Xtlb/9Ujg3vakjhnDQBIVXufw65WFjRdr/TQtuaCtZ9zF3jXbVcMhxOsAQAp\ny0YPu9wMJ506Iu0ep2svl669PMGyzj/U1HXhAADEJVs97JLOLi9wT1mTTP5T1nr5E6wBAG0iez3s\nchOWeQ8p0jXbNTH0DQBoU9nsYfuZ4QYe048O2r3CrzN+/uuVxwEA0Kay3cMO0jFmUABe9fcp1QUA\ngBjkp4cNAECOEbABAMgAAjYAABmQ+lriZpbr2V5pf79JK8Aav7RhxtF+2VeANoy0ljg9bAAAMiCf\ns8QBAA0JvEthHSLdphh1o4cNAAV30zVeoI4jWEsDeS2/Op784OEcdsLS/n6Txvmz7Mt7G9J+wUq3\nF07axD+RDh1p/PgCtGFO7ocNAIhdXL3pKA7237KYofLmMCQOAAXTymDdDuXmBQEbAArit8+kHzRd\nr/Tnn0y3DllFwAaAAnC90rChzedzw+3N57HptvR/OGQRk84Slvb3m7S8T1iSaMOso/2kt3dIw4c1\nWY7P+edmg+7v3pGG/3HtdAVoQxZOAQBEC9bdc6V7f+i/L2iyWLOTyOLo8RcJPeyEpf39Ji3vvTOJ\nNsy6ordfrV5wlJ5zWGCulfbD06Sf3V9/HSrKyH8b0sMGgCKrFay/dZ//9kZ7zn7HvbSn9nGcz46G\ngA0AOdTdVTvN0juSr4cU7QfAuNHJ1yPrCNgAkEOHtsSXV1APOM6ecd+T8eWVV6x0BgA58xfXDLwO\nO0fteqMPf7te6cRJadRs6fjT0sgR0euz/svR6rNssfSNjdHzLRp62ACQM7d/0XsOCsb7Dg28njV9\n8P6gnnMpSAcF66DjrlvoPf/6gP/+Uj3XrPDfDw8BGwAKZsr8gdfb11UG2rBh7g9e5T2PuzQ4TXVe\n5e/PXVBfPVGJgA0AOdLseeXXDgXve/lV7/nI8eA0YfuiYMZ4MAI2ABTM/FnB+ybPD94XRVjve8El\nzeVddARsAMipkzv8tz+6trX1KHl4jf/2t59pbT2yioANADkxcVzl+7OGeUPMZ5UtTRplyHnDw42V\n/9C22mnKyx8x3Hs/vGqJ0vFjGis/71iaNGFpf79Jy/uylhJtmHVFar+wYHz6jNQ5Mzhd9Yzy6jTl\nx0vS4ScGB9ZaeZSnObZVGv2e4PqW51WANmRpUgCAp2NIc8cPvbjyfffc5vILC9bwR8AGgIKJsljK\nopWV72t1cj/71XjKRbBEAraZvWJm/2JmL5gZk/QBIGPuq3Np0/Wbk6kHBiTZw/64c+6CKOPyAIDm\nLV8dPW2re7v1lFfP5ygShsQBICdWL483v8/fFi1d3Hf9ivtz5EVSAdtJ2mJmO81sSfVOM1tiZr0M\nlwNAehYsC9//7Qe85227/Pdvftp7DrqvdsmVVWuEX3t57bphsEQu6zKz9znn9pvZBEk/kvQF59zT\nAWlzPV+/AJcjpF2FxNGG2Vak9qt1jfW0K6S9+yu3lY4JGrKudUevsP1BeUe5FpzLugZLpIftnNvf\n/3xI0oOSLkqiHABAdD+5e/C2eUvDj+kKWWpUksZ+PHz/slXh+xFd7AHbzM42s5Gl15L+RNLP4i4H\nAFBp/CfC90+aMHjbYzWWBT1a42Yex06E71/bwP2tw9YjL7KOBPKcKOnB/mGaDknfdc49lkA5AIAy\nb/ymseOSmjF+1U2NHdfsHb/yKvaA7ZzbI8nnlugAgCL5/ta0a5AvXNYFAAUysSvd8meel275WcbN\nPxKW9vebtLzPMJZow6wrYvvVmoXd6BD4Rz7gBfy9+6Vf7mssj0bqVoA2jDRLPIlz2ACANhZ2Kdb8\nWc3dL/uyG6QtzwaXi8YRsAEgZ1askVbdGJ7m2FZpzBzv9cEt0oSqofLrbpHueSR6mbOmS9vXSY/f\nNbBt737v2m9JOhBhbfIvxLxiWt4wJJ6wtL/fpOV9OFWiDbOuqO0XdXGSUrpNW6TFK8PT1+O7X5MW\nXza4nFr18VOANow0JE7ATlja32/S8v6fvUQbZl1R22/8GOnwExGOj3g+e+Fs6fqF0pwZ0tET0k93\nS7eul36+p/axUYL1uEuDL+cqQBtyDhsAiqrvWOPHbl7tBeggY0dJ0yZJV8+r3L79BemSzzVWJtde\n10YPO2Fpf79Jy3vvTKINs67o7Rd1KLqzQ3rn2cHbo6oup3OmdPpMc0Ph7+ad/zakhw0ARRf1/HEp\nWDd6yVf5cWeel049Fy2vVt+XO8tYOAUAcm7RzbXTWE9w8LxliXT0KS/wlx4nd3jb/Qy5KFog/tMv\n1U6DAQyJJyzt7zdpeR9OlWjDrKP9PEG97OrAeuUc6cE7G6/P4pXejPNGyg5SgDZklng7SPv7TVre\n/7OXaMOso/0GvLVdGjG86vgeqe9Jadzoyu0jZ0tvnoxej65R0hs/rtz29Q3SzXcNDtiLbpbu+1H0\nvAvQhpzDBgAMOPtj3nN1AO0YIk29Qnplf+N5Hzle2WP+1SODe9oS56ybwTlsACiY8qDpeqWHtjUX\nrP2cu8C7brv8xwHBujkMiScs7e83aXkfTpVow6yj/YKNHSkdeSrGygTontvcdeEFaMNIQ+L0sAGg\noI6e8Hq9y1Ylk//SO/rPkTcRrDGAHnbC0v5+k5b33plEG2Yd7VefOO6oFffQdwHakB42AKA+peux\nrWfgbl7lVqwZvO2cyyqPQzLoYScs7e83aXnvnUm0YdbRftlXgDakhw0AQF4QsAEAyAACNgAAGZD6\nSmczZsxQb28M0xLbVN7PL+X93JJEG2Yd7Zd9eW/DqOhhAwCQAQRsAAAyIPUhcUTXjgsaAABagx52\nm7vpmoEbxsehlNfyq+PJDwDQGgTsNtU1ygusd3wxmfxX3ejlP6ErmfwBAPFiSLwNxdWbjuJg//1q\nGSoHgPZGD7vNtDJYt0O5AIBoCNht4rfPpB80Xa/0559Mtw4AAH8E7DbgeqVhQ5vP54bbm89j023p\n/3AAAAzGOeyUvb2j+TzKzz//zf3ec7NB97fPSMP/uLk8AADxoYedsuHDaqfpnivd+0P/fUGTxZqd\nRBZHjx8AEB8Cdopq9YJLN4PvOyZ95q+bD8LlN5i3Hum8P2uufgCA1iFgp6RWMPzWff7bGw3afse9\ntKf2cQRtAGgPBOwUdEdYrGTpHcnXQ4r2A2Dc6OTrAQAIR8BOwaEt8eUV1AOOs2fc92R8eQEAGsMs\n8Rb7i2sGXvv1bkuB1vVGH/52vdKJk9Ko2dLxp6WRI6LXZ/2Xo9Vn2WLpGxuj5wsAiBc97Ba7vX9t\n8KBgvO/QwOtZ0wfvD+o5l4J0ULAOOu66hd7zrw/47y/Vc80K//0AgNYgYLeZKfMHXm9fVxlow4a5\nP3iV9zzu0uA01XmVvz93QX31BAC0FgG7hZo9r/zaoeB9L7/qPR85HpwmbF8UzBgHgPQQsNvM/FnB\n+ybPD94XRVjve8ElzeUNAEgWATslJwOWJH10bWvrUfLwGv/tbz/T2noAAPwRsFtk4rjK92cN84aY\nzypbmjTKkPOGhxsr/6FttdOUlz9iuPd+eNUSpePHNFY+AKA5BOwWOfC4//aTO6RTz3mvo1zGdf1X\nBm87fabyfd+xwWmujDDLu1T+sa3SW9v90xx+onY+AID4EbDbQMeQ5o4fenHl++65zeU3+j3NHQ8A\niF8iAdvMxpjZP5jZv5rZL8zsj5IoJ4+i9LIXrax871x4+s9+NZ5yAQDpSaqHvVbSY865fydpuqRf\nJFROId1X59Km6zcnUw8AQOvEHrDNbJSk2ZLWSZJz7h3nnM9Z1WJZvjp62lb3duspr57PAQCITxI9\n7GmSDktab2b/bGZ3m9nZCZSTKauXx5vf52+Lli7uu37F/TkAANEkEbA7JF0o6W+dcx+V9JakvypP\nYGZLzKzXzHoPHz6cQBWyb8Gy8P3ffsB73rbLf//mp73noPtql1TPHr/28tp1AwC0XhIBe5+kfc65\n/ouV9A/yAvi7nHPfcc71OOd6uru7E6hC9kx9X+X7RwMuq6o2Z4n/9k9H7AlXX599j89lYwCA9MUe\nsJ1zByS9amYf6t/0CUk/j7ucvPnJ3YO3zVsafkxXyFKjkjT24+H7l60K3w8AaB9JzRL/gqR7zWy3\npAsk3ZpQOZkx/hPh+ydNGLztsRrLgh6tcTOPYyfC969t4P7WYeuRAwCS05FEps65FyRxZW+ZN37T\n2HFJzRi/6qbGjmv2jl8AgMaw0llBfX9r2jUAANSDgN1GJnalW/7M89ItHwAQjIDdQrWGtw/UuYJZ\nuY98QJp7kfT7kxvP49kN4ftZvhQA0pPIOWw0zvUGB8b5s5q7X/ZlN0hbng0uFwDQvgjYLbZijbTq\nxvA0x7ZKY+Z4rw9ukSZUDZVfd4t0zyPRy5w1Xdq+Tnr8roFte/dL067wXkfp2X8h5hXTAAD1MVfr\nVk8J6+npcb29+e3emdmgbVF6s9YzkG7TFmnxyvD09fju16TFlw0up1Z9/KT976cV/NowT/LehrRf\n9uW9DSXtdM7VPOlIwE6Y3z+08WOkw09EODbiOeOFs6XrF0pzZkhHT0g/3S3dul76+Z7ax0YJ1uMu\nDb6cK+1/P62Q9/8s8t6GtF/25b0NFTFgMySegr4m7l22ebUXoIOMHSVNmyRdPa9y+/YXpEs+11iZ\nXHsNAOkjYKckylB0aQJaZ4f0TtVksXpmbLte6WMXDJTXOVM6faa5oXAAQGsRsFMU9fxxKVg3GjzL\njzvzvHTquWh5EawBoH1wHXbKFt1cO431BAfPW5ZIR5/yAn/pcXKHt93PkIuiBeI//VLtNACA1mHS\nWcKiTJYI6mVXB9Yr50gP3tl4XRav9GacN1J2kLT//bRC3ie85L0Nab/sy3sbikln2WE90lvbpRHD\nB+/re1IaN7py28jZ0psno+ffNUp648fSxlu9hyR9fYN0812D0y66WbrvR9HzBgC0BgG7TZz9Me+5\nusfbMUSaeoX0yv7G8z5yvLLH/KtHBve0Jc5ZA0A74xx2mykPmq5Xemhbc8Haz7kLvOu2y38cEKwB\noL3Rw25D1iONHSkdeUq69nLvkZTuuc1dFw4AaA162G3q6AkvcC9blUz+S+/w8idYA0A20MNuc2s3\neg8pnjtqMfQNANlEDztDStdjW8/A3bzKrVgzeNs5l1UeBwDIJnrYGfWbN/0D8Op7W18XAEDy6GED\nAJABBGwAADKAgA0AQAakvpa4meV6Idy0v9+kFWCNX9ow42i/7CtAG0ZaS5weNgAAGcAscQCIamcM\nvdkZ+e4tIjn0sAEgzME7vEAdR7CWBvI6mNAyhsgtzmEnLO3vN2mcP8u+vLdhw+136g1p9/h4K+Pn\n/ANS58SGD897+0mF+BvkftgA0JC4etNR7D7He2aoHDUwJA4A5VoZrNuhXGQGARsAJGnXsPSD5k6T\njmxKtw5oWwRsANhpknun6WxuuD2GuuxdnP4PB7QlJp0lLO3vN2lMeMm+vLdhzfbbNVxyv2uqDL8b\n8TR9O1wbKl1Yu155bz+pEH+DLJwCADVFCNbdc6V7f+i/L+i2tU3fzjaGHj/yhR52wtL+fpPGr/vs\ny3sbhrZfjaHnKD3nsMBcK+2Hp0k/uz+0CjVnj+e9/aRC/A3SwwaAQDWC9bfu89/eaM/Z77iX9kQ4\nkPPZ6EfABlA8pw/VTLL0jhbUQxF/AJzuS7weaH8EbADF82LjK4tVC5pc1vSks3IvdseYGbKKlc4A\nFMvrA9dehZ2jdr3Rh79dr3TipDRqtnT8aWnkiOjVWf/lgdeh58wPrJHOuTF6xsgdetgAimX/X0oK\nDsb7ykbLZ00fvD+o51wK0kHBOui46xZ6z78+4L//3Xq+ttw/AQqDgA0AZabMH3i9fV1loA0b5v7g\nVd7zuEuD01TnVf7+3AX11RPFQ8AGUBxNzrh+LWSu2suves9HjgenCdsXCTPGC42ADQBl5s8K3jd5\nfvC+KMJ63wsuaS5v5B8BG0Ahndzhv/3Rta2tR8nDa/y3v/1Ma+uB9kXABlAMpypndZ01zDuHfNaw\ngW1RLsXa8HBjxT+0rXaa8vJHDPfeDx9alejU4cYqgMxjadKEpf39Jo1lEbMv7234bvuFnP89fUbq\nnNmf3idoV88or05TfrwkHX5CGj+mvjzK0xzbKo1+T2B1K5YrzXv7SYX4G2RpUgCIomNIc8cPvbjy\nfffc5vILDdYoLAI2AJSJsljKopWV72t1AD/71XjKRbHFHrDN7ENm9kLZ47iZLYu7HABIy31b6ku/\nfnMy9UCxxB6wnXP/5py7wDl3gaQZkk5KejDucgCgHstXR0/b6t5uPeXV8zmQL0kPiX9C0i+dc79K\nuBwACLU65pU9P39btHRx3/Ur7s+B7Eg6YC+StLF6o5ktMbNeM4vzfjYAEJsFNU7kffsB73nbLv/9\nm5/2noPuq11y5YrK99deXrtuKKbELusys6GS9kv6sHPuYEi6XM/XL8DlCGlXIXG0YbZFuaxLkqZd\nIe3dX3Vsf5ciaMi61h29wvYH5R3ptpxc1pUr7XBZ1zxJu8KCNQC0i5/cPXjbvKXhx3SFLDUqSWM/\nHr5/2arw/UC5JAP2YvkMhwNAKqaHrxA2acLgbY/VWBb0aI2beRw7Eb5/bSP/Q57f18BByINEAraZ\njZD0SUn/mET+AFC3jvENHZbUjPGrbmrwwM5xsdYD2dGRRKbOuZOS+FcFAAG+vzXtGiBrWOkMAPpN\n7Eq3/JnnpVs+2hs3/0hY2t9v0pihmn15b8NB7VdjtnijQ+Af+YAX8Pful365r7E8as4QnzH432Le\n208qxN9gpFniiQyJA0BWhV2KNX9Wc/fLvuwGacuzweUCYQjYAIpl8p3SvvAZX8e2SmPmeK8PbpEm\nVA2VX3eLdM8j0YucNV3avk56/K6BbXv3e9d+S9KBKGuTT/lm9AKRSwyJJyzt7zdpDMdlX97b0Lf9\nagyLS14vu9Tr3bRFWrwyPH09vvs1afFlg8sJ5TMcLuW//aRC/A1GGhInYCcs7e83afxnkX15b0Pf\n9jt1WNrtc+F1lajnsxfOlq5fKM2ZIR09If10t3TreunneyLUL0qwPr8v8HKuvLefVIi/Qc5hA4Cv\nzu6GD9282gvQQcaOkqZNkq6eV7l9+wvSJZ9rsFCuvYboYScu7e83afy6z768t2Fo+0UcGu/skN55\ndvD2yHWo6kV3zpROn2luKPzdeuS8/aRC/A3SwwaAUDNcpKBdCtaNXvJVftyZ56VTz0XMq0awRrGw\ncAqAYptae0Fv6wkOsLcskY4+5fWWS4+TO7ztfoZcFDFYT/1ehEQoEobEE5b295s0huOyL+9tGKn9\nAnrZ1YH1yjnSg3c2XpfFK70Z5+UCh8Uj9q7z3n5SIf4GmSXeDtL+fpPGfxbZl/c2jNx+u0ZI7u2K\nTdYj9T0pjRtdmXTkbOnNk9Hr0DVKeuPHldu+vkG6+S6fgD11o9S1KHLeeW8/qRB/g5zDBoDILuyP\nwFW97Y4h0tQrpFf2N571keOVvfVfPTK4py2Jc9YIxTlsAChXFjRdr/TQtuaCtZ9zF3jXbVf0rgnW\nqIEh8YSl/f0mjeG47Mt7GzbcfqeOSLtbcP3z+Yeaui487+0nFeJvMNKQOD1sAPDT2eX1eqesSSb/\nKWu9/JsI1igWetgJS/v7TRq/7rMv720Ya/tFuGa7ppiHvvPeflIh/gbpYQNArGa4gcf0o4N2r/Dr\njJ//euVxQIPoYScs7e83afy6z768tyHtl30FaEN62AAA5AUBGwCADCBgAwCQAe2w0lmfpF+1sLzx\n/WW2RErnl1r6GVOQ9zak/WJE+8Wu5Z+vAG14bpREqU86azUz641ycj/L8v4Z+XzZxufLtrx/Pql9\nPyND4gAAZAABGwCADChiwP5O2hVogbx/Rj5ftvH5si3vn09q089YuHPYAABkURF72AAAZA4BGwCA\nDChUwDazT5nZv5nZy2b2V2nXJ05m9ndmdsjMfpZ2XZJgZlPM7Ckz+4WZvWRmX0y7TnEzs+Fm9ryZ\nvdj/Gb+Sdp3iZmZDzOyfzeyRtOuSBDN7xcz+xcxeMLPetOsTNzMbY2b/YGb/2v+3+Edp1ykuZvah\n/nYrPY6b2bK061WuMOewzWyIpP9P0icl7ZP0T5IWO+d+nmrFYmJmsyW9Kem/OefOS7s+cTOz90p6\nr3Nul5mNlLRT0pV5aT9JMm91iLOdc2+aWaek7ZK+6Jx7NuWqxcbMlkvqkTTKObcg7frEzcxekdTj\nnMvlwilmdo+knzjn7jazoZJGOOeOpV2vuPXHi9ckzXTOtXJhr1BF6mFfJOll59we59w7kjZJ+nTK\ndYqNc+5pSUfSrkdSnDxppZQAAAJ3SURBVHOvO+d29b8+IekXkialW6t4Oc+b/W87+x+5+UVtZpMl\nXS7p7rTrgvqZ2ShJsyWtkyTn3Dt5DNb9PiHpl+0UrKViBexJkl4te79POfsPvyjM7P2SPirpuXRr\nEr/+IeMXJB2S9CPnXJ4+4zckfUnS/0i7IglykraY2U4zW5J2ZWI2TdJhSev7T2vcbWZnp12phCyS\ntDHtSlQrUsD2W4w2N72XojCz90h6QNIy59zxtOsTN+fcGefcBZImS7rIzHJxesPMFkg65JzbmXZd\nEjbLOXehpHmS/lP/qaq86JB0oaS/dc59VNJbknI1F0iS+of6r5D0vbTrUq1IAXufpCll7ydL2p9S\nXdCA/vO6D0i61zn3j2nXJ0n9Q41bJX0q5arEZZakK/rP8W6SdKmZ/X26VYqfc25///MhSQ/KOxWX\nF/sk7Ssb9fkHeQE8b+ZJ2uWcO5h2RaoVKWD/k6QPmtnU/l9QiyRtTrlOiKh/QtY6Sb9wzq1Ouz5J\nMLNuMxvT//osSXMl/Wu6tYqHc+5m59xk59z75f3t/dg595mUqxUrMzu7f0Kk+oeK/0RSbq7acM4d\nkPSqmX2of9MnJOVm0meZxWrD4XCpPW6v2RLOudNmdoOkxyUNkfR3zrmXUq5WbMxso6Q5ksab2T5J\nX3bOrUu3VrGaJekaSf/Sf45XklY6536QYp3i9l5J9/TPUP09Sfc753J5+VNOTZT0YP+tIDskfdc5\n91i6VYrdFyTd29/p2SPp+pTrEyszGyHvSqL/mHZd/BTmsi4AALKsSEPiAABkFgEbAIAMIGADAJAB\nBGwAADKAgA0AQAYQsAEAyAACNgAAGfD/A/bi5prAG3H5AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x22a2b8436a0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_NQueens(solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets' see if we can find a different solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAewAAAHwCAYAAABkPlyAAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAIABJREFUeJzt3X+4FNWd7/vPd9gbEMOvDRtMgGtg\nkifnTowY2SPOELnEkDEgGD137gxco0dzczk39xiC4GRGnmeemDwnmqsCIXHu5OTIgOeMAc04RtRE\niUYwYNTZMMrEZOY+BkxE5McWCCgmAmfdP2q3u7t3VXV1d1VXV9X79Tz9dHfVqrVW92Lz7bVq1Spz\nzgkAALS330u7AgAAoDYCNgAAGUDABgAgAwjYAABkAAEbAIAMIGADAJABBGwAADKAgA0AQAYQsIE2\nY2bvN7MfmNlRMztgZneZWUdI+jFm9rf9aU+a2b+Y2X9oZZ0BJI+ADbSf/1fSIUnvlXSBpP9F0v/t\nl9DMhkp6QtK5kv5I0mhJfyHpdjNb2pLaAmgJAjbQfqZKut8591vn3AFJj0n6cEDaayT9T5L+N+fc\nXufcKefcY5KWSvrPZjZSkszMmdkHSgeZ2QYz+89l7xeY2QtmdszMnjGz88v2vc/MHjCzw2a2t/yH\ngJndYmb3m9l/M7MTZvaSmfWU7f9LM3utf9+/mdkn4vmKgOIhYAPtZ62kRWY2wswmSZonL2j7+aSk\nHzrn3qra/oCkEZIurlWYmV0o6e8k/UdJ4yT9F0mbzWyYmf2epIclvShpkqRPSFpmZpeVZXGFpE2S\nxkjaLOmu/nw/JOkGSX/onBsp6TJJr9SqDwB/BGyg/WyT16M+LmmfpF5J3w9IO17S69UbnXOnJfVJ\n6o5Q3v8p6b84555zzp1xzt0j6Xfygv0fSup2zn3VOfeOc26PpP8qaVHZ8dudcz9wzp2R9N8lTe/f\nfkbSMEl/YGadzrlXnHO/jFAfAD4I2EAb6e/RPi7pHyWdLS8gj5X0/wQc0ifvXHd1Ph39xx6OUOy5\nklb0D4cfM7NjkqZIel//vvdV7VspaWLZ8QfKXp+UNNzMOpxzL0taJukWSYfMbJOZvS9CfQD4IGAD\n7aVLXrC8yzn3O+fcG5LWS5ofkP4JSfPM7Oyq7f+rpFOSnu9/f1LeEHnJOWWvX5X0NefcmLLHCOfc\nxv59e6v2jXTOBdWngnPuu865j8kL/E7BPzwA1EDABtqIc65P0l5JnzezDjMbI+k/yDuH7Oe/yxs2\n/17/5WCd/eeXvynpdufcb/rTvSDpfzezIWb2KXkzz0v+q6T/y8xmmudsM7u8f8La85KO908eO6v/\n+PPM7A9rfRYz+5CZXWpmwyT9VtLb8obJATSAgA20n38v6VPyhrNflnRa0o1+CZ1zv5M0V15P+Dl5\nQfExSd+Q9JWypF+UtFDSMUlXq+ycuHOuV9557LskHe0v87r+fWf6j7tA3g+JPkl3y7t8rJZhkr7e\nf8wBSRPkDacDaIA559KuA4CYmFmnpB9Kek3SdY4/cCA36GEDOeKcOyXv/PUvJX0o5eoAiBE9bAAA\nMoAeNgAAGRB4Q4FWGT9+vHv/+9+fdjUSs3PnzrSrkKgZM2akXYXE0YbZRvtlX97bUFKfc67mIkep\nD4n39PS43t7eVOuQJDNLuwqJSvvfTyvQhtlG+9VpZwzf14x465T3NpS00znXUysRQ+IAUHQH7/AC\ndRzBWhrI6+CqePKDJAI2ABTXqTe8wLrvS8nkv+8mL/9TB5PJv2BSP4cNAEhBXL3pKHb3r4Qb81B5\n0dDDBoCiaWWwbodyc4KADQBFsWtY+kFzp0lHNqVbh4wiYANAEew0yb3TdDY33B5DXfYuTv+HQwZx\nDhsA8m7X8KazsLKLjv7mfu/ZNXtF7q5h0oW/azKT4qCHDQB552oHxe650r0/9N9nAVcIB22PLIYe\nf5EQsAEgz2oMPVuP9+g7Jn3mr5sPwqX8So/z/qy5+mEAARsA8qpGMPzWff7bGw3afse9tCfCgQTt\nSAjYAJBHpw/VTLL0jhbUQxF/AJzuS7weWUfABoA8enFibFkFTS5retJZuRdr3vui8JglDgB58/rA\ntVd+vdtSoHW90Ye/Xa904qQ0arZ0/Glp5Ijo1Vn/5YHXYfXRgTXSOTdGz7hg6GEDQN7s/0tJwcF4\nX9lo+azpg/cH9ZxLQTooWAcdd91C7/nXB/z3v1vP15b7J4AkAjYAFM6U+QOvt6+rDLRhw9wfvMp7\nHndpcJrqvMrfn7ugvnqiEgEbAPKkyRnXr4XMVXv5Ve/5yPHgNGH7ImHGeCACNgAUzPxZwfsmzw/e\nF0VY73vBJc3lXXQEbADIqZM7/Lc/ura19Sh5eI3/9refaW09soqADQB5capyVtdZw7xzyGcNG9gW\n5VKsDQ83VvxD22qnKS9/xHDv/fChVYlOHW6sAjlHwAaAvNj9Xt/NJ3dIp57zXke5jOv6rwzedvpM\n5fu+Y4PTXLmidt6l8o9tld7aHpBo94TaGRUQARsACqBjSHPHD7248n333ObyG/2e5o4vIgI2ABRM\nlF72opWV750LT//Zr8ZTLoIRsAEAg9y3pb706zcnUw8MSCRgm9mnzOzfzOxlM/urJMoAAFRavjp6\n2lb3duspr57PUSSxB2wzGyLpbyTNk/QHkhab2R/EXQ4AoNLqmFf2/Pxt0dLFfdevuD9HXiTRw75I\n0svOuT3OuXckbZL06QTKAQA0YcGy8P3ffsB73rbLf//mp73noPtql1TPHr/28tp1w2BJBOxJkl4t\ne7+vf9u7zGyJmfWaWe/hw1xvBwCtMPV9le8fDbqsqsqcJf7bPx2xJ1x9ffY9PpeNobYkArbfQrAV\n8wudc99xzvU453q6u7kHKgC0wk/uHrxt3tLwY7pClhqVpLEfD9+/bFX4fkSXRMDeJ2lK2fvJkvYn\nUA4AoNz08BHLST7rkTxWY1nQozVu5nHsRPj+tRvD9/s6v6+Bg/IviYD9T5I+aGZTzWyopEWSmPAP\nAEnrGN/QYUnNGL/qpgYP7BwXaz3yoiPuDJ1zp83sBkmPSxoi6e+ccy/FXQ4AoL19f2vaNciX2AO2\nJDnnfiDpB0nkDQBo3MQu6eCR9MqfeV56ZWcdK50BQJ7MCF9D9ECdK5iV+8gHpLkXSb8/ufE8nt1Q\nI0GN+hdZIj1sAED7cr3B563nz2ruftmX3SBteTa4XDSOgA0AeTP5Tmlf+IyvY1ulMXO81we3SBO6\nKvdfd4t0zyPRi5w1Xdq+Tnr8roFte/dL067wXkfq2U/5ZvQCC4ghcQDIm4m1b0xdur2l6/WC9aYt\nXq+79KgnWEvSjhcrj9/4uLdQS6lXPbEr/HhJ0oQv1FdowZirdc+0hPX09Lje3vyOk5j5rSOTH2n/\n+2kF2jDbCtt+pw5Lu30uvK4S9ZKuhbOl6xdKc2ZIR09IP90t3bpe+vmeCHWM8l/8+X2Bl3PlvQ0l\n7XTO1WwJhsQBII86G19FcvNqL0AHGTtKmjZJunpe5fbtL0iXfK7BQrn2uiYCNgDk1Qwn7QzvnZYm\noHV2SO9UTRarZ0EV1yt97IKB3nTnTOn0mYi9a2aGR0LABoA8ixC0pYFg3eiqZ+XHnXleOvVcxLwI\n1pEx6QwA8m5q7QW9S5PF/NyyRDr6lNdbLj1O7vC2+xlyUcRgPfV7ERKhhElnCcv7ZIm0//20Am2Y\nbbRfv4BednVgvXKO9OCdjddn8Upvxnm5wGHxiL3rvLehmHQGAHjXDCftGiG5twft6ntSGje6ctvI\n2dKbJ6Nn3zVKeuPH0sZbvYckfX2DdPNdPomnbpS6FkXPHJII2ABQHBf2R+Cq3nbHEGnqFdIrTdwI\n+cjxyt76rx4Z3NOWxDnrJnAOGwCKpixoul7poW3NBWs/5y7wrtuuGA4nWDeFHjYAFNEMJ506Iu0e\np2svl669PMGyzj/U1HXh8NDDBoCi6uzyAveUNcnkP2Wtlz/BOhb0sAGg6CYs8x5SpGu2a2LoOxH0\nsAEAA2a4gcf0o4N2r/DrjJ//euVxSAQ9bACAv44xgwLwqr9PqS6ghw0AQBYQsAEAyAACNgAAGUDA\nBgAgA1K/+YeZ5XpKYdrfb9IKsCg/bZhxtF/2FaANI938gx422tKYkZW38nO90vKrB287Z1zaNQWA\n1qCHnbC0v9+kxfnrPvAWfHWIdA/eOtGG2Ub7ZV8B2pAeNtrfTdcM9JbjUN4bB4A8oYedsLS/36Q1\n+uu+dO/cpE38E+nQkebyoA2zjfbLvgK0YaQeNiudoeXi6k1HcbD/frxJDJUDQCsxJI6WamWwbody\nASAuBGy0xG+fST9oul7pzz+Zbh0AoFEEbCTO9UrDhjafzw23N5/HptvS/+EAAI1g0lnC0v5+k1Zr\nwsvbO6Thw5osw+f8c7NB93fvSMP/OFraordh1tF+2VeANuSyLqQvSrDunivd+0P/fUGTxZqdRBZH\njx8AWokedsLS/n6TFvbrvlYvOErPOSww10r74WnSz+6vvw6DyilwG+YB7Zd9BWhDethIT61g/a37\n/Lc32nP2O+6lPbWP43w2gKwgYCN23V210yy9I/l6SNF+AIwbnXw9AKBZBGzE7tCW+PIK6gHH2TPu\nezK+vAAgKax0hlj9xTUDr8POUbve6MPfrlc6cVIaNVs6/rQ0ckT0+qz/crT6LFssfWNj9HwBoNXo\nYSNWt3/Rew4KxvsODbyeNX3w/qCecylIBwXroOOuW+g9//qA//5SPdes8N8PAO2CgI2WmjJ/4PX2\ndZWBNmyY+4NXec/jLg1OU51X+ftzF9RXTwBoNwRsxKbZ88qvHQre9/Kr3vOR48FpwvZFwYxxAO2M\ngI2Wmj8reN/k+cH7ogjrfS+4pLm8ASBtBGwk4uQO/+2Prm1tPUoeXuO//e1nWlsPAGgUARuxmDiu\n8v1Zw7wh5rPKliaNMuS84eHGyn9oW+005eWPGO69H161ROn4MY2VDwBJY2nShKX9/SattCxiWDA+\nfUbqnKnAdNUzyqvTlB8vSYefGBxYa+VRnubYVmn0e4LrOyivgrRhXtF+2VeANmRpUrSHjiHNHT/0\n4sr33XObyy8sWANAuyJgo6WiLJayaGXl+1o/rj/71XjKBYB2FnvANrO/M7NDZvazuPNGMdxX59Km\n6zcnUw8AaCdJ9LA3SPpUAvmijS1fHT1tq3u79ZRXz+cAgFaKPWA7556WdCTufNHeVi+PN7/P3xYt\nXdx3/Yr7cwBAXDiHjVQsWBa+/9sPeM/bdvnv3/y09xx0X+2SK6vWCL/28tp1A4B2lErANrMlZtZr\nZiwGWRBT31f5/tHt0Y6bs8R/+6cj9oSrr8++5yvRjgOAdpNKwHbOfcc51xPlujPkw0/uHrxt3tLw\nY7pClhqVpLEfD9+/bFX4fgDIEobEEYvxnwjfP2nC4G2P1VgW9GiNm3kcOxG+f20D97cOW48cANKU\nxGVdGyX9VNKHzGyfmf0fcZeB9vPGbxo7LqkZ41fd1Nhxzd7xCwCS0hF3hs65xXHnCdTr+1vTrgEA\nxIshcbTMxK50y595XrrlA0AzuPlHwtL+fpNWfeOBWnfkanQI/CMf8AL+3v3SL/c1lkejdStaG+YN\n7Zd9BWjDSDf/iH1IHAjjeoMD4/xZzd0v+7IbpC3PBpcLAFlGwEasVqyRVt0YnubYVmnMHO/1wS3S\nhKqh8utuke55JHqZs6ZL29dJj981sG3vfmnaFd7rAxHWJv9CzCumAUDcGBJPWNrfb9L8huOi9Gat\nZyDdpi3S4pXh6evx3a9Jiy8bXE6t+gQpYhvmCe2XfQVow0hD4gTshKX9/SbN7z+L8WOkw09EODbi\n+eyFs6XrF0pzZkhHT0g/3S3dul76+Z7ax0YJ1uMuDb+cq4htmCe0X/YVoA05h4109B1r/NjNq70A\nHWTsKGnaJOnqeZXbt78gXfK5xsrk2msAWUAPO2Fpf79JC/t1H3UourNDeufZwdujqi6nc6Z0+kzz\nQ+Hv5l/gNswD2i/7CtCG9LCRrqjnj0vButFLvsqPO/O8dOq5aHm1+r7cANAMFk5BohbdXDuN9QQH\nz1uWSEef8gJ/6XFyh7fdz5CLogXiP/1S7TQA0E4YEk9Y2t9v0qIMxwX1sqsD65VzpAfvbLwui1d6\nM84bKTsMbZhttF/2FaANmSXeDtL+fpMW9T+Lt7ZLI4ZXHdsj9T0pjRtduX3kbOnNk9Hr0DVKeuPH\nldu+vkG6+a7BAXvRzdJ9P4qet0QbZh3tl30FaEPOYaN9nP0x77k6gHYMkaZeIb2yv/G8jxyv7DH/\n6pHBPW2Jc9YAso1z2Gip8qDpeqWHtjUXrP2cu8C7brv8xwHBGkDWMSSesLS/36Q1Ohw3dqR05KmY\nK+Oje25z14VLtGHW0X7ZV4A2jDQkTg8bqTh6wuv1LluVTP5L7+g/R95ksAaAdkEPO2Fpf79Ji/PX\nfRx31Epi6Js2zDbaL/sK0Ib0sJEtpeuxrWfgbl7lVqwZvO2cyyqPA4C8ooedsLS/36Tx6z778t6G\ntF/2FaAN6WEDAJAXBGwAADKAgA0AQAakvtLZjBkz1Nsbw/TgNpX380t5P7ck0YZZR/tlX97bMCp6\n2AAAZEDqPezY7IzhF9iM/P9SBQBkU7Z72Afv8AJ1HMFaGsjrYELLbwEA0KBsBuxTb3iBdd+Xksl/\n301e/qcOJpM/AAB1yt6QeFy96Sh2n+M9M1QOAEhZtnrYrQzW7VAuAAD9shGwdw1LP2juNOnIpnTr\nAAAorPYP2DtNcu80nc0Nt8dQl72L0//hAAAopPY+h71reNNZlN/B6W/u956bvo3jrmHShb9rMhMA\nAKJr7x62qx0Uu+dK9/7Qf1/Q7Rabvg1jDD1+AADq0b4Bu8bQc+n+x33HpM/8dfNBuPyeytYjnfdn\nzdUPAIA4tWfArhEMv3Wf//ZGg7bfcS/tiXAgQRsA0CLtF7BPH6qZZOkdLaiHIv4AON2XeD0AAGi/\ngP3ixNiyCppc1vSks3IvdseYGQAA/tprlvjrA9de+fVuS4HW9UYf/na90omT0qjZ0vGnpZEjoldn\n/ZcHXofVRwfWSOfcGD1jAADq1F497P1/KSk4GO8rGy2fNX3w/qCecylIBwXroOOuW+g9//qA//53\n6/nacv8EAADEpL0Cdg1T5g+83r6uMtCGDXN/8CrvedylwWmq8yp/f+6C+uoJAEDc2idgNznj+rWQ\nuWovv+o9HzkenCZsXyTMGAcAJKh9AnYE82cF75s8P3hfFGG97wWXNJc3AADNasuAfXKH//ZH17a2\nHiUPr/Hf/vYzra0HAKC42iNgn6qc1XXWMO8c8lnDBrZFuRRrw8ONFf/QttppyssfMdx7P3xoVaJT\nhxurAAAANbRHwN79Xt/NJ3dIp57zXke5jOv6rwzedvpM5fu+Y4PTXLmidt6l8o9tld7aHpBo94Ta\nGQEA0ID2CNghOoY0d/zQiyvfd89tLr/R72nueAAAGtH2AbtclF72opWV750LT//Zr8ZTLgAAScpU\nwI7ivi31pV+/OZl6AAAQp9gDtplNMbOnzOwXZvaSmX2x1jHLV9eRf4t7u/WUV8/nAACgHkn0sE9L\nWuGc+58lXSzpP5nZH4QdsDrmlT0/f1u0dHHf9SvuzwEAQEnsAds597pzblf/6xOSfiFpUpxlLFgW\nvv/bD3jP23b579/8tPccdF/tkurZ49deXrtuAAAkIdFz2Gb2fkkflfRc1fYlZtZrZr2HD9e+dnnq\n+yrfPxp0WVWVOUv8t386Yk+4+vrse3wuGwMAoBUSC9hm9h5JD0ha5pyrWKnbOfcd51yPc66nu7v2\n/aR/cvfgbfOWhh/TFbLUqCSN/Xj4/mWrwvcDANBKiQRsM+uUF6zvdc79Y80Dpof3sif5rEfyWI1l\nQY/WuJnHsRPh+9duDN/v6/y+Bg4CAKC2JGaJm6R1kn7hnIs2b7pjfGNlJTRj/KqbGjywc1ys9QAA\noCSJHvYsSddIutTMXuh/NHkvrdb6/ta0awAAQKWOuDN0zm2XFPvNoSd2SQePxJ1rdDPPS69sAADa\nZ6WzGeFriB6ocwWzch/5gDT3Iun3Jzeex7MbaiSoUX8AAJoRew87Sa43+Lz1/FnN3S/7shukLc8G\nlwsAQJraK2BPvlPaFz7j69hWacwc7/XBLdKErsr9190i3fNI9CJnTZe2r5Mev2tg29790rQrvNeR\nevZTvhm9QAAAGtA+Q+KSNLH2jalLt7d0vV6w3rTF63WXHvUEa0na8WLl8Rsf9xZqKfWqJ3aFHy9J\nmvCF+goFAKBO5mrdfzJhPT09rre3bMz51GFpt8+F11WiXtK1cLZ0/UJpzgzp6Anpp7ulW9dLP99T\n+9hIQ+Hn94VezuVd5ZZfaf/7aQXaMNtov+zLextK2umcqxnV2mtIXJI6a698FmTzai9ABxk7Spo2\nSbp6XuX27S9Il3yuwUK59hoA0ALtF7Alb8b1zvBfVKUJaJ0d0jtVk8XqWVDF9Uofu2CgN905Uzp9\nJmLvmpnhAIAWac+ALUUK2tJAsG501bPy4848L516LmJeBGsAQAu116SzalNrL+hdmizm55Yl0tGn\nvN5y6XFyh7fdz5CLIgbrqd+LkAgAgPi036SzagG97OrAeuUc6cE7G6/H4pXejPNygcPidfSu8z5Z\nIu1/P61AG2Yb7Zd9eW9DZXbSWbUZTto1QnJvD9rV96Q0bnTltpGzpTdPRs++a5T0xo+ljbd6D0n6\n+gbp5rt8Ek/dKHUtip45AAAxaf+ALUkX9kfgqt52xxBp6hXSK/sbz/rI8cre+q8eGdzTlsQ5awBA\nqtr7HHa1sqDpeqWHtjUXrP2cu8C7brtiOJxgDQBIWTZ62OVmOOnUEWn3OF17uXTt5QmWdf6hpq4L\nBwAgLtnqYZd0dnmBe8qaZPKfstbLn2ANAGgT2ethl5uwzHtIka7ZromhbwBAm8pmD9vPDDfwmH50\n0O4Vfp3x81+vPA4AgDaV7R52kI4xgwLwqr9PqS4AAMQgPz1sAAByjIANAEAGELABAMgAAjYAABmQ\n+s0/zCzX07PT/n6TVoBF+WnDjKP9sq8AbZiTm38AQDs6c1R6oati04o10qobq9Kdv1/qfG/r6oXc\nooedsLS/36Tx6z778t6GsbZfGy7QlPf2kwrxNxiph805bAAIc/AOL1DHEaylgbwOroonPxQGPeyE\npf39Jo1f99mX9zZsuP1OvSHtHh9vZfycf0DqnNjw4XlvP6kQf4OcwwaAhsTVm45i9zneM8sjowaG\nxAGgXCuDdTuUi8wgYAOAJO0aln7Q3GnSkU3p1gFti4ANADtNcu80nc0Nt8dQl72L0//hgLbEpLOE\npf39Jo0JL9mX9zas2X67hkvud02VYT7ThVxvU1lKNlS6sHa98t5+UiH+BrmsCwBqihCsu+dK9/7Q\nf59fsA7bHlkMPX7kCz3shKX9/SaNX/fZl/c2DG2/GkPPUXrOYYG5VtoPT5N+dn9oFWrOHs97+0mF\n+Bukhw0AgWoE62/d57+90Z6z33Ev7YlwIOez0Y+ADaB4Th+qmWTpHS2ohyL+ADjdl3g90P4I2ACK\n58XGVxarFjS5rOlJZ+Ve7I4xM2QVK50BKJbXB669CjtH7XqjD3+7XunESWnUbOn409LIEdGrs/7L\nA69Dz5kfWCOdU30rMBQJPWwAxbL/LyUFB+N9ZaPls6YP3h/Ucy4F6aBgHXTcdQu9518f8N//bj1f\nW+6fAIVBwAaAMlPmD7zevq4y0IYNc3/wKu953KXBaarzKn9/7oL66oniIWADKI4mZ1y/FjJX7eVX\nvecjx4PThO2LhBnjhUbABoAy82cF75s8P3hfFGG97wWXNJc38o+ADaCQTu7w3/7o2tbWo+ThNf7b\n336mtfVA+yJgAyiGU5Wzus4a5p1DPmvYwLYol2JteLix4h/aVjtNefkjhnvvhw+tSnTqcGMVQOax\nNGnC0v5+k8ayiNmX9zZ8t/1Czv+ePiN1zuxP7xO0q2eUV6cpP16SDj8hjR9TXx7laY5tlUa/J7C6\nFcuV5r39pEL8DbI0KQBE0TGkueOHXlz5vntuc/mFBmsUFgEbAMpEWSxl0crK97U6gJ/9ajzlothi\nD9hmNtzMnjezF83sJTP7StxlAECa7ttSX/r1m5OpB4oliR727yRd6pybLukCSZ8ys4trHAMAiVq+\nOnraVvd26ymvns+BfIk9YDvPm/1vO/sf+Z4xAKDtrY55Zc/P3xYtXdx3/Yr7cyA7EjmHbWZDzOwF\nSYck/cg591zV/iVm1mtmcd7PBgBis2BZ+P5vP+A9b9vlv3/z095z0H21S65cUfn+2str1w3FlOhl\nXWY2RtKDkr7gnPtZQJpc974LcDlC2lVIHG2YbVEu65KkaVdIe/dXHdvfpQgasq51R6+w/UF5R7ot\nJ5d15UpbXNblnDsmaaukTyVZDgA06yd3D942b2n4MV0hS41K0tiPh+9ftip8P1AuiVni3f09a5nZ\nWZLmSvrXuMsBgLpMD18hbNKEwdseq7Es6NEaN/M4diJ8/9qN4ft9nd/XwEHIg44E8nyvpHvMbIi8\nHwT3O+ceSaAcAIiuY3xDhyU1Y/yqmxo8sHNcrPVAdsQesJ1zuyV9NO58ASBPvr817Roga1jpDAD6\nTexKt/yZ56VbPtobN/9IWNrfb9KYoZp9eW/DQe1XY7Z4o0PgH/mAF/D37pd+ua+xPGrOEJ8x+N9i\n3ttPKsTfYKRZ4kmcwwaAzAq7FGv+rObul33ZDdKWZ4PLBcIQsAEUy+Q7pX3hM76ObZXGzPFeH9wi\nTagaKr/uFumeOqbSzpoubV8nPX7XwLa9+71rvyXpQJS1yad8M3qByCWGxBOW9vebNIbjsi/vbejb\nfjWGxSWvl13q9W7aIi1eGZ6+Ht/9mrT4ssHlhPIZDpfy335SIf4GIw2JE7ATlvb3mzT+s8i+vLeh\nb/udOizt9rnwukrU89kLZ0vXL5TmzJCOnpB+ulu6db308z0R6hclWJ/fF3g5V97bTyrE3yDnsAHA\nV2d3w4duXu0F6CBjR0nTJklXz6vcvv0F6ZLPNVgo115D9LATl/b3mzR+3Wdf3tswtP0iDo13dkjv\nPDt4e+Q6VPWiO2dKp880NxS6nRyyAAAgAElEQVT+bj1y3n5SIf4G6WEDQKgZLlLQLgXrRi/5Kj/u\nzPPSqeci5lUjWKNYWDgFQLFNrb2gt/UEB9hblkhHn/J6y6XHyR3edj9DLooYrKd+L0IiFAlD4glL\n+/tNGsNx2Zf3NozUfgG97OrAeuUc6cE7G6/L4pXejPNygcPiEXvXeW8/qRB/g8wSbwdpf79J4z+L\n7Mt7G0Zuv10jJPd2xSbrkfqelMaNrkw6crb05snodegaJb3x48ptX98g3XyXT8CeulHqWhQ577y3\nn1SIv0HOYQNAZBf2R+Cq3nbHEGnqFdIr+xvP+sjxyt76rx4Z3NOWxDlrhOIcNgCUKwuarld6aFtz\nwdrPuQu867YretcEa9TAkHjC0v5+k8ZwXPblvQ0bbr9TR6TdLbj++fxDTV0Xnvf2kwrxNxhpSJwe\nNgD46ezyer1T1iST/5S1Xv5NBGsUCz3shKX9/SaNX/fZl/c2jLX9IlyzXVPMQ995bz+pEH+D9LAB\nIFYz3MBj+tFBu1f4dcbPf73yOKBB9LATlvb3mzR+3Wdf3tuQ9su+ArQhPWwAAPKCgA0AQAYQsAEA\nyIDUVzqbMWOGenuj3GMum/J+finv55Yk2jDraL/sy3sbRkUPGwCADEi9hw0AQKsE3h2tDo3eF71Z\n9LABALl20zUD9yqPQymv5VfHk19UBGwAQC51jfIC6x1fTCb/VTd6+U/oSib/agyJAwByJ67edBQH\n+2+VmvRQOT1sAECutDJYt7JcAjYAIBd++0x6wbrE9Up//slk8iZgAwAyz/VKw4Y2n88Ntzefx6bb\nkvnhwDlsAECmvb2j+TzKzz//zf3ec7NB97fPSMP/uLk8ytHDBgBk2vBhtdN0z5Xu/aH/vqDJYs1O\nIoujx1+OgA0AyKxavWDr8R59x6TP/HXzQbiUX+lx3p81V796ELABAJlUKxh+6z7/7Y0Gbb/jXtpT\n+7i4gjYBGwCQOd0RFitZekfy9ZCi/QAYN7r5cgjYAIDMObQlvryCesBxDmf3Pdl8HswSBwBkyl9c\nM/Dar3dbCrSuN/rwt+uVTpyURs2Wjj8tjRwRvT7rvxytPssWS9/YGD3favSwAQCZcnv/2uBBwXjf\noYHXs6YP3h/Ucy4F6aBgHXTcdQu9518f8N9fqueaFf77oyJgAwByZcr8gdfb11UG2rBh7g9e5T2P\nuzQ4TXVe5e/PXVBfPetFwAYAZEaz55VfOxS87+VXvecjx4PThO2Lopn6E7ABALkyf1bwvsnzg/dF\nEdb7XnBJc3nXQsAGAGTSyYAlSR9d29p6lDy8xn/728/Ekz8BGwCQCRPHVb4/a5g3xHxW2dKkUYac\nNzzcWPkPbaudprz8EcO998OrligdP6ax8gnYAIBMOPC4//aTO6RTz3mvo1zGdf1XBm87fabyfd+x\nwWmujDDLu1T+sa3SW9v90xx+onY+fgjYAIDM6xjS3PFDL6583z23ufxGv6e54/0QsAEAuRKll71o\nZeV758LTf/ar8ZTbjEQCtpkNMbN/NrNHksgfAIBm3Ffn0qbrNydTj3ok1cP+oqRfJJQ3AKCAlq+O\nnjbp3m4z5dXzOcrFHrDNbLKkyyXdHXfeAIDiWr083vw+f1u0dHHf9avRz5FED/sbkr4k6X8EJTCz\nJWbWa2a9hw8fTqAKAICiW7AsfP+3H/Cet+3y37/5ae856L7aJdWzx6+9vHbdGhFrwDazBZIOOed2\nhqVzzn3HOdfjnOvp7u6OswoAgIKa+r7K948GXFZVbc4S/+2fjtgTrr4++x6fy8biEHcPe5akK8zs\nFUmbJF1qZn8fcxkAAAzyE58TsfOWhh/TFbLUqCSN/Xj4/mWrwvfHKdaA7Zy72Tk32Tn3fkmLJP3Y\nOfeZOMsAABTT+E+E7580YfC2x2osC3q0xs08jp0I37+2gftbh61HHobrsAEAmfDGbxo7LqkZ41fd\n1Nhxjd7xq6Oxw2pzzm2VtDWp/AEASNP3t7a2PHrYAIDcmNiVbvkzz0subwI2ACAzag1vH6hzBbNy\nH/mANPci6fcnN57HsxvC9zczPJ/YkDgAAGlwvcGBcf6s5u6XfdkN0pZng8tNEgEbAJApK9ZIq24M\nT3NsqzRmjvf64BZpQtVQ+XW3SPfUcbeLWdOl7eukx+8a2LZ3vzTtCu91lJ79F5pcMc1crVuUJKyn\np8f19ib8syRFZpZ2FRKV9r+fVqANs432yz6/NozSm7WegXSbtkiLV4anr8d3vyYtvmxwObXqE2Cn\nc67mYDkBO2H8Z5F9tGG20X7Z59eG48dIh5+IcGzEc8YLZ0vXL5TmzJCOnpB+ulu6db308z21j40S\nrMddGno5V6SAzZA4ACBz+o41fuzm1V6ADjJ2lDRtknT1vMrt21+QLvlcY2U2eu11OQI2ACCTogxF\nlyagdXZI71RNFqtnxrbrlT52wUB5nTOl02eaHgqvCwEbAJBZUc8fl4J1o8Gz/Lgzz0unnouWV5yr\nrHEdNgAg0xbdXDuN9QQHz1uWSEef8gJ/6XFyh7fdz5CLogXiP/1S7TT1YNJZwpjwkn20YbbRftkX\npQ2DetnVgfXKOdKDdzZel8UrvRnnjZQdgklnAIBisB7pre3SiOGD9/U9KY0bXblt5GzpzZPR8+8a\nJb3xY2njrd5Dkr6+Qbr5rsFpF90s3fej6HlHRcAGAOTC2R/znqt7vB1DpKlXSK/sbzzvI8cre8y/\nemRwT1tK7s5gEuewAQA5Ux40Xa/00LbmgrWfcxd4122X/zhIMlhL9LABADlkPdLYkdKRp6RrL/ce\nSeme29x14VHRwwYA5NLRE17gXrYqmfyX3uHl34pgLdHDBgDk3NqN3kOK545aSQ99B6GHDQAojNL1\n2NYzcDevcivWDN52zmWVx6WFHjYAoJB+86Z/AF59b+vrEgU9bAAAMoCADQBABhCwAQDIgNTXEjez\nXC+Em/b3m7S8r9Ms0YZZR/tlXwHaMNJa4vSwAQDIAGaJA4hNlq9xBdodPWwATbnpmoF7CMehlNfy\nq+PJD8gLzmEnLO3vN2mcP8u+RtuwdLvBpE38E+nQkcaPp/2yrwBtyP2wASQjrt50FAf7b2HIUDmK\njiFxAHVpZbBuh3KBdkHABhDJb59JP2i6XunPP5luHYC0ELAB1OR6pWFDm8/nhtubz2PTben/cADS\nwKSzhKX9/SaNCS/ZV6sN394hDR/WZBk+55+bDbq/e0ca/se10xW9/fKgAG3IwikAmhclWHfPle79\nof++oMlizU4ii6PHD2QJPeyEpf39Jo1f99kX1oa1esFRes5hgblW2g9Pk352f/11qCijwO2XFwVo\nQ3rYABpXK1h/6z7/7Y32nP2Oe2lP7eM4n42iIGADGKS7q3aapXckXw8p2g+AcaOTrweQNgI2gEEO\nbYkvr6AecJw9474n48sLaFesdAagwl9cM/A67By1640+/O16pRMnpVGzpeNPSyNHRK/P+i9Hq8+y\nxdI3NkbPF8gaetgAKtz+Re85KBjvOzTwetb0wfuDes6lIB0UrIOOu26h9/zrA/77S/Vcs8J/P5AX\nBGwAdZkyf+D19nWVgTZsmPuDV3nP4y4NTlOdV/n7cxfUV08gbwjYAN7V7Hnl1w4F73v5Ve/5yPHg\nNGH7omDGOPKMgA2gLvNnBe+bPD94XxRhve8FlzSXN5B1BGwAvk7u8N/+6NrW1qPk4TX+299+prX1\nANJCwAYgSZo4rvL9WcO8IeazypYmjTLkvOHhxsp/aFvtNOXljxjuvR9etUTp+DGNlQ+0O5YmTVja\n32/SWBYx+0ptGBaMT5+ROmcqMF31jPLqNOXHS9LhJwYH1lp5lKc5tlUa/Z7g+pbnVZT2y7MCtCFL\nkwKIR8eQ5o4fenHl++65zeUXFqyBvCJgA6hLlMVSFq2sfF+rg/TZr8ZTLpBniQRsM3vFzP7FzF4w\nMy60AArmvjqXNl2/OZl6AHmSZA/74865C6KMywNI3/LV0dO2urdbT3n1fA4gSxgSByBJWr083vw+\nf1u0dHHf9SvuzwG0i6QCtpO0xcx2mtmS6p1mtsTMehkuB7JrwbLw/d9+wHvetst//+anveeg+2qX\nXFm1Rvi1l9euG5BHiVzWZWbvc87tN7MJkn4k6QvOuacD0uZ6vn4BLkdIuwqJK0ob1rrGetoV0t79\nldtKxwQNWde6o1fY/qC8o1wLzmVd+VKANkzvsi7n3P7+50OSHpR0URLlAGidn9w9eNu8peHHdIUs\nNSpJYz8evn/ZqvD9QJHEHrDN7GwzG1l6LelPJP0s7nIAxGv8J8L3T5oweNtjNZYFPVrjZh7HToTv\nX9vA/a3D1iMHsqwjgTwnSnqwf5imQ9J3nXOPJVAOgBi98ZvGjktqxvhVNzV2XLN3/ALaVewB2zm3\nR5LPbe0BILrvb027BkB74bIuAJFN7Eq3/JnnpVs+kCZu/pGwtL/fpDFDNfuq27DWLOxGh8A/8gEv\n4O/dL/1yX2N5NFK3orVfHhWgDSPNEk/iHDaAHAu7FGv+rObul33ZDdKWZ4PLBYqMgA2gwoo10qob\nw9Mc2yqNmeO9PrhFmlA1VH7dLdI9j0Qvc9Z0afs66fG7Brbt3e9d+y1JByKsTf6FmFdMA9oNQ+IJ\nS/v7TRrDcdnn14ZRFycppdu0RVq8Mjx9Pb77NWnxZYPLqVUfP0Vsv7wpQBtGGhInYCcs7e83afxn\nkX1+bTh+jHT4iQjHRjyfvXC2dP1Cac4M6egJ6ae7pVvXSz/fU/vYKMF63KXBl3MVsf3ypgBtyDls\nAI3pO9b4sZtXewE6yNhR0rRJ0tXzKrdvf0G65HONlcm11ygCetgJS/v7TRq/7rMvrA2jDkV3dkjv\nPDt4e1TV5XTOlE6faW4o/N28C9x+eVGANqSHDaA5Uc8fl4J1o5d8lR935nnp1HPR8mr1fbmBNLFw\nCoBQi26uncZ6goPnLUuko095gb/0OLnD2+5nyEXRAvGffql2GiBPGBJPWNrfb9IYjsu+KG0Y1Muu\nDqxXzpEevLPxuixe6c04b6TsILRf9hWgDZkl3g7S/n6Txn8W2Re1Dd/aLo0YXnVsj9T3pDRudOX2\nkbOlN09Gr0PXKOmNH1du+/oG6ea7BgfsRTdL9/0oet60X/YVoA05hw0gPmd/zHuuDqAdQ6SpV0iv\n7G887yPHK3vMv3pkcE9b4pw1io1z2ADqUh40Xa/00LbmgrWfcxd4122X/zggWKPoGBJPWNrfb9IY\njsu+Rttw7EjpyFMxV8ZH99zmrgun/bKvAG0YaUicHjaAhhw94fV6l61KJv+ld/SfI28iWAN5Qg87\nYWl/v0nj1332xdmGcdxRK+6hb9ov+wrQhvSwAbRW6Xps6xm4m1e5FWsGbzvnssrjAPijh52wtL/f\npPHrPvvy3oa0X/YVoA3pYQMAkBcEbAAAMoCADQBABqS+0tmMGTPU2xvD1NI2lffzS3k/tyTRhllH\n+2Vf3tswKnrYAABkAAEbAIAMSH1IHNG146IUAIDWoIfd5m66xgvUcQRraSCv5VfHkx8AoDUI2G2q\na5QXWO/4YjL5r7rRy39CVzL5AwDixZB4G4qrNx3Fwf57DjNUDgDtjR52m2llsG6HcgEA0RCw28Rv\nn0k/aLpe6c8/mW4dAAD+CNhtwPVKw4Y2n88Ntzefx6bb0v/hAAAYjHPYKXt7R/N5lJ9//pv7vedm\ng+5vn5GG/3FzeQAA4kMPO2XDh9VO0z1XuveH/vuCJos1O4ksjh4/ACA+BOwU1eoFW4/36Dsmfeav\nmw/CpfxKj/P+rLn6AQBah4CdklrB8Fv3+W9vNGj7HffSntrHEbQBoD0QsFPQHWGxkqV3JF8PKdoP\ngHGjk68HACAcATsFh7bEl1dQDzjOnnHfk/HlBQBoDLPEW+wvrhl47de7LQVa1xt9+Nv1SidOSqNm\nS8eflkaOiF6f9V+OVp9li6VvbIyeLwAgXvSwW+z2/rXBg4LxvkMDr2dNH7w/qOdcCtJBwTrouOsW\nes+/PuC/v1TPNSv89wMAWoOA3WamzB94vX1dZaANG+b+4FXe87hLg9NU51X+/twF9dUTANBaBOwW\nava88muHgve9/Kr3fOR4cJqwfVEwYxwA0kPAbjPzZwXvmzw/eF8UYb3vBZc0lzcAIFkE7JScDFiS\n9NG1ra1HycNr/Le//Uxr6wEA8EfAbpGJ4yrfnzXMG2I+q2xp0ihDzhsebqz8h7bVTlNe/ojh3vvh\nVUuUjh/TWPkAgOYQsFvkwOP+20/ukE49572OchnX9V8ZvO30mcr3fccGp7kywizvUvnHtkpvbfdP\nc/iJ2vkAAOJHwG4DHUOaO37oxZXvu+c2l9/o9zR3PAAgfokEbDMbY2b/YGb/ama/MLM/SqKcPIrS\ny160svK9c+HpP/vVeMoFAKQnqR72WkmPOef+naTpkn6RUDmFdF+dS5uu35xMPQAArRN7wDazUZJm\nS1onSc65d5xzPmdVi2X56uhpW93brae8ej4HACA+SfSwp0k6LGm9mf2zmd1tZmcnUE6mrF4eb36f\nvy1aurjv+hX35wAARJNEwO6QdKGkv3XOfVTSW5L+qjyBmS0xs14z6z18+HACVci+BcvC93/7Ae95\n2y7//Zuf9p6D7qtdUj17/NrLa9cNANB6SQTsfZL2Oef6L1bSP8gL4O9yzn3HOdfjnOvp7u5OoArZ\nM/V9le8fDbisqtqcJf7bPx2xJ1x9ffY9PpeNAQDSF3vAds4dkPSqmX2of9MnJP087nLy5id3D942\nb2n4MV0hS41K0tiPh+9ftip8PwCgfSQ1S/wLku41s92SLpB0a0LlZMb4T4TvnzRh8LbHaiwLerTG\nzTyOnQjfv7aB+1uHrUcOAEhORxKZOudekMSVvWXe+E1jxyU1Y/yqmxo7rtk7fgEAGsNKZwX1/a1p\n1wAAUA8CdhuZ2JVu+TPPS7d8AEAwAnYL1RrePlDnCmblPvIBae5F0u9PbjyPZzeE72f5UgBITyLn\nsNE41xscGOfPau5+2ZfdIG15NrhcAED7ImC32Io10qobw9Mc2yqNmeO9PrhFmlA1VH7dLdI9j0Qv\nc9Z0afs66fG7Brbt3S9Nu8J7HaVn/4WYV0wDANTHXK1bPSWsp6fH9fbmt3tnZoO2RenNWs9Auk1b\npMUrw9PX47tfkxZfNricWvXxk/a/n1bwa8M8yXsb0n7Zl/c2lLTTOVfzpCMBO2F+/9DGj5EOPxHh\n2IjnjBfOlq5fKM2ZIR09If10t3Treunne2ofGyVYj7s0+HKutP/9tELe/7PIexvSftmX9zZUxIDN\nkHgK+pq4d9nm1V6ADjJ2lDRtknT1vMrt21+QLvlcY2Vy7TUApI+AnZIoQ9GlCWidHdI7VZPF6pmx\n7Xqlj10wUF7nTOn0meaGwgEArUXATlHU88elYN1o8Cw/7szz0qnnouVFsAaA9sF12ClbdHPtNNYT\nHDxvWSIdfcoL/KXHyR3edj9DLooWiP/0S7XTAABah0lnCYsyWSKol10dWK+cIz14Z+N1WbzSm3He\nSNlB0v730wp5n/CS9zak/bIv720oJp1lh/VIb22XRgwfvK/vSWnc6MptI2dLb56Mnn/XKOmNH0sb\nb/UekvT1DdLNdw1Ou+hm6b4fRc8bANAaBOw2cfbHvOfqHm/HEGnqFdIr+xvP+8jxyh7zrx4Z3NOW\nOGcNAO2Mc9htpjxoul7poW3NBWs/5y7wrtsu/3FAsAaA9kYPuw1ZjzR2pHTkKenay71HUrrnNndd\nOACgNehht6mjJ7zAvWxVMvkvvcPLn2ANANlAD7vNrd3oPaR47qjF0DcAZBM97AwpXY9tPQN38yq3\nYs3gbedcVnkcACCb6GFn1G/e9A/Aq+9tfV0AAMmjhw0AQAYQsAEAyAACNgAAGZD6WuJmluuFcNP+\nfpNWgDV+acOMo/2yrwBtGGktcXrYAABkALPEgVbZGUNPaEa+exoAgtHDBpJ08A4vUMcRrKWBvA4m\ntAQegLbFOeyEpf39Jo3zZwFOvSHtHh9/Zaqdf0DqnNhUFnlvQ/4Gs68Abcj9sIFUxNWbjmL3Od4z\nQ+VA7jEkDsSplcG6HcoF0DIEbCAOu4alHzR3mnRkU7p1AJAYAjbQrJ0muXeazuaG22Ooy97F6f9w\nAJAIJp0lLO3vN2mFn/Cya7jkftdU/n43cWn6Vqo2VLowWr3y3ob8DWZfAdqQhVOAxEUI1t1zpXt/\n6L8v6JanTd8KNYYeP4D2Qg87YWl/v0kr9K/7GkPPUXrOYYG5VtoPT5N+dn9oFSLNHs97G/I3mH0F\naEN62EBiagTrb93nv73RnrPfcS/tiXAg57OB3CBgA/U6fahmkqV3tKAeivgD4HRf4vUAkDwCNlCv\nF5tbWaxc0OSypiedlXuxO8bMAKSFlc6Aerw+cO1V2Dlq1xt9+Nv1SidOSqNmS8eflkaOiF6d9V8e\neB16zvzAGumcG6NnDKDt0MMG6rH/LyUFB+N9ZaPls6YP3h/Ucy4F6aBgHXTcdQu9518f8N//bj1f\nW+6fAEBmELCBGE2ZP/B6+7rKQBs2zP3Bq7zncZcGp6nOq/z9uQvqqyeA7CFgA1E1OeP6tZC5ai+/\n6j0fOR6cJmxfJMwYBzKNgA3EaP6s4H2T5wfviyKs973gkubyBtD+CNhAA07u8N/+6NrW1qPk4TX+\n299+prX1AJAcAjYQxanKWV1nDfPOIZ81bGBblEuxNjzcWPEPbaudprz8EcO998OHViU6dbixCgBI\nHUuTJizt7zdphVkWMeT87+kzUufM/rQ+Qbt6Rnl1mvLjJenwE9L4MfXlUZ7m2FZp9HsCqztoudK8\ntyF/g9lXgDZkaVKgFTqGNHf80Isr33fPbS6/0GANILMI2ECMoiyWsmhl5ftanYfPfjWecgFkW+wB\n28w+ZGYvlD2Om9myuMsBsuq+LfWlX785mXoAyJbYA7Zz7t+ccxc45y6QNEPSSUkPxl0O0ErLV0dP\n2+rebj3l1fM5ALSXpIfEPyHpl865XyVcDpCo1TGv7Pn526Kli/uuX3F/DgCtk3TAXiRpY/VGM1ti\nZr1mFuc9iYC2saDGSaBvP+A9b9vlv3/z095z0H21S65cUfn+2str1w1ANiV2WZeZDZW0X9KHnXMH\nQ9Ller5+AS5HSLsKiat1WZckTbtC2ru/6rj+n6NBQ9a17ugVtj8o70i35eSyrlzJe/tJhWjD1C/r\nmidpV1iwBvLiJ3cP3jZvafgxXSFLjUrS2I+H71+2Knw/gHxJMmAvls9wOJBJ08NXCJs0YfC2x2os\nC3q0xs08jp0I37+2kb+u8/saOAhAO0gkYJvZCEmflPSPSeQPtFzH+IYOS2rG+FU3NXhg57hY6wGg\ndTqSyNQ5d1IS/zMACfn+1rRrAKDVWOkMiMnErnTLn3leuuUDSBY3/0hY2t9v0go3Q7XGbPFGh8A/\n8gEv4O/dL/1yX2N51JwhPsP/32Le25C/wewrQBtGmiWeyJA4UFRhl2LNn9Xc/bIvu0Ha8mxwuQDy\njYAN1GPyndK+8Blfx7ZKY+Z4rw9ukSZUDZVfd4t0zyPRi5w1Xdq+Tnr8roFte/d7135L0oEoa5NP\n+Wb0AgG0JYbEE5b295u0Qg7H1RgWl7xedqnXu2mLtHhlePp6fPdr0uLLBpcTKmA4XMp/G/I3mH0F\naMNIQ+IE7ISl/f0mrZD/WZw6LO32ufC6StTz2QtnS9cvlObMkI6ekH66W7p1vfTzPRHqFiVYn98X\nejlX3tuQv8HsK0Abcg4bSERnd8OHbl7tBeggY0dJ0yZJV8+r3L79BemSzzVYKNdeA7lADzthaX+/\nSSv0r/uIQ+OdHdI7zw7eHrn8ql5050zp9Jnmh8LfrUvO25C/wewrQBvSwwYSNaP2TUGkgWDd6CVf\n5cedeV469VzEvCIEawDZwcIpQDOm1l7Q23qCA+wtS6SjT3m95dLj5A5vu58hF0UM1lO/FyERgCxh\nSDxhaX+/SWM4ToG97OrAeuUc6cE7G6/H4pXejPOKugUNi9fRu857G/I3mH0FaENmibeDtL/fpPGf\nRb9dIyT3dsUm65H6npTGja5MOnK29ObJ6OV3jZLe+HHltq9vkG6+yydgT90odS2Knrny34b8DWZf\nAdqQc9hAy1zYH4GretsdQ6SpV0iv7G886yPHK3vrv3pkcE9bEuesgZzjHDYQp7Kg6Xqlh7Y1F6z9\nnLvAu267ondNsAZyjyHxhKX9/SaN4bgAp45Iu1tw/fP5h5q6LlzKfxvyN5h9BWjDSEPi9LCBJHR2\neb3eKWuSyX/KWi//JoM1gOygh52wtL/fpPHrvg4RrtmuKYGh77y3IX+D2VeANqSHDbSVGW7gMf3o\noN0r/Drj579eeRyAwqKHnbC0v9+k8es++/LehrRf9hWgDelhAwCQFwRsAAAygIANAEAGtMNKZ32S\nftXC8sb3l9kSKZ1faulnTEHe25D2ixHtF7uWf74CtOG5URKlPums1cysN8rJ/SzL+2fk82Ubny/b\n8v75pPb9jAyJAwCQAQRsAAAyoIgB+ztpV6AF8v4Z+XzZxufLtrx/PqlNP2PhzmEDAJBFRexhAwCQ\nOQRsAAAyoFAB28w+ZWb/ZmYvm9lfpV2fOJnZ35nZITP7Wdp1SYKZTTGzp8zsF2b2kpl9Me06xc3M\nhpvZ82b2Yv9n/EradYqbmQ0xs382s0fSrksSzOwVM/sXM3vBzHrTrk/czGyMmf2Dmf1r/9/iH6Vd\np7iY2Yf62630OG5my9KuV7nCnMM2syGS/j9Jn5S0T9I/SVrsnPt5qhWLiZnNlvSmpP/mnDsv7frE\nzczeK+m9zrldZjZS0k5JV+al/STJvNUhznbOvWlmnZK2S/qic+7ZlKsWGzNbLqlH0ijn3IK06xM3\nM3tFUo9zLpcLp5jZPZJ+4py728yGShrhnDuWdr3i1h8vXpM00znXyoW9QhWph32RpJedc3ucc+9I\n2iTp0ynXKTbOuaclHZMOmcMAAAJ8SURBVEm7Hklxzr3unNvV//qEpF9ImpRureLlPG/2v+3sf+Tm\nF7WZTZZ0uaS7064L6mdmoyTNlrROkpxz7+QxWPf7hKRftlOwlooVsCdJerXs/T7l7D/8ojCz90v6\nqKTn0q1J/PqHjF+QdEjSj5xzefqM35D0JUn/I+2KJMhJ2mJmO81sSdqVidk0SYclre8/rXG3mZ2d\ndqUSskjSxrQrUa1IAdtvMdrc9F6KwszeI+kBScucc8fTrk/cnHNnnHMXSJos6SIzy8XpDTNbIOmQ\nc25n2nVJ2Czn3IWS5kn6T/2nqvKiQ9KFkv7WOfdRSW9JytVcIEnqH+q/QtL30q5LtSIF7H2SppS9\nnyxpf0p1QQP6z+s+IOle59w/pl2fJPUPNW6V9KmUqxKXWZKu6D/Hu0nSpWb29+lWKX7Ouf39z4ck\nPSjvVFxe7JO0r2zU5x/kBfC8mSdpl3PuYNoVqVakgP1Pkj5oZlP7f0EtkrQ55Tohov4JWesk/cI5\ntzrt+iTBzLrNbEz/67MkzZX0r+nWKh7OuZudc5Odc++X97f3Y+fcZ1KuVqzM7Oz+CZHqHyr+E0m5\nuWrDOXdA0qtm9qH+TZ+QlJtJn2UWqw2Hw6X2uL1mSzjnTpvZDZIelzRE0t85515KuVqxMbONkuZI\nGm9m+yR92Tm3Lt1axWqWpGsk/Uv/OV5JWumc+0GKdYrbeyXd0z9D9fck3e+cy+XlTzk1UdKD/beC\n7JD0XefcY+lWKXZfkHRvf6dnj6TrU65PrMxshLwrif5j2nXxU5jLugAAyLIiDYkDAJBZBGwAADKA\ngA0AQAYQsAEAyAACNgAAGUDABgAgAwjYAABkwP8PfpHmmmpMFEsAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x22a2bb03d30>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "eight_queens = NQueensCSP(8)\n",
    "solution = min_conflicts(eight_queens)\n",
    "plot_NQueens(solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solution is a bit different this time. \n",
    "Running the above cell several times should give you various valid solutions.\n",
    "<br>\n",
    "In the `search.ipynb` notebook, we will see how NQueensProblem can be solved using a heuristic search method such as `uniform_cost_search` and `astar_search`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Helper Functions\n",
    "\n",
    "We will now implement a few helper functions that will help us visualize the Coloring Problem. We will make some modifications to the existing Classes and Functions for additional book keeping. To begin we modify the **assign** and **unassign** methods in the **CSP** to add a copy of the assignment to the **assignment_history**. We call this new class **InstruCSP**. This will allow us to see how the assignment evolves over time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import copy\n",
    "class InstruCSP(CSP):\n",
    "    \n",
    "    def __init__(self, variables, domains, neighbors, constraints):\n",
    "        super().__init__(variables, domains, neighbors, constraints)\n",
    "        self.assignment_history = []\n",
    "        \n",
    "    def assign(self, var, val, assignment):\n",
    "        super().assign(var,val, assignment)\n",
    "        self.assignment_history.append(copy.deepcopy(assignment))\n",
    "    \n",
    "    def unassign(self, var, assignment):\n",
    "        super().unassign(var,assignment)\n",
    "        self.assignment_history.append(copy.deepcopy(assignment))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we define **make_instru** which takes an instance of **CSP** and returns a **InstruCSP** instance. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def make_instru(csp):\n",
    "    return InstruCSP(csp.variables, csp.domains, csp.neighbors, csp.constraints)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will now use a graph defined as a dictionary for plotting purposes in our Graph Coloring Problem. The keys are the nodes and their corresponding values are the nodes they are connected to."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "neighbors = {\n",
    "    0: [6, 11, 15, 18, 4, 11, 6, 15, 18, 4], \n",
    "    1: [12, 12, 14, 14], \n",
    "    2: [17, 6, 11, 6, 11, 10, 17, 14, 10, 14], \n",
    "    3: [20, 8, 19, 12, 20, 19, 8, 12], \n",
    "    4: [11, 0, 18, 5, 18, 5, 11, 0], \n",
    "    5: [4, 4], \n",
    "    6: [8, 15, 0, 11, 2, 14, 8, 11, 15, 2, 0, 14], \n",
    "    7: [13, 16, 13, 16], \n",
    "    8: [19, 15, 6, 14, 12, 3, 6, 15, 19, 12, 3, 14], \n",
    "    9: [20, 15, 19, 16, 15, 19, 20, 16], \n",
    "    10: [17, 11, 2, 11, 17, 2], \n",
    "    11: [6, 0, 4, 10, 2, 6, 2, 0, 10, 4], \n",
    "    12: [8, 3, 8, 14, 1, 3, 1, 14], \n",
    "    13: [7, 15, 18, 15, 16, 7, 18, 16], \n",
    "    14: [8, 6, 2, 12, 1, 8, 6, 2, 1, 12], \n",
    "    15: [8, 6, 16, 13, 18, 0, 6, 8, 19, 9, 0, 19, 13, 18, 9, 16], \n",
    "    16: [7, 15, 13, 9, 7, 13, 15, 9], \n",
    "    17: [10, 2, 2, 10], \n",
    "    18: [15, 0, 13, 4, 0, 15, 13, 4], \n",
    "    19: [20, 8, 15, 9, 15, 8, 3, 20, 3, 9], \n",
    "    20: [3, 19, 9, 19, 3, 9]\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we are ready to create an InstruCSP instance for our problem. We are doing this for an instance of **MapColoringProblem** class which inherits from the **CSP** Class. This means that our **make_instru** function will work perfectly for it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "coloring_problem = MapColoringCSP('RGBY', neighbors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "coloring_problem1 = make_instru(coloring_problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BACKTRACKING SEARCH\n",
    "\n",
    "For solving a CSP the main issue with Naive search algorithms is that they can continue expanding obviously wrong paths. In backtracking search, we check constraints as we go. Backtracking is just the above idea combined with the fact that we are dealing with one variable at a time. Backtracking Search is implemented in the repository as the function **backtracking_search**. This is the same as **Figure 6.5** in the book. The function takes as input a CSP and few other optional parameters which can be used to further speed it up. The function returns the correct assignment if it satisfies the goal. We will discuss these later. Let us solve our **coloring_problem1** with **backtracking_search**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "result = backtracking_search(coloring_problem1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 'R',\n",
       " 1: 'R',\n",
       " 2: 'R',\n",
       " 3: 'R',\n",
       " 4: 'G',\n",
       " 5: 'R',\n",
       " 6: 'G',\n",
       " 7: 'R',\n",
       " 8: 'B',\n",
       " 9: 'R',\n",
       " 10: 'G',\n",
       " 11: 'B',\n",
       " 12: 'G',\n",
       " 13: 'G',\n",
       " 14: 'Y',\n",
       " 15: 'Y',\n",
       " 16: 'B',\n",
       " 17: 'B',\n",
       " 18: 'B',\n",
       " 19: 'G',\n",
       " 20: 'B'}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result # A dictonary of assignments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us also check the number of assignments made."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coloring_problem1.nassigns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let us check the total number of assignments and unassignments which is the length of our assignment history."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(coloring_problem1.assignment_history)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let us explore the optional keyword arguments that the **backtracking_search** function takes. These optional arguments help speed up the assignment further. Along with these, we will also point out to methods in the CSP class that help make this work. \n",
    "\n",
    "The first of these is **select_unassigned_variable**. It takes in a function that helps in deciding the order in which variables will be selected for assignment. We use a heuristic called Most Restricted Variable which is implemented by the function **mrv**. The idea behind **mrv** is to choose the variable with the fewest legal values left in its domain. The intuition behind selecting the **mrv** or the most constrained variable is that it allows us to encounter failure quickly before going too deep into a tree if we have selected a wrong step before. The **mrv** implementation makes use of another function **num_legal_values** to sort out the variables by a number of legal values left in its domain. This function, in turn, calls the **nconflicts** method of the **CSP** to return such values.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },