search.ipynb

   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "target = 'Genetic Algorithm'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "We then need to define our gene pool, i.e the elements which an individual from the population might comprise of. Here, the gene pool contains all uppercase and lowercase letters of the English alphabet and the space character."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The ASCII values of uppercase characters ranges from 65 to 91\n",
    "u_case = [chr(x) for x in range(65, 91)]\n",
    "# The ASCII values of lowercase characters ranges from 97 to 123\n",
    "l_case = [chr(x) for x in range(97, 123)]\n",
    "\n",
    "gene_pool = []\n",
    "gene_pool.extend(u_case) # adds the uppercase list to the gene pool\n",
    "gene_pool.extend(l_case) # adds the lowercase list to the gene pool\n",
    "gene_pool.append(' ')    # adds the space character to the gene pool"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now need to define the maximum size of each population. Larger populations have more variation but are computationally more  expensive to run algorithms on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "max_population = 100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As our population is not very large, we can afford to keep a relatively large mutation rate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "mutation_rate = 0.07 # 7%"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! Now, we need to define the most important metric for the genetic algorithm, i.e the fitness function. This will simply return the number of matching characters between the generated sample and the target phrase."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fitness_fn(sample):\n",
    "    # initialize fitness to 0\n",
    "    fitness = 0\n",
    "    for i in range(len(sample)):\n",
    "        # increment fitness by 1 for every matching character\n",
    "        if sample[i] == target[i]:\n",
    "            fitness += 1\n",
    "    return fitness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before we run our genetic algorithm, we need to initialize a random population. We will use the `init_population` function to do this. We need to pass in the maximum population size, the gene pool and the length of each individual, which in this case will be the same as the length of the target phrase."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "population = init_population(max_population, gene_pool, len(target))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will now define how the individuals in the population should change as the number of generations increases. First, the `select` function will be run on the population to select *two* individuals with high fitness values. These will be the parents which will then be recombined using the `recombine` function to generate the child."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "parents = select(2, population, fitness_fn) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The recombine function takes two parents as arguments, so we need to unpack the previous variable\n",
    "child = recombine(*parents)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we need to apply a mutation according to the mutation rate. We call the `mutate` function on the child with the gene pool and mutation rate as the additional arguments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "child = mutate(child, gene_pool, mutation_rate)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above lines can be condensed into\n",
    "\n",
    "`child = mutate(recombine(*select(2, population, fitness_fn)), gene_pool, mutation_rate)`\n",
    "\n",
    "And, we need to do this `for` every individual in the current population to generate the new population."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "population = [mutate(recombine(*select(2, population, fitness_fn)), gene_pool, mutation_rate) for i in range(len(population))]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The individual with the highest fitness can then be found using the `max` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "current_best = max(population, key=fitness_fn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's print this out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['J', 'y', 'O', 'e', ' ', 'h', 'c', 'r', 'C', 'W', 'H', 'o', 'r', 'R', 'y', 'P', 'U']\n"
     ]
    }
   ],
   "source": [
    "print(current_best)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that this is a list of characters. This can be converted to a string using the join function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "JyOe hcrCWHorRyPU\n"
     ]
    }
   ],
   "source": [
    "current_best_string = ''.join(current_best)\n",
    "print(current_best_string)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now need to define the conditions to terminate the algorithm. This can happen in two ways\n",
    "1. Termination after a predefined number of generations\n",
    "2. Termination when the fitness of the best individual of the current generation reaches a predefined threshold value.\n",
    "\n",
    "We define these variables below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ngen = 1200 # maximum number of generations\n",
    "# we set the threshold fitness equal to the length of the target phrase\n",
    "# i.e the algorithm only terminates whne it has got all the characters correct \n",
    "# or it has completed 'ngen' number of generations\n",
    "f_thres = len(target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "To generate `ngen` number of generations, we run a `for` loop `ngen` number of times. After each generation, we calculate the fitness of the best individual of the generation and compare it to the value of `f_thres` using the `fitness_threshold` function. After every generation, we print out the best individual of the generation and the corresponding fitness value. Lets now write a function to do this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def genetic_algorithm_stepwise(population, fitness_fn, gene_pool=[0, 1], f_thres=None, ngen=1200, pmut=0.1):\n",
    "    for generation in range(ngen):\n",
    "        population = [mutate(recombine(*select(2, population, fitness_fn)), gene_pool, pmut) for i in range(len(population))]\n",
    "        # stores the individual genome with the highest fitness in the current population\n",
    "        current_best = ''.join(max(population, key=fitness_fn))\n",
    "        print(f'Current best: {current_best}\\t\\tGeneration: {str(generation)}\\t\\tFitness: {fitness_fn(current_best)}\\r', end='')\n",
    "        \n",
    "        # compare the fitness of the current best individual to f_thres\n",
    "        fittest_individual = fitness_threshold(fitness_fn, f_thres, population)\n",
    "        \n",
    "        # if fitness is greater than or equal to f_thres, we terminate the algorithm\n",
    "        if fittest_individual:\n",
    "            return fittest_individual, generation\n",
    "    return max(population, key=fitness_fn) , generation       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function defined above is essentially the same as the one defined in `search.py` with the added functionality of printing out the data of each generation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "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\">genetic_algorithm</span><span class=\"p\">(</span><span class=\"n\">population</span><span class=\"p\">,</span> <span class=\"n\">fitness_fn</span><span class=\"p\">,</span> <span class=\"n\">gene_pool</span><span class=\"o\">=</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">,</span> <span class=\"mi\">1</span><span class=\"p\">],</span> <span class=\"n\">f_thres</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"n\">ngen</span><span class=\"o\">=</span><span class=\"mi\">1000</span><span class=\"p\">,</span> <span class=\"n\">pmut</span><span class=\"o\">=</span><span class=\"mf\">0.1</span><span class=\"p\">):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;[Figure 4.8]&quot;&quot;&quot;</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\">ngen</span><span class=\"p\">):</span>\n",
       "        <span class=\"n\">population</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">mutate</span><span class=\"p\">(</span><span class=\"n\">recombine</span><span class=\"p\">(</span><span class=\"o\">*</span><span class=\"n\">select</span><span class=\"p\">(</span><span class=\"mi\">2</span><span class=\"p\">,</span> <span class=\"n\">population</span><span class=\"p\">,</span> <span class=\"n\">fitness_fn</span><span class=\"p\">)),</span> <span class=\"n\">gene_pool</span><span class=\"p\">,</span> <span class=\"n\">pmut</span><span class=\"p\">)</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=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">population</span><span class=\"p\">))]</span>\n",
       "\n",
       "        <span class=\"n\">fittest_individual</span> <span class=\"o\">=</span> <span class=\"n\">fitness_threshold</span><span class=\"p\">(</span><span class=\"n\">fitness_fn</span><span class=\"p\">,</span> <span class=\"n\">f_thres</span><span class=\"p\">,</span> <span class=\"n\">population</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">fittest_individual</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">fittest_individual</span>\n",
       "\n",
       "\n",
       "    <span class=\"k\">return</span> <span class=\"n\">argmax</span><span class=\"p\">(</span><span class=\"n\">population</span><span class=\"p\">,</span> <span class=\"n\">key</span><span class=\"o\">=</span><span class=\"n\">fitness_fn</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(genetic_algorithm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have defined all the required functions and variables. Let's now create a new population and test the function we wrote above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current best: Genetic Algorithm\t\tGeneration: 985\t\tFitness: 17\r"
     ]
    }
   ],
   "source": [
    "population = init_population(max_population, gene_pool, len(target))\n",
    "solution, generations = genetic_algorithm_stepwise(population, fitness_fn, gene_pool, f_thres, ngen, mutation_rate)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The genetic algorithm was able to converge!\n",
    "We implore you to rerun the above cell and play around with `target, max_population, f_thres, ngen` etc parameters to get a better intuition of how the algorithm works. To summarize, if we can define the problem states in simple array format and if we can create a fitness function to gauge how good or bad our approximate solutions are, there is a high chance that we can get a satisfactory solution using a genetic algorithm. \n",
    "- There is also a better GUI version of this program `genetic_algorithm_example.py` in the GUI folder for you to play around with."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Usage\n",
    "\n",
    "Below we give two example usages for the genetic algorithm, for a graph coloring problem and the 8 queens problem.\n",
    "\n",
    "#### Graph Coloring\n",
    "\n",
    "First we will take on the simpler problem of coloring a small graph with two colors. Before we do anything, let's imagine how a solution might look. First, we have to represent our colors. Say, 'R' for red and 'G' for green. These make up our gene pool. What of the individual solutions though? For that, we will look at our problem. We stated we have a graph. A graph has nodes and edges, and we want to color the nodes. Naturally, we want to store each node's color. If we have four nodes, we can store their colors in a list of genes, one for each node. A possible solution will then look like this: ['R', 'R', 'G', 'R']. In the general case, we will represent each solution with a list of chars ('R' and 'G'), with length the number of nodes.\n",
    "\n",
    "Next we need to come up with a fitness function that appropriately scores individuals. Again, we will look at the problem definition at hand. We want to color a graph. For a solution to be optimal, no edge should connect two nodes of the same color. How can we use this information to score a solution? A naive (and ineffective) approach would be to count the different colors in the string. So ['R', 'R', 'R', 'R'] has a score of 1 and ['R', 'R', 'G', 'G'] has a score of 2. Why that fitness function is not ideal though? Why, we forgot the information about the edges! The edges are pivotal to the problem and the above function only deals with node colors. We didn't use all the information at hand and ended up with an ineffective answer. How, then, can we use that information to our advantage?\n",
    "\n",
    "We said that the optimal solution will have all the edges connecting nodes of different color. So, to score a solution we can count how many edges are valid (aka connecting nodes of different color). That is a great fitness function!\n",
    "\n",
    "Let's jump into solving this problem using the `genetic_algorithm` function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we need to represent the graph. Since we mostly need information about edges, we will just store the edges. We will denote edges with capital letters and nodes with integers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "edges = {\n",
    "    'A': [0, 1],\n",
    "    'B': [0, 3],\n",
    "    'C': [1, 2],\n",
    "    'D': [2, 3]\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edge 'A' connects nodes 0 and 1, edge 'B' connects nodes 0 and 3 etc.\n",
    "\n",
    "We already said our gene pool is 'R' and 'G', so we can jump right into initializing our population. Since we have only four nodes, `state_length` should be 4. For the number of individuals, we will try 8. We can increase this number if we need higher accuracy, but be careful! Larger populations need more computating power and take longer. You need to strike that sweet balance between accuracy and cost (the ultimate dilemma of the programmer!)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['R', 'G', 'G', 'G'], ['G', 'R', 'R', 'G'], ['G', 'G', 'G', 'G'], ['G', 'R', 'G', 'G'], ['G', 'G', 'G', 'R'], ['G', 'R', 'R', 'G'], ['G', 'R', 'G', 'G'], ['G', 'G', 'R', 'G']]\n"
     ]
    }
   ],
   "source": [
    "population = init_population(8, ['R', 'G'], 4)\n",
    "print(population)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We created and printed the population. You can see that the genes in the individuals are random and there are 8 individuals each with 4 genes.\n",
    "\n",
    "Next we need to write our fitness function. We previously said we want the function to count how many edges are valid. So, given a coloring/individual `c`, we will do just that:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fitness(c):\n",
    "    return sum(c[n1] != c[n2] for (n1, n2) in edges.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! Now we will run the genetic algorithm and see what solution it gives."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['R', 'G', 'R', 'G']\n"
     ]
    }
   ],
   "source": [
    "solution = genetic_algorithm(population, fitness, gene_pool=['R', 'G'])\n",
    "print(solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The algorithm converged to a solution. Let's check its score:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "print(fitness(solution))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solution has a score of 4. Which means it is optimal, since we have exactly 4 edges in our graph, meaning all are valid!\n",
    "\n",
    "*NOTE: Because the algorithm is non-deterministic, there is a chance a different solution is given. It might even be wrong, if we are very unlucky!*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Eight Queens\n",
    "\n",
    "Let's take a look at a more complicated problem.\n",
    "\n",
    "In the *Eight Queens* problem, we are tasked with placing eight queens on an 8x8 chessboard without any queen threatening the others (aka queens should not be in the same row, column or diagonal). In its general form the problem is defined as placing *N* queens in an NxN chessboard without any conflicts.\n",
    "\n",
    "First we need to think about the representation of each solution. We can go the naive route of representing the whole chessboard with the queens' placements on it. That is definitely one way to go about it, but for the purpose of this tutorial we will do something different. We have eight queens, so we will have a gene for each of them. The gene pool will be numbers from 0 to 7, for the different columns. The *position* of the gene in the state will denote the row the particular queen is placed in.\n",
    "\n",
    "For example, we can have the state \"03304577\". Here the first gene with a value of 0 means \"the queen at row 0 is placed at column 0\", for the second gene \"the queen at row 1 is placed at column 3\" and so forth.\n",
    "\n",
    "We now need to think about the fitness function. On the graph coloring problem we counted the valid edges. The same thought process can be applied here. Instead of edges though, we have positioning between queens. If two queens are not threatening each other, we say they are at a \"non-attacking\" positioning. We can, therefore, count how many such positionings are there.\n",
    "\n",
    "Let's dive right in and initialize our population:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[2, 6, 2, 0, 2, 3, 4, 7], [7, 2, 0, 6, 3, 3, 0, 6], [2, 3, 0, 6, 6, 2, 5, 5], [2, 6, 4, 2, 3, 5, 5, 5], [3, 1, 5, 1, 5, 1, 0, 3]]\n"
     ]
    }
   ],
   "source": [
    "population = init_population(100, range(8), 8)\n",
    "print(population[:5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have a population of 100 and each individual has 8 genes. The gene pool is the integers from 0 to 7, in string form. Above you can see the first five individuals.\n",
    "\n",
    "Next we need to write our fitness function. Remember, queens threaten each other if they are at the same row, column or diagonal.\n",
    "\n",
    "Since positionings are mutual, we must take care not to count them twice. Therefore for each queen, we will only check for conflicts for the queens after her.\n",
    "\n",
    "A gene's value in an individual `q` denotes the queen's column, and the position of the gene denotes its row. We can check if the aforementioned values between two genes are the same. We also need to check for diagonals. A queen *a* is in the diagonal of another queen, *b*, if the difference of the rows between them is equal to either their difference in columns (for the diagonal on the right of *a*) or equal to the negative difference of their columns (for the left diagonal of *a*). Below is given the fitness function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fitness(q):\n",
    "    non_attacking = 0\n",
    "    for row1 in range(len(q)):\n",
    "        for row2 in range(row1+1, len(q)):\n",
    "            col1 = int(q[row1])\n",
    "            col2 = int(q[row2])\n",
    "            row_diff = row1 - row2\n",
    "            col_diff = col1 - col2\n",
    "\n",
    "            if col1 != col2 and row_diff != col_diff and row_diff != -col_diff:\n",
    "                non_attacking += 1\n",
    "\n",
    "    return non_attacking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the best score achievable is 28. That is because for each queen we only check for the queens after her. For the first queen we check 7 other queens, for the second queen 6 others and so on. In short, the number of checks we make is the sum 7+6+5+...+1. Which is equal to 7\\*(7+1)/2 = 28.\n",
    "\n",
    "Because it is very hard and will take long to find a perfect solution, we will set the fitness threshold at 25. If we find an individual with a score greater or equal to that, we will halt. Let's see how the genetic algorithm will fare."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 5, 7, 1, 3, 6, 4, 6]\n",
      "25\n"
     ]
    }
   ],
   "source": [
    "solution = genetic_algorithm(population, fitness, f_thres=25, gene_pool=range(8))\n",
    "print(solution)\n",
    "print(fitness(solution))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Above you can see the solution and its fitness score, which should be no less than 25."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is where we conclude Genetic Algorithms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### N-Queens Problem\n",
    "Here, we will look at the generalized cae of the Eight Queens problem.\n",
    "<br>\n",
    "We are given a `N` x `N` chessboard, with `N` queens, and we need to place them in such a way that no two queens can attack each other.\n",
    "<br>\n",
    "We will solve this problem using search algorithms.\n",
    "To do this, we already have a `NQueensProblem` class in `search.py`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "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\">NQueensProblem</span><span class=\"p\">(</span><span class=\"n\">Problem</span><span class=\"p\">):</span>\n",
       "\n",
       "    <span class=\"sd\">&quot;&quot;&quot;The problem of placing N queens on an NxN board with none attacking</span>\n",
       "<span class=\"sd\">    each other.  A state is represented as an N-element array, where</span>\n",
       "<span class=\"sd\">    a value of r in the c-th entry means there is a queen at column c,</span>\n",
       "<span class=\"sd\">    row r, and a value of -1 means that the c-th column has not been</span>\n",
       "<span class=\"sd\">    filled in yet.  We fill in columns left to right.</span>\n",
       "<span class=\"sd\">    &gt;&gt;&gt; depth_first_tree_search(NQueensProblem(8))</span>\n",
       "<span class=\"sd\">    &lt;Node (7, 3, 0, 2, 5, 1, 6, 4)&gt;</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=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">N</span> <span class=\"o\">=</span> <span class=\"n\">N</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">initial</span> <span class=\"o\">=</span> <span class=\"nb\">tuple</span><span class=\"p\">([</span><span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">]</span> <span class=\"o\">*</span> <span class=\"n\">N</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">Problem</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=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">initial</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">actions</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;In the leftmost empty column, try all non-conflicting rows.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">state</span><span class=\"p\">[</span><span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">]</span> <span class=\"ow\">is</span> <span class=\"ow\">not</span> <span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"p\">[]</span>  <span class=\"c1\"># All columns filled; no successors</span>\n",
       "        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">col</span> <span class=\"o\">=</span> <span class=\"n\">state</span><span class=\"o\">.</span><span class=\"n\">index</span><span class=\"p\">(</span><span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">return</span> <span class=\"p\">[</span><span class=\"n\">row</span> <span class=\"k\">for</span> <span class=\"n\">row</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">N</span><span class=\"p\">)</span>\n",
       "                    <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">conflicted</span><span class=\"p\">(</span><span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">row</span><span class=\"p\">,</span> <span class=\"n\">col</span><span class=\"p\">)]</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">result</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">row</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Place the next queen at the given row.&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">col</span> <span class=\"o\">=</span> <span class=\"n\">state</span><span class=\"o\">.</span><span class=\"n\">index</span><span class=\"p\">(</span><span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">new</span> <span class=\"o\">=</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"n\">state</span><span class=\"p\">[:])</span>\n",
       "        <span class=\"n\">new</span><span class=\"p\">[</span><span class=\"n\">col</span><span class=\"p\">]</span> <span class=\"o\">=</span> <span class=\"n\">row</span>\n",
       "        <span class=\"k\">return</span> <span class=\"nb\">tuple</span><span class=\"p\">(</span><span class=\"n\">new</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">conflicted</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">row</span><span class=\"p\">,</span> <span class=\"n\">col</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Would placing a queen at (row, col) conflict with anything?&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">return</span> <span class=\"nb\">any</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">conflict</span><span class=\"p\">(</span><span class=\"n\">row</span><span class=\"p\">,</span> <span class=\"n\">col</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">[</span><span class=\"n\">c</span><span class=\"p\">],</span> <span class=\"n\">c</span><span class=\"p\">)</span>\n",
       "                   <span class=\"k\">for</span> <span class=\"n\">c</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">col</span><span class=\"p\">))</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">conflict</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">row1</span><span class=\"p\">,</span> <span class=\"n\">col1</span><span class=\"p\">,</span> <span class=\"n\">row2</span><span class=\"p\">,</span> <span class=\"n\">col2</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Would putting two queens in (row1, col1) and (row2, col2) conflict?&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">return</span> <span class=\"p\">(</span><span class=\"n\">row1</span> <span class=\"o\">==</span> <span class=\"n\">row2</span> <span class=\"ow\">or</span>  <span class=\"c1\"># same row</span>\n",
       "                <span class=\"n\">col1</span> <span class=\"o\">==</span> <span class=\"n\">col2</span> <span class=\"ow\">or</span>  <span class=\"c1\"># same column</span>\n",
       "                <span class=\"n\">row1</span> <span class=\"o\">-</span> <span class=\"n\">col1</span> <span class=\"o\">==</span> <span class=\"n\">row2</span> <span class=\"o\">-</span> <span class=\"n\">col2</span> <span class=\"ow\">or</span>  <span class=\"c1\"># same \\ diagonal</span>\n",
       "                <span class=\"n\">row1</span> <span class=\"o\">+</span> <span class=\"n\">col1</span> <span class=\"o\">==</span> <span class=\"n\">row2</span> <span class=\"o\">+</span> <span class=\"n\">col2</span><span class=\"p\">)</span>   <span class=\"c1\"># same / diagonal</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">goal_test</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Check if all columns filled, no conflicts.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">state</span><span class=\"p\">[</span><span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">]</span> <span class=\"ow\">is</span> <span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"bp\">False</span>\n",
       "        <span class=\"k\">return</span> <span class=\"ow\">not</span> <span class=\"nb\">any</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">conflicted</span><span class=\"p\">(</span><span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">[</span><span class=\"n\">col</span><span class=\"p\">],</span> <span class=\"n\">col</span><span class=\"p\">)</span>\n",
       "                       <span class=\"k\">for</span> <span class=\"n\">col</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">state</span><span class=\"p\">)))</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">h</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">node</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Return number of conflicting queens for a given node&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">num_conflicts</span> <span class=\"o\">=</span> <span class=\"mi\">0</span>\n",
       "        <span class=\"k\">for</span> <span class=\"p\">(</span><span class=\"n\">r1</span><span class=\"p\">,</span> <span class=\"n\">c1</span><span class=\"p\">)</span> <span class=\"ow\">in</span> <span class=\"nb\">enumerate</span><span class=\"p\">(</span><span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">):</span>\n",
       "            <span class=\"k\">for</span> <span class=\"p\">(</span><span class=\"n\">r2</span><span class=\"p\">,</span> <span class=\"n\">c2</span><span class=\"p\">)</span> <span class=\"ow\">in</span> <span class=\"nb\">enumerate</span><span class=\"p\">(</span><span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">):</span>\n",
       "                <span class=\"k\">if</span> <span class=\"p\">(</span><span class=\"n\">r1</span><span class=\"p\">,</span> <span class=\"n\">c1</span><span class=\"p\">)</span> <span class=\"o\">!=</span> <span class=\"p\">(</span><span class=\"n\">r2</span><span class=\"p\">,</span> <span class=\"n\">c2</span><span class=\"p\">):</span>\n",
       "                    <span class=\"n\">num_conflicts</span> <span class=\"o\">+=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">conflict</span><span class=\"p\">(</span><span class=\"n\">r1</span><span class=\"p\">,</span> <span class=\"n\">c1</span><span class=\"p\">,</span> <span class=\"n\">r2</span><span class=\"p\">,</span> <span class=\"n\">c2</span><span class=\"p\">)</span>\n",
       "\n",
       "        <span class=\"k\">return</span> <span class=\"n\">num_conflicts</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(NQueensProblem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In [`csp.ipynb`](https://github.com/aimacode/aima-python/blob/master/csp.ipynb) we have seen that the N-Queens problem can be formulated as a CSP and can be solved by \n",
    "the `min_conflicts` algorithm in a way similar to Hill-Climbing. \n",
    "Here, we want to solve it using heuristic search algorithms and even some classical search algorithms.\n",
    "The `NQueensProblem` class derives from the `Problem` class and is implemented in such a way that the search algorithms we already have, can solve it.\n",
    "<br>\n",
    "Let's instantiate the class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nqp = NQueensProblem(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's use `depth_first_tree_search` first.\n",
    "<br>\n",
    "We will also use the %%timeit magic with each algorithm to see how much time they take."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.82 ms ± 498 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "depth_first_tree_search(nqp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "dfts = depth_first_tree_search(nqp).solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAewAAAHwCAYAAABkPlyAAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAIABJREFUeJzt3X+4FdWd7/nP93IOIIZfBw6YAGOg\nkyczHQO2nBa7iQwxpA0IRmd6umGMXs1kuJO5hiDY6Zbn6Scmz41mVCB07OncXGnw3jagaduI2lGi\nEQwYtQ+00jHpnseAiYj8OMIJ6DERuGv+qLM9e+9TVbvO3lW7dlW9X8+zn7131aq11t6Lw3evVatW\nmXNOAACgtf27tCsAAABqI2ADAJABBGwAADKAgA0AQAYQsAEAyAACNgAAGUDABgAgAwjYAABkAAEb\naDFm9kEz+0czO2Fmh83sbjNrC0k/zsz+pj9tn5n9i5n9+2bWGUDyCNhA6/l/JR2V9H5JF0r6nyX9\n334JzWy4pCclnS/pDySNlfRnku4wsxVNqS2ApiBgA61nuqQHnHO/cc4dlvS4pI8GpL1W0v8g6X9z\nzh1wzp12zj0uaYWk/2RmoyXJzJyZfah0kJltNrP/VPZ+sZm9aGa9Zvasmc0s2/cBM3vQzI6Z2YHy\nHwJmdquZPWBm/9XMTpnZy2bWVbb/z83s9f59/2Zmn4znKwKKh4ANtJ4Nkpaa2SgzmyJpobyg7edT\nkn7gnHu7avuDkkZJuqRWYWZ2kaS/lfQfJE2Q9J8lbTOzEWb27yQ9IuklSVMkfVLSSjO7vCyLKyVt\nlTRO0jZJd/fn+xFJN0r6fefcaEmXS3q1Vn0A+CNgA61np7we9UlJByV1S/p+QNqJkt6o3uicOyOp\nR1JnhPL+T0n/2Tn3vHPurHPuXkm/lRfsf19Sp3Pua865d51z+yX9F0lLy47f5Zz7R+fcWUn/TdKs\n/u1nJY2Q9Ltm1u6ce9U594sI9QHgg4ANtJD+Hu0Tkv5B0rnyAvJ4Sf9PwCE98s51V+fT1n/ssQjF\nni9pdf9weK+Z9UqaJukD/fs+ULVvjaTJZccfLnvdJ2mkmbU5516RtFLSrZKOmtlWM/tAhPoA8EHA\nBlpLh7xgebdz7rfOuTclbZK0KCD9k5IWmtm5Vdv/V0mnJb3Q/75P3hB5yXllr1+T9HXn3Liyxyjn\n3Jb+fQeq9o12zgXVp4Jz7rvOuY/LC/xOwT88ANRAwAZaiHOuR9IBSV8wszYzGyfp38s7h+znv8kb\nNv9e/+Vg7f3nl/9K0h3OuV/3p3tR0v9uZsPM7NPyZp6X/BdJ/5eZzTHPuWZ2Rf+EtRckneyfPHZO\n//EXmNnv1/osZvYRM7vMzEZI+o2kd+QNkwOoAwEbaD3/i6RPyxvOfkXSGUk3+SV0zv1W0gJ5PeHn\n5QXFxyV9U9JXy5J+SdISSb2SrlHZOXHnXLe889h3SzrRX+b1/fvO9h93obwfEj2S7pF3+VgtIyR9\no/+Yw5ImyRtOB1AHc86lXQcAMTGzdkk/kPS6pOsdf+BAbtDDBnLEOXda3vnrX0j6SMrVARAjetgA\nAGQAPWwAADIg8IYCzTJx4kT3wQ9+MO1qJGbPnj1pVyFRs2fPTrsKiaMNs432y768t6GkHudczUWO\nUh8S7+rqct3d3anWIUlmlnYVEhXrv589MXxXs+P/90wbZhvtl315b0NJe5xzXbUSMSSOdB250wvU\ncQRraSCvI2vjyQ8AWgQBG+k4/aYXWA9+OZn8D97s5X/6SDL5A0CTpX4OGwUUV286in39K3AmMFQO\nAM1EDxvN1cxg3QrlAkBMCNhojr0j0g+ae0w6vjXdOgBAnQjYSN4ek9y7DWdz4x0x1OXAsvR/OABA\nHTiHjWTtHdlwFlZ2scNfP+A9u0avBNw7Qrrotw1mAgDNQw8byXK1g2LnAum+H/jvs4ArE4O2RxZD\njx8AmomAjeTUGHq2Lu/R0yt99i8bD8Kl/EqPC/6ksfoBQCshYCMZNYLht+73315v0PY77uX9EQ4k\naAPICAI24nfmaM0kK+5sQj0U8QfAmZ7E6wEAjSJgI34vTY4tq6DJZQ1POiv3Us019wEgdcwSR7ze\nGLj2yq93Wwq0rjv68Lfrlk71SWPmSSefkUaPil6dTV8ZeB1WHx1eL513U/SMAaDJ6GEjXof+XFJw\nMD5YNlo+d9bg/UE951KQDgrWQcddv8R7/tVh//3v1fP1Vf4JAKBFELDRVNMWDbzetbEy0IYNc3/4\nau95wmXBaarzKn9//uKh1RMAWg0BG/FpcMb16yFz1V55zXs+fjI4Tdi+SJgxDqCFEbDRVIvmBu+b\nuih4XxRhve/FlzaWNwCkjYCNRPTt9t/+2Ibm1qPkkfX+2995trn1AIB6EbARj9OVs7rOGeGdQz5n\nxMC2KJdibX6kvuIf3lk7TXn5o0Z670cOr0p0+lh9FQCAhBGwEY997/fd3LdbOv289zrKZVw3fHXw\ntjNnK9/39A5Oc9Xq2nmXyu/dIb29KyDRvkm1MwKAFBCwkbi2YY0dP/ySyvedCxrLb+z7GjseANJA\nwEZTRellL11T+d658PSf+1o85QJAKyNgo+Xcv31o6TdtS6YeANBKEgnYZvZpM/s3M3vFzP4iiTLQ\nWlati5622b3doZQ3lM8BAM0Ue8A2s2GS/lrSQkm/K2mZmf1u3OWgtayLeWXPL9weLV3cd/2K+3MA\nQFyS6GFfLOkV59x+59y7krZK+kwC5SDDFq8M3//tB73nnXv99297xnsOuq92SfXs8euuqF03AGhF\nSQTsKZJeK3t/sH/be8xsuZl1m1n3sWNc91oE0z9Q+f6xoMuqqsxf7r/9MxF7wtXXZ9/rc9kYAGRB\nEgHbb0Hminm+zrnvOOe6nHNdnZ3ci7gIfnzP4G0LV4Qf0xGy1Kgkjf9E+P6Va8P3A0CWJBGwD0qa\nVvZ+qqRDCZSDVjIrfKRkis96JI/XWBb0RI2befSeCt+/YUv4fl8ze+o4CACSl0TA/idJHzaz6WY2\nXNJSSVx4k3dtE+s6LKkZ41ffXOeB7RNirQcAxKUt7gydc2fM7EZJT0gaJulvnXMvx10OEOb7O9Ku\nAQDEK/aALUnOuX+U9I9J5I3smtwhHTmeXvlzLkivbABoFCudIT6zw9cQPTzEFczKfexD0oKLpd+Z\nWn8ez22ukaBG/QEgTYn0sIEgrjv4vPWiuY3dL/vyG6XtzwWXCwBZRsBGvKbeJR0Mn/HVu0MaN997\nfWS7NKmjcv/1t0r3Phq9yLmzpF0bpSfuHth24JA040rvdaSe/bS/il4gAKSAIXHEa3LtG1OXbm/p\nur1gvXW71+suPYYSrCVp90uVx295wluopdSrntwRfrwkadIXh1YoADSZuVr3LkxYV1eX6+7O73il\nmd86Mvnh++/n9DFpn8+F11WiXtK1ZJ50wxJp/mzpxCnpJ/uk2zZJP9sfoX5R/mnN7Am9nKuQbZgj\ntF/25b0NJe1xztX8H5EhccSvvf7V67at8wJ0kPFjpBlTpGsWVm7f9aJ06efrLJRrrwFkAAEbyZjt\npD3hv4pLE9Da26R3qyaLDWVBFdctffzCgd50+xzpzNmIvWtmhgPICAI2khMhaEsDwbreVc/Kjzv7\ngnT6+Yh5EawBZAiTzpCs6bUX9C5NFvNz63LpxNNeb7n06Nvtbfcz7OKIwXr69yIkAoDWwaSzhOV9\nskSkfz8BvezqwHrVfOmhu+qvy7I13ozzcoHD4kPoXdOG2Ub7ZV/e21BMOkPLmO2kvaMk986gXT1P\nSRPGVm4bPU96qy969h1jpDd/JG25zXtI0jc2S7fc7ZN4+hapY2n0zAGgRRCw0RwX9Ufgqt522zBp\n+pXSqw3cgPX4ycre+i8fHdzTlsQ5awCZxjlsNFdZ0HTd0sM7GwvWfs5f7F23XTEcTrAGkHH0sNF8\ns510+ri0b4Kuu0K67ooEy5p5tKHrwgGgVdDDRjraO7zAPW19MvlP2+DlT7AGkBP0sJGuSSu9hxTp\nmu2aGPoGkFP0sNE6ZruBx6wTg3av9uuMz3yj8jgAyCl62GhNbeMGBeC1f5dSXQCgBdDDBgAgAwjY\nAABkAAEbAIAMIGADAJABqd/8w8xyPbU37e83aQVYlJ82zDjaL/sK0Ibc/AMAEnP2hPRiR8Wm1eul\ntTdVpZt5SGp/f/Pqhdyih52wtL/fpPHrPvvy3oaxtl8LLu6T9/aTCvE3GKmHzTlsAAhz5E4vUMcR\nrKWBvI6sjSc/FAY97ISl/f0mjV/32Zf3Nqy7/U6/Ke2bGG9l/Mw8LLVPrvvwvLefVIi/Qc5hA0Bd\n4upNR7HvPO+ZpXVRA0PiAFCumcG6FcpFZhCwAUCS9o5IP2juMen41nTrgJZFwAaAPSa5dxvO5sY7\nYqjLgWXp/3BAS2LSWcLS/n6TxoSX7Mt7G9Zsv70jJffbhsown+lCrruhLCUbLl1Uu155bz+pEH+D\nXNYFADVFCNadC6T7fuC/zy9Yh22PLIYeP/KFHnbC0v5+k8av++zLexuGtl+NoecoPeewwFwr7Udn\nSD99ILQKNWeP5739pEL8DdLDBoBANYL1t+73315vz9nvuJf3RziQ89noR8AGUDxnjtZMsuLOJtRD\nEX8AnOlJvB5ofQRsAMXzUv0ri1ULmlzW8KSzci91xpgZsoqVzgAUyxsD116FnaN23dGHv123dKpP\nGjNPOvmMNHpU9Ops+srA69Bz5ofXS+dV3woMRUIPG0CxHPpzScHB+GDZaPncWYP3B/WcS0E6KFgH\nHXf9Eu/5V4f9979Xz9dX+SdAYRCwAaDMtEUDr3dtrAy0YcPcH77ae55wWXCa6rzK35+/eGj1RPEQ\nsAEUR4Mzrl8Pmav2ymve8/GTwWnC9kXCjPFCI2ADQJlFc4P3TV0UvC+KsN734ksbyxv5R8AGUEh9\nu/23P7ahufUoeWS9//Z3nm1uPdC6CNgAiuF05ayuc0Z455DPGTGwLcqlWJsfqa/4h3fWTlNe/qiR\n3vuRw6sSnT5WXwWQeSxNmrC0v9+ksSxi9uW9Dd9rv5Dzv2fOSu1z+tP7BO3qGeXVacqPl6RjT0oT\nxw0tj/I0vTukse8LrG7FcqV5bz+pEH+DLE0KAFG0DWvs+OGXVL7vXNBYfqHBGoVFwAaAMlEWS1m6\npvJ9rQ7g574WT7kottgDtpn9rZkdNbOfxp03ALSC+7cPLf2mbcnUA8WSRA97s6RPJ5AvANRt1bro\naZvd2x1KeUP5HMiX2AO2c+4ZScfjzhcAGrEu5pU9v3B7tHRx3/Ur7s+B7OAcNgD4WLwyfP+3H/Se\nd+7137/tGe856L7aJVetrnx/3RW164ZiSiVgm9lyM+s2szhvQAcAdZv+gcr3j+2Kdtz85f7bPxOx\nJ1x9ffa9X412HIonlYDtnPuOc64rynVnANAMP75n8LaFK8KP6QhZalSSxn8ifP/KteH7gXIMiQMo\nhlnhK4RNmTR42+M1lgU9UeNmHr2nwvdv2BK+39fMnjoOQh4kcVnXFkk/kfQRMztoZv9H3GUAwJC1\nTazrsKRmjF99c50Htk+ItR7Ijra4M3TOLYs7TwDIm+/vSLsGyBqGxAGg3+SOdMufc0G65aO1cfOP\nhKX9/SaNGw9kX97bcFD7hdwERKp/CPxjH/IC/oFD0i8O1pdHzbuFzR78bzHv7ScV4m8w0s0/Yh8S\nB4Asc93BQXvR3Mbul335jdL254LLBcIQsAEUy9S7pIPhM756d0jj5nuvj2yXJlUNlV9/q3Tvo9GL\nnDtL2rVReuLugW0HDkkzrvReH46yNvm0v4peIHKJIfGEpf39Jo3huOzLexv6tl+NYXHJ62WXer1b\nt0vL1oSnH4rvfl1advngckL5DIdL+W8/qRB/g5GGxAnYCUv7+00a/1lkX97b0Lf9Th+T9vlceF0l\n6vnsJfOkG5ZI82dLJ05JP9kn3bZJ+tn+CPWLEqxn9gRezpX39pMK8TfIOWwA8NXeWfeh29Z5ATrI\n+DHSjCnSNQsrt+96Ubr083UWyrXXED3sxKX9/SaNX/fZl/c2DG2/iEPj7W3Su88N3h65DlW96PY5\n0pmzjQ2Fv1ePnLefVIi/QXrYABBqtosUtEvBut5LvsqPO/uCdPr5iHnVCNYoFhZOAVBs02sv6G1d\nwQH21uXSiae93nLp0bfb2+5n2MURg/X070VIhCJhSDxhaX+/SWM4Lvvy3oaR2i+gl10dWK+aLz10\nV/11WbbGm3FeLnBYPGLvOu/tJxXib5BZ4q0g7e83afxnkX15b8PI7bd3lOTeqdhkXVLPU9KEsZVJ\nR8+T3uqLXoeOMdKbP6rc9o3N0i13+wTs6VukjqWR8857+0mF+BvkHDYARHZRfwSu6m23DZOmXym9\neqj+rI+frOyt//LRwT1tSZyzRijOYQNAubKg6bqlh3c2Fqz9nL/Yu267ondNsEYNDIknLO3vN2kM\nx2Vf3tuw7vY7fVza14Trn2cebei68Ly3n1SIv8FIQ+L0sAHAT3uH1+udtj6Z/Kdt8PJvIFijWOhh\nJyzt7zdp/LrPvry3YaztF+Ga7ZpiHvrOe/tJhfgbpIcNALGa7QYes04M2r3arzM+843K44A60cNO\nWNrfb9L4dZ99eW9D2i/7CtCG9LABAMgLAjYAABlAwAYAIANSX+ls9uzZ6u6Oco+5bMr7+aW8n1uS\naMOso/2yL+9tGBU9bAAAMiD1HjZQFIF3ZRqCeu/HDCD76GEDCbr52oF7JMehlNeqa+LJD0B2ELCB\nBHSM8QLrnV9KJv+1N3n5T+pIJn8ArYchcSBmcfWmozjSf4tGhsqB/KOHDcSomcG6FcoF0DwEbCAG\nv3k2/aDpuqU//VS6dQCQHAI20CDXLY0Y3ng+N97ReB5bb0//hwOAZHAOG2jAO7sbz6P8/PNfP+A9\nNxp0f/OsNPIPG8sDQGuhhw00YOSI2mk6F0j3/cB/X9BksUYnkcXR4wfQWgjYQJ1q9YKty3v09Eqf\n/cvGg3Apv9Ljgj9prH4AsoWADdShVjD81v3+2+sN2n7Hvby/9nEEbSA/CNjAEHVGWKxkxZ3J10OK\n9gNgwtjk6wEgeQRsYIiObo8vr6AecJw9456n4ssLQHqYJQ4MwZ9dO/Dar3dbCrSuO/rwt+uWTvVJ\nY+ZJJ5+RRo+KXp9NX4lWn5XLpG9uiZ4vgNZDDxsYgjv61wYPCsYHjw68njtr8P6gnnMpSAcF66Dj\nrl/iPf/qsP/+Uj3Xr/bfDyA7CNhAjKYtGni9a2NloA0b5v7w1d7zhMuC01TnVf7+/MVDqyeA7CFg\nAxE1el759aPB+155zXs+fjI4Tdi+KJgxDmQbARuI0aK5wfumLgreF0VY73vxpY3lDaD1EbCBOvQF\nLEn62Ibm1qPkkfX+2995trn1AJAcAjYQweQJle/PGeENMZ9TtjRplCHnzY/UV/7DO2unKS9/1Ejv\n/ciqJUonjquvfADpI2ADERx+wn97327p9PPe6yiXcd3w1cHbzpytfN/TOzjNVRFmeZfK790hvb3L\nP82xJ2vnA6A1EbCBBrUNa+z44ZdUvu9c0Fh+Y9/X2PEAWhMBG4hRlF720jWV750LT/+5r8VTLoBs\nI2ADTXb/EJc23bQtmXoAyJbYA7aZTTOzp83s52b2spl9Ke4ygGZbtS562mb3dodS3lA+B4DWkkQP\n+4yk1c65/0nSJZL+o5n9bgLlAE2zblW8+X3h9mjp4r7rV9yfA0DzxB6wnXNvOOf29r8+JennkqbE\nXQ7QyhavDN//7Qe95517/fdve8Z7Drqvdkn17PHrrqhdNwDZlOg5bDP7oKTfk/R81fblZtZtZt3H\njh1LsgpAU0z/QOX7xwIuq6o2f7n/9s9E7AlXX599r89lYwDyIbGAbWbvk/SgpJXOuYpVkJ1z33HO\ndTnnujo7O5OqAtA0P75n8LaFK8KP6QhZalSSxn8ifP/KteH7AeRLIgHbzNrlBev7nHP/kEQZQDNN\n/GT4/imTBm97vMayoCdq3Myj91T4/g113N86bD1yAK0tiVniJmmjpJ8755iTilx489f1HZfUjPGr\nb67vuEbv+AUgPUn0sOdKulbSZWb2Yv+jwfsUASj3/R1p1wBAs7XFnaFzbpckiztfoNVN7pCOHE+v\n/DkXpFc2gOSx0hkQUa3h7cNDXMGs3Mc+JC24WPqdqfXn8dzm8P0sXwpkW+w9bKDIXHdwYFw0t7H7\nZV9+o7T9ueByAeQbARsYgtXrpbU3hafp3SGNm++9PrJdmtRRuf/6W6V7H41e5txZ0q6N0hN3D2w7\ncEiacaX3OkrP/osxr5gGoPnM1bpVUMK6urpcd3d+uwfepPn8SvvfTzNUt2GU3qx1DaTbul1atiY8\n/VB89+vSsssHl1OrPkHy3ob8DWZf3ttQ0h7nXM2TVgTshOX9H1ra/36aoboNJ46Tjj0Z4biI54yX\nzJNuWCLNny2dOCX9ZJ902ybpZ/trHxslWE+4LPxyrry3IX+D2Zf3NlTEgM2QODBEPb31H7ttnReg\ng4wfI82YIl2zsHL7rhelSz9fX5lcew3kAwEbqEOUoejSBLT2NundqsliQ5mx7bqlj184UF77HOnM\n2caHwgFkCwEbqFPU88elYF1v8Cw/7uwL0unno+VFsAbyheuwgQYsvaV2GusKDp63LpdOPO0F/tKj\nb7e33c+wi6MF4j/+cu00ALKFSWcJy/tkibT//TRDrTYM6mVXB9ar5ksP3VV/PZat8Wac11N2mLy3\nIX+D2Zf3NhSTzoDmsC7p7V3SqJGD9/U8JU0YW7lt9Dzprb7o+XeMkd78kbTlNu8hSd/YLN1y9+C0\nS2+R7v9h9LwBZAcBG4jBuR/3nqt7vG3DpOlXSq8eqj/v4ycre8y/fHRwT1vinDWQd5zDBmJUHjRd\nt/TwzsaCtZ/zF3vXbZf/OCBYA/lHDxuImXVJ40dLx5+WrrvCeySlc0Fj14UDyA562EACTpzyAvfK\ntcnkv+JOL3+CNVAc9LCBBG3Y4j2keO6oxdA3UFz0sIEmKV2PbV0Dd/Mqt3r94G3nXV55HIDioocN\npODXb/kH4HX3Nb8uALKBHjYAABlAwAYAIAMI2AAAZAABGwCADEj95h9mluuV69P+fpNWgEX5acOM\no/2yrwBtyM0/cu3sCenFjopNq9dLa2+qSjfzkNT+/ubVCwCQCHrYCYv1+90Twy/p2fF+3fy6z768\ntyHtl30FaMNIPWzOYbe6I3d6gTqOYC0N5HUkoTUzAQCJoIedsLq/39NvSvsmxlsZPzMPS+2T6z6c\nX/fZl/c2pP2yrwBtyDnszIqrNx3FvvO855iHygEA8WJIvNU0M1i3QrkAgEgI2K1i74j0g+Yek45v\nTbcOAABfBOxWsMck927D2dx4Rwx1ObAs/R8OAIBBmHSWsJrf796RkvttQ2X43fWp4Xsv23Dpotr1\nYsJL9uW9DWm/7CtAG3JZVyZECNadC6T7fuC/L+geyQ3fOzmGHj8AID70sBMW+v3WGHqO0nMOC8y1\n0n50hvTTB0KrUHP2OL/usy/vbUj7ZV8B2pAedkurEay/db//9np7zn7Hvbw/woGczwaAlkDATsOZ\nozWTrLizCfVQxB8AZ3oSrwcAIBwBOw0v1b+yWLWgyWUNTzor91JnjJkBAOrBSmfN9sbAtVdh56hd\nd/Thb9ctneqTxsyTTj4jjR4VvTqbvjLwOvSc+eH10nnVtwIDADQLPexmO/TnkoKD8cGy0fK5swbv\nD+o5l4J0ULAOOu76Jd7zrw7773+vnq+v8k8AAGgKAnaLmbZo4PWujZWBNmyY+8NXe88TLgtOU51X\n+fvzFw+tngCA5iJgN1ODM65fD5mr9spr3vPxk8FpwvZFwoxxAEgNAbvFLJobvG/qouB9UYT1vhdf\n2ljeAIBkEbBT0rfbf/tjG5pbj5JH1vtvf+fZ5tYDAOCPgN0spytndZ0zwjuHfM6IgW1RLsXa/Eh9\nxT+8s3aa8vJHjfTejxxelej0sfoqAABoCEuTJuy97zfk/O+Zs1L7nP70PkG7ekZ5dZry4yXp2JPS\nxHFDy6M8Te8Oaez7AqtbsVwpyyJmX97bkPbLvgK0IUuTZkXbsMaOH35J5fvOBY3lFxqsAQCpIGC3\nmCiLpSxdU/m+1o/Pz30tnnIBAOmJPWCb2Ugze8HMXjKzl83sq3GXUXT3bx9a+k3bkqkHAKB5kuhh\n/1bSZc65WZIulPRpM7ukxjG5t2pd9LTN7u0OpbyhfA4AQHxiD9jO81b/2/b+R75nDESwLuaVPb9w\ne7R0cd/1K+7PAQCIJpFz2GY2zMxelHRU0g+dc89X7V9uZt1mFuc9pXJl8crw/d9+0Hveudd//7Zn\nvOeg+2qXXLW68v11V9SuGwCg+RK9rMvMxkl6SNIXnXM/DUiT6953lMu6JGnGldKBQ1XH9v+cCRqy\nrnVHr7D9QXlHui0nl3XlSt7bkPbLvgK0YfqXdTnneiXtkPTpJMvJgx/fM3jbwhXhx3SELDUqSeM/\nEb5/5drw/QCA1pHELPHO/p61zOwcSQsk/Wvc5WTOrPAVwqZMGrzt8RrLgp6ocTOP3lPh+zdsCd/v\na2ZPHQcBABrVlkCe75d0r5kNk/eD4AHn3KMJlJMtbRPrOiypGeNX31znge0TYq0HACCa2AO2c26f\npN+LO1/E6/s70q4BAGAoWOmshUzuSLf8ORekWz4AIBg3/0jYoO+3xmzxeofAP/YhL+AfOCT94mB9\nedScIT57cFMxQzX78t6GtF/2FaANI80ST+IcNhoQdinWormN3S/78hul7c8FlwsAaF0E7Gabepd0\nMHzGV+8Oadx87/WR7dKkqqHy62+V7h3CNL65s6RdG6Un7h7YduCQd+23JB2Osjb5tL+KXiAAIHYM\niSfM9/utMSwueb3sUq9363Zp2Zrw9EPx3a9Lyy4fXE4on+FwieG4PMh7G9J+2VeANow0JE7ATpjv\n93v6mLTP58LrKlHPZy+ZJ92wRJo/WzpxSvrJPum2TdLP9keoX5RgPbMn8HIu/rPIvry3Ie2XfQVo\nQ85ht6z2zroP3bbOC9BBxo+RZkyRrllYuX3Xi9Kln6+zUK69BoDU0cNOWOj3G3FovL1Neve5wdsj\n16GqF90+RzpztrGh8Pfqwa//wb/SAAAgAElEQVT7zMt7G9J+2VeANqSH3fJmu0hBuxSs673kq/y4\nsy9Ip5+PmFeNYA0AaB4WTknb9NoLeltXcIC9dbl04mmvt1x69O32tvsZdnHEYD39exESAQCahSHx\nhEX6fgN62dWB9ar50kN31V+XZWu8GeflAofFI/auGY7Lvry3Ie2XfQVoQ2aJt4LI3+/eUZJ7p2KT\ndUk9T0kTxlYmHT1Peqsveh06xkhv/qhy2zc2S7fc7ROwp2+ROpZGzpv/LLIv721I+2VfAdqQc9iZ\nclF/BK7qbbcNk6ZfKb16qP6sj5+s7K3/8tHBPW1JnLMGgBbGOexWUxY0Xbf08M7GgrWf8xd7121X\n9K4J1gDQ0hgST1jd3+/p49K+Jlz/PPNoQ9eFMxyXfXlvQ9ov+wrQhpGGxOlht6r2Dq/XO219MvlP\n2+Dl30CwBgA0Dz3shMX6/Ua4ZrummIe++XWffXlvQ9ov+wrQhvSwc2e2G3jMOjFo92q/zvjMNyqP\nAwBkEj3shKX9/SaNX/fZl/c2pP2yrwBtSA8bAIC8IGADAJABBGwAADIg9ZXOZs+ere7uKPd5zKa8\nn1/K+7kliTbMOtov+/LehlHRwwYAIANS72EDANAsgXcoHIJItyhOAD1sAECu3XytF6jjCNbSQF6r\nroknv6gI2ACAXOoY4wXWO7+UTP5rb/Lyn9SRTP7VGBIHAOROXL3pKI7036446aFyetgAgFxpZrBu\nZrkEbABALvzm2fSCdYnrlv70U8nkTcAGAGSe65ZGDG88nxvvaDyPrbcn88OBc9gAgEx7Z3fjeZSf\nf/7rB7znRoPub56VRv5hY3mUo4cNAMi0kSNqp+lcIN33A/99QZPFGp1EFkePvxwBGwCQWbV6wdbl\nPXp6pc/+ZeNBuJRf6XHBnzRWv6EgYAMAMqlWMPzW/f7b6w3afse9vL/2cXEFbQI2ACBzOiMsVrLi\nzuTrIUX7ATBhbOPlELABAJlzdHt8eQX1gOMczu55qvE8mCUOAMiUP7t24LVf77YUaF139OFv1y2d\n6pPGzJNOPiONHhW9Ppu+Eq0+K5dJ39wSPd9q9LABAJlyR//a4EHB+ODRgddzZw3eH9RzLgXpoGAd\ndNz1S7znXx3231+q5/rV/vujImADAHJl2qKB17s2VgbasGHuD1/tPU+4LDhNdV7l789fPLR6DhUB\nGwCQGY2eV379aPC+V17zno+fDE4Tti+KRupPwAYA5MqiucH7pi4K3hdFWO978aWN5V0LARsAkEl9\nAUuSPrahufUoeWS9//Z3no0nfwI2ACATJk+ofH/OCG+I+ZyypUmjDDlvfqS+8h/eWTtNefmjRnrv\nR1YtUTpxXH3lE7ABAJlw+An/7X27pdPPe6+jXMZ1w1cHbztztvJ9T+/gNFdFmOVdKr93h/T2Lv80\nx56snY8fAjYAIPPahjV2/PBLKt93Lmgsv7Hva+x4PwRsAECuROllL11T+d658PSf+1o85TYikYBt\nZsPM7J/N7NEk8gcAoBH3D3Fp003bkqnHUCTVw/6SpJ8nlDcAoIBWrYueNunebiPlDeVzlIs9YJvZ\nVElXSLon7rwBAMW1blW8+X3h9mjp4r7rV72fI4ke9jclfVnSfw9KYGbLzazbzLqPHTuWQBUAAEW3\neGX4/m8/6D3v3Ou/f9sz3nPQfbVLqmePX3dF7brVI9aAbWaLJR11zu0JS+ec+45zrss519XZ2Rln\nFQAABTX9A5XvHwu4rKra/OX+2z8TsSdcfX32vT6XjcUh7h72XElXmtmrkrZKuszM/i7mMgAAGOTH\nPidiF64IP6YjZKlRSRr/ifD9K9eG749TrAHbOXeLc26qc+6DkpZK+pFz7rNxlgEAKKaJnwzfP2XS\n4G2P11gW9ESNm3n0ngrfv6GO+1uHrUcehuuwAQCZ8Oav6zsuqRnjV99c33H13vGrrb7DanPO7ZC0\nI6n8AQBI0/d3NLc8etgAgNyY3JFu+XMuSC5vAjYAIDNqDW8fHuIKZuU+9iFpwcXS70ytP4/nNofv\nb2R4PrEhcQAA0uC6gwPjormN3S/78hul7c8Fl5skAjYAIFNWr5fW3hSepneHNG6+9/rIdmlS1VD5\n9bdK9w7hbhdzZ0m7NkpP3D2w7cAhacaV3usoPfsvNrhimrlatyhJWFdXl+vuTvhnSYrMLO0qJCrt\nfz/NQBtmG+2XfX5tGKU3a10D6bZul5atCU8/FN/9urTs8sHl1KpPgD3OuZqD5QTshPGfRfbRhtlG\n+2WfXxtOHCcdezLCsRHPGS+ZJ92wRJo/WzpxSvrJPum2TdLP9tc+NkqwnnBZ6OVckQI2Q+IAgMzp\n6a3/2G3rvAAdZPwYacYU6ZqFldt3vShd+vn6yqz32utyBGwAQCZFGYouTUBrb5PerZosNpQZ265b\n+viFA+W1z5HOnG14KHxICNgAgMyKev64FKzrDZ7lx519QTr9fLS84lxljeuwAQCZtvSW2mmsKzh4\n3rpcOvG0F/hLj77d3nY/wy6OFoj/+Mu10wwFk84SxoSX7KMNs432y74obRjUy64OrFfNlx66q/66\nLFvjzTivp+wQTDoDABSDdUlv75JGjRy8r+cpacLYym2j50lv9UXPv2OM9OaPpC23eQ9J+sZm6Za7\nB6ddeot0/w+j5x0VARsAkAvnftx7ru7xtg2Tpl8pvXqo/ryPn6zsMf/y0cE9bSm5O4NJnMMGAORM\nedB03dLDOxsL1n7OX+xdt13+4yDJYC3RwwYA5JB1SeNHS8eflq67wnskpXNBY9eFR0UPGwCQSydO\neYF75dpk8l9xp5d/M4K1RA8bAJBzG7Z4DymeO2olPfQdhB42AKAwStdjW9fA3bzKrV4/eNt5l1ce\nlxZ62ACAQvr1W/4BeN19za9LFPSwAQDIAAI2AAAZQMAGACADUl9L3MxyvRBu2t9v0vK+TrNEG2Yd\n7Zd9BWjDSGuJ08MGACADmCUOIDZZvsYVaHX0sAE05OZrB+4hHIdSXquuiSc/IC84h52wtL/fpHH+\nLPvqbcPS7QaTNvmPpKPH6z+e9su+ArQh98MGkIy4etNRHOm/hSFD5Sg6hsQBDEkzg3UrlAu0CgI2\ngEh+82z6QdN1S3/6qXTrAKSFgA2gJtctjRjeeD433tF4HltvT/+HA5AGJp0lLO3vN2lMeMm+Wm34\nzm5p5IgGy/A5/9xo0P3tu9LIP6ydrujtlwcFaEMWTgHQuCjBunOBdN8P/PcFTRZrdBJZHD1+IEvo\nYScs7e83afy6z76wNqzVC47Scw4LzLXSfnSG9NMHhl6HijIK3H55UYA2pIcNoH61gvW37vffXm/P\n2e+4l/fXPo7z2SgKAjaAQTo7aqdZcWfy9ZCi/QCYMDb5egBpI2ADGOTo9vjyCuoBx9kz7nkqvryA\nVsVKZwAq/Nm1A6/DzlG77ujD365bOtUnjZknnXxGGj0qen02fSVafVYuk765JXq+QNbQwwZQ4Y4v\nec9Bwfjg0YHXc2cN3h/Ucy4F6aBgHXTc9Uu8518d9t9fquf61f77gbwgYAMYkmmLBl7v2lgZaMOG\nuT98tfc84bLgNNV5lb8/f/HQ6gnkDQEbwHsaPa/8+tHgfa+85j0fPxmcJmxfFMwYR54RsAEMyaK5\nwfumLgreF0VY73vxpY3lDWQdARuAr77d/tsf29DcepQ8st5/+zvPNrceQFoI2AAkSZMnVL4/Z4Q3\nxHxO2dKkUYacNz9SX/kP76ydprz8USO99yOrliidOK6+8oFWx9KkCUv7+00ayyJmX6kNw4LxmbNS\n+xwFpqueUV6dpvx4STr25ODAWiuP8jS9O6Sx7wuub3leRWm/PCtAG7I0KYB4tA1r7Pjhl1S+71zQ\nWH5hwRrIKwI2gCGJsljK0jWV72t1kD73tXjKBfIskYBtZq+a2b+Y2YtmxoUWQMHcP8SlTTdtS6Ye\nQJ4k2cP+hHPuwijj8gDSt2pd9LTN7u0OpbyhfA4gSxgSByBJWrcq3vy+cHu0dHHf9SvuzwG0iqQC\ntpO03cz2mNny6p1mttzMuhkuB7Jr8crw/d9+0Hveudd//7ZnvOeg+2qXXFW1Rvh1V9SuG5BHiVzW\nZWYfcM4dMrNJkn4o6YvOuWcC0uZ6vn4BLkdIuwqJK0ob1rrGesaV0oFDldtKxwQNWde6o1fY/qC8\no1wLzmVd+VKANkzvsi7n3KH+56OSHpJ0cRLlAGieH98zeNvCFeHHdIQsNSpJ4z8Rvn/l2vD9QJHE\nHrDN7FwzG116LemPJP007nIAxGviJ8P3T5k0eNvjNZYFPVHjZh69p8L3b6jj/tZh65EDWdaWQJ6T\nJT3UP0zTJum7zrnHEygHQIze/HV9xyU1Y/zqm+s7rtE7fgGtKvaA7ZzbL8nntvYAEN33d6RdA6C1\ncFkXgMgmd6Rb/pwL0i0fSBM3/0hY2t9v0pihmn3VbVhrFna9Q+Af+5AX8A8ckn5xsL486qlb0dov\njwrQhpFmiSdxDhtAjoVdirVobmP3y778Rmn7c8HlAkVGwAZQYfV6ae1N4Wl6d0jj5nuvj2yXJlUN\nlV9/q3Tvo9HLnDtL2rVReuLugW0HDnnXfkvS4Qhrk38x5hXTgFbDkHjC0v5+k8ZwXPb5tWHUxUlK\n6bZul5atCU8/FN/9urTs8sHl1KqPnyK2X94UoA0jDYkTsBOW9vebNP6zyD6/Npw4Tjr2ZIRjI57P\nXjJPumGJNH+2dOKU9JN90m2bpJ/tr31slGA94bLgy7mK2H55U4A25Bw2gPr09NZ/7LZ1XoAOMn6M\nNGOKdM3Cyu27XpQu/Xx9ZXLtNYqAHnbC0v5+k8av++wLa8OoQ9HtbdK7zw3eHlV1Oe1zpDNnGxsK\nfy/vArdfXhSgDelhA2hM1PPHpWBd7yVf5cedfUE6/Xy0vJp9X24gTSycAiDU0ltqp7Gu4OB563Lp\nxNNe4C89+nZ72/0MuzhaIP7jL9dOA+QJQ+IJS/v7TRrDcdkXpQ2DetnVgfWq+dJDd9Vfl2VrvBnn\n9ZQdhPbLvgK0IbPEW0Ha32/S+M8i+6K24du7pFEjq47tknqekiaMrdw+ep70Vl/0OnSMkd78UeW2\nb2yWbrl7cMBeeot0/w+j5037ZV8B2pBz2ADic+7HvefqANo2TJp+pfTqofrzPn6yssf8y0cH97Ql\nzlmj2DiHDWBIyoOm65Ye3tlYsPZz/mLvuu3yHwcEaxQdQ+IJS/v7TRrDcdlXbxuOHy0dfzrmyvjo\nXNDYdeG0X/YVoA0jDYnTwwZQlxOnvF7vyrXJ5L/izv5z5A0EayBP6GEnLO3vN2n8us++ONswjjtq\nxT30TftlXwHakB42gOYqXY9tXQN38yq3ev3gbeddXnkcAH/0sBOW9vebNH7dZ1/e25D2y74CtCE9\nbAAA8oKADQBABhCwAQDIgNRXOps9e7a6u2OYWtqi8n5+Ke/nliTaMOtov+zLextGRQ8bAIAMIGAD\nAJABqQ+JAwBayJ4Yhp9n53+YPg30sAGg6I7c6QXqOIK1NJDXkYTWrS0oAjYAFNXpN73AevDLyeR/\n8GYv/9NHksm/YBgSB4Aiiqs3HcW+87xnhsobQg8bAIqmmcG6FcrNCQI2ABTF3hHpB809Jh3fmm4d\nMoqADQBFsMck927D2dx4Rwx1ObAs/R8OGcQ5bADIu70jG86i/Nanf/2A99zw/c/3jpAu+m2DmRQH\nPWwAyDtXOyh2LpDu+4H/vqD7lDd8//IYevxFQsAGgDyrMfRsXd6jp1f67F82HoRL+ZUeF/xJY/XD\nAAI2AORVjWD4rfv9t9cbtP2Oe3l/hAMJ2pEQsAEgj84crZlkxZ1NqIci/gA405N4PbKOgA0AefTS\n5NiyCppc1vCks3IvdcaYWT4xSxwA8uaNgWuv/Hq3pUDruqMPf7tu6VSfNGaedPIZafSo6NXZ9JWB\n12H10eH10nk3Rc+4YOhhA0DeHPpzScHB+GDZaPncWYP3B/WcS0E6KFgHHXf9Eu/5V4f9979Xz9dX\n+SeAJAI2ABTOtEUDr3dtrAy0YcPcH77ae55wWXCa6rzK35+/eGj1RCUCNgDkSYMzrl8Pmav2ymve\n8/GTwWnC9kXCjPFABGwAKJhFc4P3TV0UvC+KsN734ksby7voCNgAkFN9u/23P7ahufUoeWS9//Z3\nnm1uPbKKgA0AeXG6clbXOSO8c8jnjBjYFuVSrM2P1Ff8wztrpykvf9RI7/3I4VWJTh+rrwI5R8AG\ngLzY937fzX27pdPPe6+jXMZ1w1cHbztztvJ9T+/gNFetrp13qfzeHdLbuwIS7ZtUO6MCImADQAG0\nDWvs+OGXVL7vXNBYfmPf19jxRZRIwDazcWb292b2r2b2czP7gyTKAQAMXZRe9tI1le+dC0//ua/F\nUy6CJdXD3iDpcefc/yhplqSfJ1QOACAB928fWvpN25KpBwbEHrDNbIykeZI2SpJz7l3nnM/ZDgBA\nnFati5622b3doZQ3lM9RJEn0sGdIOiZpk5n9s5ndY2bnJlAOAKDMuphX9vzC7dHSxX3Xr7g/R14k\nEbDbJF0k6W+cc78n6W1Jf1GewMyWm1m3mXUfO8b0fQBIw+KV4fu//aD3vHOv//5tz3jPQffVLqme\nPX7dFbXrhsGSCNgHJR10zvVfRKC/lxfA3+Oc+45zrss519XZyS3VAKAZpn+g8v1jQZdVVZm/3H/7\nZyL2hKuvz77X57Ix1BZ7wHbOHZb0mpl9pH/TJyX9LO5yAABD8+N7Bm9buCL8mI6QpUYlafwnwvev\nXBu+H9EldT/sL0q6z8yGS9ov6YaEygEAlMw6Jr0UPGo5xWc9ksdrLAt6osbNPHpPhe/fsCV8v6+Z\nPXUclH+JBGzn3IuSuOIOAJqpbWJdhyU1Y/zqm+s8sH1CrPXIC1Y6AwAk4vs70q5BvhCwAaBAJnek\nW/6cC9ItP8sI2ACQJ7PD1xA9PMQVzMp97EPSgoul35lafx7Pba6RoEb9iyypSWcAgBbluoPPWy+a\n29j9si+/Udr+XHC5qB8BGwDyZupd0sHwGV+9O6Rx873XR7ZLk6qGyq+/Vbr30ehFzp0l7dooPXH3\nwLYDh6QZV3qvI/Xsp/1V9AILiCFxAMibybVvTF26vaXr9oL11u1er7v0GEqwlqTdL1Uev+UJb6GW\nUq860rnzSV8cWqEFY67WPdMS1tXV5bq78ztOYmZpVyFRaf/7aQbaMNsK236nj0n7fC68rhL1kq4l\n86QblkjzZ0snTkk/2Sfdtkn62f4IdYzyX/zMnsDLufLehpL2OOdqtgRD4gCQR+31L/u8bZ0XoIOM\nHyPNmCJds7By+64XpUs/X2ehXHtdEwEbAPJqtpP2hPdOSxPQ2tukd6smiw1lQRXXLX38woHedPsc\n6czZiL1rZoZHQsAGgDyLELSlgWBd76pn5cedfUE6/XzEvAjWkTHpDADybnrtBb1Lk8X83LpcOvG0\n11suPfp2e9v9DLs4YrCe/r0IiVDCpLOE5X2yRNr/fpqBNsw22q9fQC+7OrBeNV966K7667NsjTfj\nvFzgsHjE3nXe21BMOgMAvGe2k/aOktw7g3b1PCVNGFu5bfQ86a2+6Nl3jJHe/JG05TbvIUnf2Czd\ncrdP4ulbpI6l0TOHJAI2ABTHRf0RuKq33TZMmn6l9Oqh+rM+frKyt/7LRwf3tCVxzroBnMMGgKIp\nC5quW3p4Z2PB2s/5i73rtiuGwwnWDaGHDQBFNNtJp49L+ybouiuk665IsKyZRxu6LhweetgAUFTt\nHV7gnrY+mfynbfDyJ1jHgh42ABTdpJXeQ4p0zXZNDH0ngh42AGDAbDfwmHVi0O7Vfp3xmW9UHodE\n0MMGAPhrGzcoAK/9u5TqAnrYAABkAQEbAIAMIGADAJABqa8lbma5nqGQ9vebtAKs8UsbZhztl30F\naMNIa4nTwwYAIANyM0s80k3Sa6j3PrAAACQt0z3sm68duDdrHEp5rbomnvwAAIhLJs9hl27jlrTJ\nfyQdPd5YHml/v0nj/Fn25b0Nab/sK0Ab5vN+2HH1pqM40n9rOIbKAQBpy9SQeDODdSuUCwBASSYC\n9m+eTT9oum7pTz+Vbh0AAMXV8gHbdUsjhjeez413NJ7H1tvT/+EAACimlp509s5uaeSIBvP3Of/c\naND97bvSyD+Mljbt7zdpTHjJvry3Ie2XfQVow+wvnBIlWHcukO77gf++oMlijU4ii6PHDwDAULRs\nD7tWLzhKzzksMNdK+9EZ0k8fGHodBpWT/1+GaVchcbRhttF+2VeANsxuD7tWsP7W/f7b6+05+x33\n8v7ax3E+GwDQLC0XsDs7aqdZcWfy9ZCi/QCYMDb5egAA0HIB++j2+PIK6gHH2TPueSq+vAAACNJS\nK5392bUDr8POUbvu6MPfrls61SeNmSedfEYaPSp6fTZ9JVp9Vi6Tvrkler4AAAxVS/Ww7/iS9xwU\njA8eHXg9d9bg/UE951KQDgrWQcddv8R7/tVh//2leq5f7b8fAIC4tFTArmXaooHXuzZWBtqwYe4P\nX+09T7gsOE11XuXvz188tHoCABC3lgnYjZ5Xfv1o8L5XXvOej58MThO2LwpmjAMAktQyATuKRXOD\n901dFLwvirDe9+JLG8sbAIBGtWTA7tvtv/2xDc2tR8kj6/23v/Nsc+sBACiulgjYkydUvj9nhDfE\nfE7Z0qRRhpw3P1Jf+Q/vrJ2mvPxRI733I6uWKJ04rr7yAQCopSWWJg0LxmfOSu1zvNd+6apnlFen\nKT9eko49OTiw1sqjPE3vDmns+4LrOyiv/C+pl3YVEkcbZhvtl30FaMPsLk1arm1YY8cPv6TyfeeC\nxvILC9YAACSl5QN2uSiLpSxdU/m+1g+zz30tnnIBAEhS7AHbzD5iZi+WPU6a2cq4ywly/xCXNt20\nLZl6AAAQp9gDtnPu35xzFzrnLpQ0W1KfpIfCjlm1Lnr+ze7tDqW8oXwOAACGIukh8U9K+oVz7pdh\nidatirfQL9weLV3cd/2K+3MAAFCSdMBeKmnQbTHMbLmZdZtZXeuDLa4xwP7tB73nnXv99297xnsO\nuq92yVVVa4Rfd0XtugEAkITELusys+GSDkn6qHPuSEi60Mu6JGnGldKBQ5XbSscEDVnXuqNX2P6g\nvKNcC85lXflDG2Yb7Zd9BWjD1C/rWihpb1iwjurH9/hkviL8mI6QpUYlafwnwvevXBu+HwCAZkoy\nYC+Tz3C4n4mfDN8/ZdLgbY/XWBb0RI2befSeCt+/oY77W4etRw4AQCMSCdhmNkrSpyT9Q5T0b/66\nznISmjF+9c31HdfoHb8AAAjSlkSmzrk+SRNqJmxR39+Rdg0AAKiUmZXOJnekW/6cC9ItHwBQbC1x\n84/S61qzsOsdAv/Yh7yAf+CQ9IuD9eVRb93S/n6TxgzV7Mt7G9J+2VeANow0SzyRIfGkhF2KtWhu\nY/fLvvxGaftzweUCAJCmlgrYq9dLa28KT9O7Qxo333t9ZLs0qWqo/PpbpXsfjV7m3FnSro3SE3cP\nbDtwyLv2W5IOR1ib/Isxr5gGAEC1lhoSl6IvTlJKt3W7tGxNePqh+O7XpWWXDy6nVn2CpP39Jo3h\nuOzLexvSftlXgDaMNCTecgF74jjp2JMRjot4PnvJPOmGJdL82dKJU9JP9km3bZJ+tr/2sVGC9YTL\nwi/nSvv7TRr/WWRf3tuQ9su+ArRhNs9h9/TWf+y2dV6ADjJ+jDRjinTNwsrtu16ULv18fWVy7TUA\noBlaroddEnUour1Neve5wdujqi6nfY505mzjQ+Hv5Z//X4ZpVyFxtGG20X7ZV4A2zGYPuyTq+eNS\nsK73kq/y486+IJ1+Plpezb4vNwCg2Fp64ZSlt9ROY13BwfPW5dKJp73AX3r07fa2+xl2cbRA/Mdf\nrp0GAIA4teyQeElQL7s6sF41X3rorvrrsWyNN+O8nrLDpP39Jo3huOzLexvSftlXgDbM5ixxP2/v\nkkaNrDquS+p5SpowtnL76HnSW33Ry+8YI735o8pt39gs3XL34IC99Bbp/h9Gz1sqxD+0tKuQONow\n22i/7CtAG2b7HHa5cz/uPVcH0LZh0vQrpVcP1Z/38ZOVPeZfPjq4py1xzhoAkK6WPoddrTxoum7p\n4Z2NBWs/5y/2rtsu/3FAsAYApC0TQ+LVxo+Wjj+dRG0qdS5o7LpwqRBDOWlXIXG0YbbRftlXgDaM\nNCSeqR52yYlTXq935dpk8l9xZ/858gaDNQAAcclkD9tPHHfUSmLoO+3vN2n8us++vLch7Zd9BWjD\n/Paw/ZSux7augbt5lVu9fvC28y6vPA4AgFaVmx52q0r7+00av+6zL+9tSPtlXwHasFg9bAAA8oyA\nDQBABhCwAQDIgFZY6axH0i+bWN7E/jKbIqXzS039jCnIexvSfjGi/WLX9M9XgDY8P0qi1CedNZuZ\ndUc5uZ9lef+MfL5s4/NlW94/n9S6n5EhcQAAMoCADQBABhQxYH8n7Qo0Qd4/I58v2/h82Zb3zye1\n6Gcs3DlsAACyqIg9bAAAMoeADQBABhQqYJvZp83s38zsFTP7i7TrEycz+1szO2pmP027Lkkws2lm\n9rSZ/dzMXjazL6Vdp7iZ2Ugze8HMXur/jF9Nu05xM7NhZvbPZvZo2nVJgpm9amb/YmYvmlkM9xBs\nLWY2zsz+3sz+tf9v8Q/SrlNczOwj/e1Wepw0s5Vp16tcYc5hm9kwSf+fpE9JOijpnyQtc879LNWK\nxcTM5kl6S9J/dc5dkHZ94mZm75f0fufcXjMbLWmPpKvy0n6SZN7qEOc6594ys3ZJuyR9yTn3XMpV\ni42ZrZLUJWmMc25x2vWJm5m9KqnLOZfLhVPM7F5JP3bO3WNmwyWNcs71pl2vuPXHi9clzXHONXNh\nr1BF6mFfLOkV59x+59y7krZK+kzKdYqNc+4ZScfTrkdSnHNvOOf29r8+JennkqakW6t4Oc9b/W/b\n+x+5+UVtZlMlXSHpnn58C9IAAAJTSURBVLTrgqEzszGS5knaKEnOuXfzGKz7fVLSL1opWEvFCthT\nJL1W9v6gcvYfflGY2Qcl/Z6k59OtSfz6h4xflHRU0g+dc3n6jN+U9GVJ/z3tiiTISdpuZnvMbHna\nlYnZDEnHJG3qP61xj5mdm3alErJU0pa0K1GtSAHbbzHa3PReisLM3ifpQUkrnXMn065P3JxzZ51z\nF0qaKuliM8vF6Q0zWyzpqHNuT9p1Sdhc59xFkhZK+o/9p6ryok3SRZL+xjn3e5LelpSruUCS1D/U\nf6Wk76Vdl2pFCtgHJU0rez9V0qGU6oI69J/XfVDSfc65f0i7PknqH2rcIenTKVclLnMlXdl/jner\npMvM7O/SrVL8nHOH+p+PSnpI3qm4vDgo6WDZqM/fywvgebNQ0l7n3JG0K1KtSAH7nyR92Mym9/+C\nWippW8p1QkT9E7I2Svq5c25d2vVJgpl1mtm4/tfnSFog6V/TrVU8nHO3OOemOuc+KO9v70fOuc+m\nXK1Ymdm5/RMi1T9U/EeScnPVhnPusKTXzOwj/Zs+KSk3kz7LLFMLDodLrXF7zaZwzp0xsxslPSFp\nmKS/dc69nHK1YmNmWyTNlzTRzA5K+opzbmO6tYrVXEnXSvqX/nO8krTGOfePKdYpbu+XdG//DNV/\nJ+kB51wuL3/KqcmSHuq/FWSbpO865x5Pt0qx+6Kk+/o7Pfsl3ZByfWJlZqPkXUn0H9Kui5/CXNYF\nAECWFWlIHACAzCJgAwCQAQRsAAAygIANAEAGELABAMgAAjYAABlAwAYAIAP+fzFY3dTllVswAAAA\nAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x2871fddf550>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_NQueens(dfts)"