A1 Uninformed Search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment 1: Uninformed Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Maxwell You*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Breadth-first and depth-first are two algorithms for performing\n",
    "uninformed search---a search that does not use\n",
    "knowledge about the goal of the search. I have implemented both\n",
    "search algorithms in python and tested them on some given examples and some of my own."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Required Code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this jupyter notebook, you must implement at least the following functions:\n",
    "\n",
    "  * `breadthFirstSearch(startState, goalState, successorsf)` \n",
    "  * `depthFirstSearch(startState, goalState, successorsf)`\n",
    "  \n",
    "Each receives as arguments the starting state, the goal state, and a successors function.  `breadthFirstSearch` returns the breadth-first solution path as a list of states starting with the `startState` and ending with the `goalState`.  `depthFirstSearch` returns the depth-first solution path.\n",
    "\n",
    "<font color=\"red\">You must</font> implement the search algorithm as specified in [A3 Problem-Solving Agents](http://nbviewer.jupyter.org/url/www.cs.colostate.edu/~anderson/cs440/notebooks/03 Problem-Solving Agents.ipynb) lecture notes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you prefer to develop your python code in a separate editor or IDE, you may do so.  If it is stored in a file called `A1mysolution.py`, you can use it here by executing the following cell.\n",
    "\n",
    "When your solution works, <font color=\"red\">Remember</font> to remove or comment out the following import statement and instead, paste in all of your function definintions into this notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# from A1mysolution import *\n",
    "def breadthFirstSearch(startState, goalState, successorsf):\n",
    "    expanded = {}\n",
    "    unExpanded = [(startState, None)]\n",
    "\n",
    "    if startState == goalState:\n",
    "        return [startState]\n",
    "\n",
    "    while unExpanded:  # check if unExpanded is empty\n",
    "        pair = unExpanded.pop()  # retrieve the next node to search\n",
    "        state = pair[0]\n",
    "        parent = pair[1]\n",
    "        expanded[state] = parent  # add state with respective parent to expanded\n",
    "        eStates = expanded.keys()  # retrieve expanded states, exclude parents\n",
    "\n",
    "        # removing from children any states already in expanded or unExpanded\n",
    "        if unExpanded:  # can only check for states in unExpanded if it is not empty\n",
    "            # zip(*unExpanded)[0] retrieves unExpanded states, excludes parents\n",
    "            # children should not be in either unExpanded or expanded\n",
    "            # zip object not superscript-able in jupyter, so have to typecast to list first\n",
    "            children = [x for x in successorsf(state) if (x not in list(zip(*unExpanded))[0] and x not in eStates)]\n",
    "        else:  # unExpanded is empty so can't check if children are in unExpanded, so just check if they're in expanded\n",
    "            children = [x for x in successorsf(state) if (x not in eStates)]\n",
    "\n",
    "        if goalState in children:\n",
    "            solution = [state, goalState]\n",
    "            while parent:\n",
    "                solution.insert(0, parent)\n",
    "                parent = expanded[parent]  # retrieve parent of current state\n",
    "            return solution\n",
    "\n",
    "        children = [i for i in reversed(sorted(children))]  # sort and reverse states in children\n",
    "        modifiedChildren = list(zip(children, [state for i in children]))   # have to typecast to list in jupyter because type\n",
    "                                                                            # is zip on there, but type is list in PyCharm\n",
    "        unExpanded = modifiedChildren + unExpanded  # insert children at the front for BFS\n",
    "\n",
    "def depthFirstSearch(startState, goalState, successorsf):\n",
    "    expanded = {}\n",
    "    unExpanded = [(startState, None)]\n",
    "\n",
    "    if startState == goalState:\n",
    "        return [startState]\n",
    "\n",
    "    while unExpanded:  # check if unExpanded is empty\n",
    "        pair = unExpanded.pop() # retrieve the next node to search\n",
    "        state = pair[0]\n",
    "        parent = pair[1]\n",
    "        expanded[state] = parent    # add state with respective parent to expanded\n",
    "        eStates = expanded.keys()   # retrieve expanded states, exclude parents\n",
    "\n",
    "        # removing from children any states already in expanded or unExpanded\n",
    "        if unExpanded:  # can only check for states in unExpanded if it is not empty\n",
    "            # zip(*unExpanded)[0] retrieves unExpanded states, excludes parents\n",
    "            # children should not be in either unExpanded or expanded\n",
    "            children = [x for x in successorsf(state) if (x not in list(zip(*unExpanded))[0] and x not in eStates)]\n",
    "        else:   # unExpanded is empty so can't check if children are in unExpanded, so just check if they're in expanded\n",
    "            children = [x for x in successorsf(state) if (x not in eStates)]\n",
    "\n",
    "        if goalState in children:\n",
    "            solution = [state, goalState]\n",
    "            while parent:\n",
    "                solution.insert(0, parent)\n",
    "                parent = expanded[parent]  # retrieve parent of current state\n",
    "            return solution\n",
    "\n",
    "        children = [i for i in reversed(sorted(children))]  # sort and reverse states in children\n",
    "        modifiedChildren = list(zip(children, [state for i in children]))   # have to typecast to list in jupyter because type\n",
    "                                                                            # is zip on there, but type is list in PyCharm\n",
    "        unExpanded = unExpanded + modifiedChildren  # insert children at the back for DFS\n",
    "        \n",
    "        children = list(zip(children, [state for i in children]))   # have to typecast to list because type is zip on\n",
    "                                                                    # jupyter, but is list in PyCharm\n",
    "        unExpanded = unExpanded + children  # insert children at the back for DFS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a simple example.  States are defined by lower case letters.  A dictionary stores a list of successor states for each state in the graph that has successors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': ['b', 'c', 'd'],\n",
       " 'b': ['e', 'f', 'g'],\n",
       " 'c': ['a', 'h', 'i'],\n",
       " 'd': ['j', 'z'],\n",
       " 'e': ['k', 'l'],\n",
       " 'g': ['m'],\n",
       " 'k': ['z']}"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "successors = {'a':  ['b', 'c', 'd'],\n",
    "              'b':  ['e', 'f', 'g'],\n",
    "              'c':  ['a', 'h', 'i'],\n",
    "              'd':  ['j', 'z'],\n",
    "              'e':  ['k', 'l'],\n",
    "              'g':  ['m'],\n",
    "              'k':  ['z']}\n",
    "successors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "def successorsf(state):\n",
    "    return copy.copy(successors.get(state, []))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['k', 'l']"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "successorsf('e')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Breadth-first\n",
      "path from a to a is ['a']\n",
      "path from a to m is ['a', 'b', 'g', 'm']\n",
      "path from a to z is ['a', 'd', 'z']\n"
     ]
    }
   ],
   "source": [
    "print('Breadth-first')\n",
    "print('path from a to a is', breadthFirstSearch('a', 'a', successorsf))\n",
    "print('path from a to m is', breadthFirstSearch('a', 'm', successorsf))\n",
    "print('path from a to z is', breadthFirstSearch('a', 'z', successorsf))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth-first\n",
      "path from a to a is ['a']\n",
      "path from a to m is ['a', 'b', 'g', 'm']\n",
      "path from a to z is ['a', 'b', 'e', 'k', 'z']\n"
     ]
    }
   ],
   "source": [
    "print('Depth-first')\n",
    "print('path from a to a is', depthFirstSearch('a', 'a', successorsf))\n",
    "print('path from a to m is', depthFirstSearch('a', 'm', successorsf))\n",
    "print('path from a to z is', depthFirstSearch('a', 'z', successorsf))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try a navigation problem around a grid of size 10 x 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def gridSuccessors(state):\n",
    "    row, col = state\n",
    "    # succs will be list of tuples () rather than list of lists [] because state must\n",
    "    # be an immutable type to serve as a key in dictionary of expanded nodes\n",
    "    succs = []\n",
    "    for r in [-1, 0, 1]:\n",
    "        for c in [-1, 0, 1]:\n",
    "            newr = row + r\n",
    "            newc = col + c\n",
    "            if 0 <= newr <= 9 and 0 <= newc <= 9:  # cool, huh?\n",
    "                succs.append( (newr, newc) )\n",
    "    return succs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5)]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gridSuccessors([3,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 8), (2, 9), (3, 8), (3, 9), (4, 8), (4, 9)]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gridSuccessors([3,9])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 0), (0, 1), (1, 0), (1, 1)]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gridSuccessors([0,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Breadth-first\n",
      "path from (0, 0) to (9, 9) is [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)]\n"
     ]
    }
   ],
   "source": [
    "print('Breadth-first')\n",
    "print('path from (0, 0) to (9, 9) is', breadthFirstSearch((0, 0), (9, 9), gridSuccessors))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth-first\n",
      "path from (0, 0) to (9, 9) is [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 9), (2, 8), (2, 7), (2, 6), (2, 5), (2, 4), (2, 3), (2, 2), (2, 1), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0), (9, 1), (8, 2), (7, 2), (6, 2), (5, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (5, 9), (6, 8), (6, 7), (6, 6), (6, 5), (7, 4), (8, 4), (9, 5), (8, 6), (8, 7), (8, 8), (9, 9)]\n"
     ]
    }
   ],
   "source": [
    "print('Depth-first')\n",
    "print('path from (0, 0) to (9, 9) is', depthFirstSearch((0, 0), (9, 9), gridSuccessors))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oooo, what kind of path is that?  Let's plot it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 0),\n",
       " (0, 1),\n",
       " (0, 2),\n",
       " (0, 3),\n",
       " (0, 4),\n",
       " (0, 5),\n",
       " (0, 6),\n",
       " (0, 7),\n",
       " (0, 8),\n",
       " (1, 9),\n",
       " (2, 8),\n",
       " (2, 7),\n",
       " (2, 6),\n",
       " (2, 5),\n",
       " (2, 4),\n",
       " (2, 3),\n",
       " (2, 2),\n",
       " (2, 1),\n",
       " (3, 0),\n",
       " (4, 0),\n",
       " (5, 0),\n",
       " (6, 0),\n",
       " (7, 0),\n",
       " (8, 0),\n",
       " (9, 1),\n",
       " (8, 2),\n",
       " (7, 2),\n",
       " (6, 2),\n",
       " (5, 2),\n",
       " (4, 3),\n",
       " (4, 4),\n",
       " (4, 5),\n",
       " (4, 6),\n",
       " (4, 7),\n",
       " (4, 8),\n",
       " (5, 9),\n",
       " (6, 8),\n",
       " (6, 7),\n",
       " (6, 6),\n",
       " (6, 5),\n",
       " (7, 4),\n",
       " (8, 4),\n",
       " (9, 5),\n",
       " (8, 6),\n",
       " (8, 7),\n",
       " (8, 8),\n",
       " (9, 9)]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path = depthFirstSearch((0, 0), (9, 9), gridSuccessors)\n",
    "path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlAVPX6x/H3lx33fcMFzRUFU9FU1MpccinX223fs27Z\novfmVl0tLTW7ZnvZfttupUjuW5Z7looCIoriiigoisq+fH9/oD8cYgSM4ZzDeV5/Bc3AwzNnPn7n\nzJnvo7TWCCGEsA43owsQQghROhLcQghhMRLcQghhMRLcQghhMRLcQghhMRLcQghhMRLcQghhMRLc\nQghhMRLcQghhMR6u+KF16tTR/v7+rvjRQghRIe3YseO01rpuSW7rkuD29/dn+/btrvjRQghRISml\njpT0tnKqRAghLEaCWwghLEaCWwghLEaCWwghLEaCWwghLMYlV5VYWVh4PHNW7ePEuXQa1fDl+YFt\nGN7Jz+iyhAnIsSGcKe9jQ4L7CmHh8UwOjSQ9OxeA+HPpTA6NBJAnqM3JsSGcMeLYkFMlV5izat//\nN/+y9Oxc5qzaZ1BFwizk2BDOGHFsSHBfIf5cepHfP+Hk+8I+nB0DcmwII44NOVUCnE3NYvrSaKf/\nv25V73KsRphJTm4en246hLOR2jUre5VrPcJcft2XiJtS5BYxdL1RDV+X/V5br7i11iyNOEG/uetZ\nvPsEAwPq4eP555acuZjJe78cIDs3z4AqhVH2Jpxn5AdbmLkihg6NquHj4XhsKCA5NYux3+7k9MVM\nY4oUhjibmsX4H3bx4Od/ULuKF96Fjg1fT3eeH9jGZb/ftivuU+czeDEsijXRpwj0q87Xj95Au4bV\n/vTu8OM3tmDboWTmrNrH0ogE5owOooNfdaPLFy6UmZPLe+sO8P6vB6lRyZP37u7M4MAG/LTrhMOx\nMa5fKxJSMnhn3QE2HzjN1NvaM+z6RiiljP4ThItorVkRdZJ//xTFubRsnu7bkrF9W7Ii8mS5XlWi\ndBFL/L8qODhYm3WTKa01P2w/xoxle8nKyWN8/9Y80qs5Hu5Xf/Gxas9JXgyLIjk1i8d6t+C5fq3w\n8XQvp6pFedlx5CwTF0ZwIPEiIzv78dKQgGJPh8SeusCEhRGEHz3HzW3q8uqIQJe+TBbGSDyfwUs/\nRbFqT/5ib/aoIAIaVSuzn6+U2qG1Di7Rbe0U3EfPpDEpNIItB89wQ/NazBoVRPM6lUt8/5S0bF5b\nvpfvtx+jRZ3KzBoVRLfmtVxYsSgvaVk5zFm1jy+2HKZhNR9eHRnIzW3qlfj+uXmaL7ccZs6qfbi7\nKSYOass93Zri5iarb6vTWvPjjuPMWBpNZk4e4/q35tESLPZKS4K7kNw8zRdbDvPGpSfV5MFtuavr\ntT+pNsWeZvKiCI4lp3Nf92ZMHNSWKt62PetkeZtiTzMpNILjZ9O5v0czJtx67Y/nseQ0JodGsunA\nabo1r8XsUi4OhLkUfjxnjQykRd0qLvldEtxX2H/qAhMWRLDr2Dn6tq3HqyM60LD6X38Zm5aVwxur\n9vP5lkPXtEITxktJz+bVZdH8sP14mb6C0lrz4/bjTF8WTZYLV2jCdQq/gpo0qC13u/gVlAQ3kJWT\nxwe/HuTdX2Kp4u3BtNvbc3vHsn/jaOfRs0xcEEFs4kVGdvLjpaHFnxMVxlu15yQvhUVxJjWLMX1a\n8OwtZf+exanzGbwUFsXqaNecExWuEXvqAhMXRrDz6DlualOX18rpPQvbB/fuY+eYuDCCmJMXuK1j\nI6bdFkDtKq67FvvKqxCq+3ry8rD2DAlsKFcXmFDShUymLd7DssgEAhpW43UXXyWktWZ55EmmLs6/\nCuEfN13H2L4t8faQN7bNJjs3jw9/Pcg76w5Q2du93K8Ssm1wp2fl8uba/XyyMY66Vb2ZMTyQ/gH1\ny+337004z4QFEUTGpzAgoD7Th3egfjWfcvv9wjmtNaE743llaTTpWbk8268VY/q0wLOcTl+cTc1i\n+rJoQnfG07JeFWaPCqJLs5rl8rtF8SKPp/D8gt3EnLzA0KCGTLu9PXVcuNgrii2De+vBM0wOjeDw\nmTTu6taUyYPbUs3Hs1xrgIJP2s1dsx8vDzdeHNKOO4KbyOrbQPHn0pkSGsn6/Ul0aVaT2aOCaFnP\nNW8wFefXfYm8sCiKEynpPNjTn+cHtqGSl7yxbZSM7PzF3scb8hd704d1YED7BobUYqvgPp+RzawV\nMXy77SjNaldi5shAel5Xp1x+99UcOp3KxIUR/H4omZCWtZk5IoimtSsZXZat5OVpvt52hNkrYtDA\nhIFtuL+Hv+GX6F3MzOH1lTH8d+sRGtf0ZdbIIHq1Mv6YtZvf4s4waeHlxV4TJg1qR3Xf8l/sXWab\n4F4Xc4opoVEkXsjgkV7NGd+/Db5e5jl3mJen+e6Po8xcHkNunuZfA9vwYE9/3OXaXpc7mHSRSQsj\n+OPwWXq3qsNrIwJpUstc/3D+fiiZSQsjiDudyh3BjXlhcADVKxkXHHZx4dJi75ttR2laqxKzRgbS\ns6Xx/3BW+OA+czGTV5ZG89OuE7SpX5XZo4O4vkkNl/2+vyohJZ0XFkWxLiaRTk1r8PqoIFrVr2p0\nWRVSdm4eH2+MY97aWHw93XlpaACjOvuZ9lRVRnYub/0cy/wNcdSq7MX0YR24tYMxL9Xt4JeYRKYs\niuTU+QweDmnO+AGtTXOqqsIGt9aaxbtP8PKSaC5kZPPUzS158qaWeHmY//rYy7VPW7yHi5k5PN23\nFU/ceJ0lareKqPgUJi6MYM+J8wzq0ICXh7WnXlVrvDkcFZ/ChAURRCecZ0hg/ptjsitl2UlOzeKV\nJXsI23WC1vXz3xzu1NRcbw5XyOBOSEnnxUVR/ByTSMcm+avWNg2st2o9czGTaUuiWbL7BG0bVGX2\nqCA6mvjVghVkZOfyzrpYPlwfR81KXkwf1p5BgQ2NLqvUsnPzmL8hjrd+zn+18O+hAYw08asFK9Ba\nsyQigWmL93AhI5snb2rJUzebc7FXoYI7L0/zvz+OMXP5XrLz8vjXgDY8FNLc8ueJ10Sf4sWwSJIu\nZF7atKq1qc7PW8X2w8lMWBhBXFIqo7s05sUh7ahRydofgDqQeJGJCyPYceQsN7auy2sjA/GTTatK\n7WRK/g6ga/eeomPj6sweHUTbBub9AFSFCe7Dp1OZFBrBb3HJ9GhRm1mjAmlWu+Ls+3A+I5uZy/fy\n3e/H8K9diVmjgujeorbRZVlCamb+plBfbj1Mo+q+zBwZSJ/WdY0uq8zk5Wm++u0Is1fGoICJg9py\n7w3NDL8ixgq0zl/svbYsf7H3z/5teLiX+Rd7ZR7cSqlxwKOABiKBh7TWGc5ufy3BfeU+2A1r+NC1\nWS1WRZ/E082NF4a04+9dK+610FsOnGZSaCRHk9O454amBPpV4511B2Wa+CWF90i/rWNDluxO4ERK\nOg/0yL8WunIF3eTrWHIaUxZFsjH2NF39azJrVBCRx1Nk2vwlhY+Nh0L8+XlvIlvjztC9RS1mjQzC\n3yKbfJVpcCul/IBNQIDWOl0p9QOwXGv9hbP7lDa4C09Jvqx9o2p8+kBXGlS3xhtMf0V6Vi5z1+zj\n442H/vT/fD3dmTky0JZPTmfHRr2qXrx/TxeC/Sv+trpaaxbujGf60mguZmSjlCInr+B5a9fjw9mx\n4e2umDasA38PbmKpVyilCe6SnqH3AHyVUh5AJeDEtRZXlKKmJAOcS8uyRWgD+Hq588KQAOoW8TFb\nO08Td3ZseLi52SK0AZRSjO7SmDXj++Dp4eYQ2mDf48PZsVGzsjd3VfC90IsNbq11PPAGcBRIAFK0\n1qsL304pNUYptV0ptT0pKalURTifkuz0bEyF5Wx2oV2niTv7uxNS7Hds1KvqQ2Z20XNP7Xh8OPub\nT52v+MdGscGtlKoJDAOaA42AykqpewvfTms9X2sdrLUOrlu3dG8SOdsy0Y7jn6QXjqQfjqQfBezc\ni5KcKukHHNJaJ2mts4FQoGdZFvH8wDb4FtoL2dVTks1KeuFI+uHo+YFt8PEs34niZmXnY6Mkb8Uf\nBborpSoB6cAtQJl+uubymyrjvt+FBvxs/E755b/5laV7SE7Npl5Vb6YMbmfLXkBBPyYtjCAjJ8/W\nxwbk9yMzO5eJoZGAPFcApi7eQ0p6Ng2q+TBpUFtb9KLY4NZab1NKLQB2AjlAODC/rAsZ3smPyaGR\n3NejGVMGtyvrH28pwzv54ePpxhNf7+TLh7vRrqF5PzRQHoZ38mN5ZAJHk9NY+Vwfo8sx3NCOjZgY\nGsmUwW0Z0+c6o8sx1PBOflzIzOGlsCiWPN3LNtsElOjiV631VGCqi2sRQghRAub7wL4QQoirkuAW\nQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAWQgiL\nkeAWQgiLkeAWQgiLMU1wh4XHk5Gdy/wNcYTMWkdYeLzRJRkmLDyeKYvy91t+4LPfbd0LyO/Hhv1J\nxJy8YPtjA2Dp7vyRr68tj7F9P8LC43nj0rzN297ZZJtelGhbV1e7PK358gjU+HPpTL60UbwdNkW/\nUuHJ1YkXMm3bCyjoR0ZO/qxFOx8bkN+PqUv2/P/Xdu5H4efKyfMZtumFKVbcRU1rlsnVBezaC5B+\nFDZn1T4yCg0Mtms/7HxsmCK4nU95l8nVxX2/opN+OJJ+FLBzL0wR3Hae1lyY9MKR9MOR9KOAnXth\niuC287TmwqQXjqQfjmTKewE7HxumeHNSprwXkCnvjmTKuyOZ8l5AprybgEx5LyBT3h3JlHdHMuW9\ngF2nvJviVIkQQoiSk+AWQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAW\nQgiLkeAWQgiLkeAWQgiLkeAWQgiLkeAWQgiLKVFwK6VqKKUWKKVilFJ7lVI9XF2YEEKIopV0xf0W\nsFJr3RboCOwt60JkynsBmfLuSKa8O5Ip7wVkyrsTSqnqQB/gQQCtdRaQVZZFyJT3AjLl3ZFMeXck\nU94LyJT3q2sOJAGfK6XClVKfKKUql2URdp7WXJj0wpH0w5FMeS9g52OjJMHtAXQGPtBadwJSgUmF\nb6SUGqOU2q6U2p6UlFSqIuw8rbkw6YUj6Ycj6UcBO/eiJMF9HDiutd526esF5Ae5A631fK11sNY6\nuG7duqUqws7TmguTXjiSfjiSfhRw9jd7ebhV+PAuNri11ieBY0qpy6OTbwGiy7IIO09rLkx64Uj6\n4UimvBco6tjwdFfk5Wn6z13PV78dIS9PO7m3tZV0WPDTwDdKKS8gDnioLIuQKe8FZMq7I5ny7kim\nvBe4/DfPWbWPE+fSaXSpF12a1WRyaGT+AOFdJ5g1KpAWdasYXG3ZUlqX/b9IwcHBevv27aW+X7uX\nVsqU90tWRiXwxNc7WfFsb9tPeQcY89/tMuX9ktTMHNpPXSVT3q9Ca82PO44zY2k0mTl5jOvfmkd7\nNcfD3byfOVRK7dBaB5fktub9K4QQ4hoppbgjuAlrx9/ITW3qMmtFDMPf30z0ifNGl1YmJLiFEBVW\nvWo+fHhvF96/pzMnUzK4/d1N/Gf1PjJzcou/s4lJcAshKjSlFIMDG7Jm3I0Mu96Pd9YdYMjbm9hx\nJNno0q6ZBLcQwhZqVvbiP3d05MuHu5GelcvoD7cybfEeUjNzjC6t1CS4hRC2cmPruqwa14f7uzfj\niy2HGThvAxtjS/ehQaNJcAshbKeKtwcvD+vAj0/0wMvDjfs+/Z3nf9xNSlq20aWViAS3EMK2uvrX\nYvkzvXnypusIDY+n35vrWRl10uiyiiXBLYSwNR9Pdybc2pafngqhbhVvnvh6B09+s4PECxlGl+aU\nBLcQQgAd/Krz09gQnh/YhrV7E+k/dwMLdhzHFR9S/KskuIUQ4hJPdzeeurkly5/pTat6VfjXj7t5\n4PM/OH42zejSHEhwCyFEIS3rVeGHx3vw8u3t2X44mQFvbuDLLYdNs2mVBLcQQhTBzU3xQE9/Vo/r\nQ7B/LaYu3sMdH23lYNJFo0uT4BZCiKtpXLMSXz7UlTf+1pHYxIsMemsj7/1ygOzcvOLv7CIS3EII\nUQylFKO7NGbN+D70a1ePOav2Mfy9zUTFpxhSj2mCW6a8F5Ap745kyrsjmfJunHpVfXj/ni58eG9n\nEi9kMuy9zby+MoYftx8jZNY6mk9aVi6PSUkHKbiUTHkvIFPeHcmUd0cy5d0cbu3QkB4t6jBjWTTv\n/3oQBeWaX6ZYcdt5WnNh0gtH0g9HMuXdPKpX8mTO3zpSu7IXha81cfVjYorgtvO05sKkF46kH46k\nH+aTnJpV5Pdd+ZiYIrhlcnUB6YUj6YcjZ393zUqepvyEX0WWl6f5YvMhp//flceoKYJbJnkXkF44\nkn44KqofSkFyWjZPfL2DxPPm3V+jIjmQeJE7PtrKtCXRtGlQFW8Pxyh19TFqijcnZcp7AZny7kim\nvDsqarL5P/u3IuliFnPX7OeWuet5aUgAfwtujFLK4GornuzcPOZviOOttbFU8nZn7h0dGdHJj592\nnfjTtHlXHqMy5d2kZMq7I5nyXry4pItMCo3k90PJ9GpZh5kjA2lSq5LRZVUYUfEpTFgQQXTCeYYE\nNmTa7e2pW9W7zH6+THkXwoZa1K3C/x7rzozhHdh17BwD3tzAZ5sOkWuS/TWsKiM7l9krYxj23maS\nLmby4b1deO+ezmUa2qVlilMlQoiy4eamuLd7M/q2rceURZG8sjSapREnmD0qiFb1qxpdnuX8cTiZ\niQsiiDudyh3BjXlhcADVK3kaXZasuIWoiBrV8OXzB7sy7+/Xc+h0KkPe3sQ7P8caur+GlVzMzOHf\nP0Xxtw+3kpWbx9eP3MDrozuaIrRBVtxCVFhKKYZ38qNXqzq8vCSa/6zZz7LIBF4fHURQ4xpGl2da\nv+5L5IVFUZxISefhkOb8a2BrKnmZKyplxS1EBVenijfv3NWJj+8P5mxaFsPf28zM5XvJKPSJVLs7\nm5rF+B928eDnf+Dr5c6CJ3ry79sCTBfaICtuIWyjf0B9ujWvxawVe/loQxyr9pxk1qggureobXRp\nhtJaszzyJFMXR3EuLZtn+rbkqb4t8fZwL/7OBpEVtxA2Ut3Xk5kjg/j20RvI03Dn/N94YVEkFzKy\njS7NEInnM3j8qx089e1OGlb3ZfHYXowf0MbUoQ2y4hbClnq2rMPK53ozd/V+Ptt8iHUxibw2IpCb\n29YzurRyobXmx+3Hmb4smqycPCYPassjvZrj4W6Ntaw1qhRClLlKXh68ODSAhf/oSVUfDx764g+e\n+1+4002TKopjyWnc9+nvTFgYQbuG1Vj5XB8ev/E6y4Q2yIpbCNvr1LQmS5/uzXu/HOD9Xw+wMfY0\n025vz9CghhXqY/O5eZovtxxmzqp9uLspZgzvwN3dmuLmZr2/UYJbCIGXhxvj+rdmUGADJi6I4Onv\nwvlp1wlmDO9Ag+o+Rpf3l8WeusCEhRGEHz3HzW3q8uqIQEvvMGmd1wZCCJdr26AaoU+G8MLgdmw6\nkET/uev57vejlt0yNisnj7d/jmXI25s4fDqVeX+/ns8e7Grp0AZZcQshCnF3UzzWpwX9A+ozKTSC\nyaGRLN51glmjAmlWu7LR5ZVYxPFzTFgQQczJC9zWsRFTbwugThXj9hcpSyVecSul3JVS4Uqppa4s\nSAhhDv51KvPto915bUQgUfEpDJy3gU82xpl+06qM7FxmLt/L8Pc2czYti4/vD+aduzpVmNCGUmzr\nqpQaDwQD1bTWQ69222vZ1jUsPF72474kLDxe9uO+Qlh4vOzHbbCElHReXBTFzzGJdGxSg9dHBbE3\n4Xy57kFdlLDweIcaRnRqxNKIBA6fSeOubk2YNKgd1X3Nsb9IcUqzrWuJglsp1Rj4EngVGF/WwV14\nsjnkT5CYOTLQdk9Q6YUj6Yd5aK1ZEpHAtMV7OJeWhZtS5Fyx+i7vx6WoYwOgVmVP3r2rMz1b1imX\nOspKaYK7pOe45wETAJfsC3m1Sd52e3JKLxxJP8xDKcXtHRvRq2UdQmatK/JxmbQwgmWRCeVSz8b9\nSWTk/Hm3Qx8Pd8uFdmkVG9xKqaFAotZ6h1LqpqvcbgwwBqBp06alKkImVxeQXjiSfphPrcpeTjeo\nysjJ4/jZ8nlsigptgISUij93syQr7hDgdqXUYMAHqKaU+lprfe+VN9JazwfmQ/6pktIU0aiGL/FF\nPBGtfsnOtZBeOJJ+mJOzx8Wvhi8rnu1dLjWEzFpn22Oj2KtKtNaTtdaNtdb+wJ3AusKh/VfJJO8C\n0gtH0g9zMsPjYoYajGKK67hlynsBmfLuSKa8m1NR0+bL+3ExQw1GkSnvJiVT3h3JlHdR0cmUdyGE\nqMAkuIUQwmIkuIUQwmIkuIUQwmIkuIUQwmIkuIUQwmIkuIUQwmIkuIUQwmIkuIUQwmIkuIUQwmIk\nuIUQwmIkuIUQwmIkuIUQwmIkuIUQwmJME9xh4fFkZOcyf0McIbPWERYeb3RJhgkLj2fKokgAHvjs\nd1v3AvL7sWF/EjEnL9j+2BACTDJI4fK05ss7g8efS2dyaH5w2WFT9CsVnlydeCHTtr2Agn5cni9o\n52NDiMtMseK+2iRvu5FeOJJ+CPFnpghumeRdQHrhSPohxJ+ZIridTWW2w7TmwqQXjpz93T6e7iSn\nZpVzNUKYgymC287TmguTXjgqqh8eboqM7Fz6zV3P4t0ncMXcVCHMzBTBPbyTHzNHBqIufe1Xw5eZ\nIwNt+ebT5V7UquwJQL2q3rbtBRT0w6+GL4r8Y+ONv3VkxXO9aVzTl2e+C+ex/+7gZEqG0aUKUW5k\nyrtJyZT34uXk5vH55sO8sXofXu5uTBnSjju7NkEpVfydhTAZmfIubMHD3Y3H+rRg1XN9CGhUjcmh\nkdz98TaOnEk1ujQhXEqCW1ief53KfPdYd14bEUhkfAoD523gk41x5ObJuW9RMUlwiwrBzU1x9w1N\nWTO+DyHX1WHGsr2M/GAL+05eMLo0IcqcBLeoUBpW9+WTB4J5687rOZacxtB3NjJv7X6yLn3yUoiK\nQIJbVDhKKYZd78eacX0YHNiQeWtjue2dTew6ds7o0oQoExLcosKqXcWbt+7sxCf3B5OSns3I9zfz\n6rJo0rNyi7+zECYmwS0qvH4B9Vk9vg93dmvKxxsPMXDeBrYcPG10WUJcMwluYQvVfDx5bUQg3z3W\nHaXg7o+3MTk0kvMZ2UaXJkSpSXALW+lxXW1WPtuHMX1a8P0fR+k/dz1ro08ZXZYQpSLBLWzH18ud\nKYPbsejJEGpW8uLR/27n6e/COXMx0+jShCgRCW5hWx2b1GDx2F6M79+alVEJ9Ju7np92xcumVcL0\nJLiFrXl5uPHMLa1Y9kxvmtWuzLP/28UjX26X/b6FqUlwCwG0rl+Vhf/oyUtDA9h68AwD3tzAN9uO\nkCcfmxcmVGxwK6WaKKV+UUpFK6X2KKWeLY/ChChv7m6KR3o1Z9VzfejYpDovLIriro9/49Bp2bRK\nmEux27oqpRoCDbXWO5VSVYEdwHCtdbSz+1zLtq5h4fGM+34Xmvw9l58f2Ma2e1CHhcfzytI9JKdm\nU6+qN1MGt7NtL4yiteaH7ceYsWwvWTl5/HNAa+pU9uI/a2I5cS6dRgYeo2Hh8cxZtU/qMEkNZaU0\n27qWej9updRPwLta6zXOblPa4C482Rzyp77YcYCA9MJcTp3P4MWwKNZEn0IpuPLpYsTjYpbjwwx1\nmKGGsuSy4FZK+QMbgA5a6/POblfa4A6ZtY74It4M8qvhy+ZJfUv8cyoC6YX5aK3pPH0NZ9P+/GEd\nL3c3OjapXm617D6WQlbunzfMsmMdzmqw6nOlNMHtUYofWgVYCDxXVGgrpcYAYwCaNm1a0h8LyCTv\nK0kvzEcpxbkiQhsgKzcPT/fye4+/qKCyax3OarDDc6VEwa2U8iQ/tL/RWocWdRut9XxgPuSvuEtT\nRKMavkWuMu042Vx6YU7OHhe/Gr58+1j3cqvjaq/I7FaHsxrc3RThR8/SqWnNcqnDCCW5qkQBnwJ7\ntdZzXVGETDYvIL0wJ7M8LlLH1Wvwcnejsrc7Iz/YwvSl0aRl5ZRbPeWpJCvuEOA+IFIptevS96Zo\nrZeXVRGX30iQq0oKeiFXlZjL5f4bfQWD1FF8Dbe0q8fslTF8uukQq6NPMmtkECEt65RbXeVBpryb\nlEx5F+Kv2RZ3hkmhkRw6ncqdXZsweXA7qvt6Gl2WUzLlXQhheze0qM2KZ3vz+I0t+GH7MfrPXc/q\nPSeNLqtMSHALISosH093Jg9qR9hTIdSq7MWYr3Yw9tudnLb4TpAS3EKICi+ocQ2WPN2Lfw1ozeo9\np+g3dz2Lwo9bdidICW4hhC14ursxtm8rlj/bixZ1KjPu+908/MUflrzuW4JbCGErLetV5ccnejL1\ntgB+i0um/9z1fPWbtXaClOAWQtiOu5vioZDmrB7Xh05Na/JSWBR3zv+NuKSLRpdWIhLcQgjbalKr\nEl890o3XRwcRc/I8g97ayIfrD5Lj5OP0ZiHBLYSwNaUUdwQ3Ye34G7mpTV1mrYhh+PubiT7hdB89\nw0lwCyEEUK+aDx/dF8wH93TmZEomt7+7if+s3kdmTm7xdy5nEtxCCHGFQYENWTu+D8Ou9+OddQcY\n8vYmdhxJNrosBxLcQghRSI1KXvznjo58+XA30rNyGf3hVqYt3kNqpjk2rZLgFkIIJ25sXZdV4/pw\nf/dmfLHlMAPnbWBjbJLRZUlwCyHE1VTx9uDlYR348YkeeHm4cd+nv/P8j7tJcTJcozxIcAshRAl0\n9a/F8md68+RN1xEaHk+/N9ezMsqYTatMs62rTHkvIFPehTC3qPgUJiyIIDrhPIMDG9C9RS0+Wn/o\nL+1N7tIp7yUhU96vnfRCCGvIzs1j/oY45q7eR26hGL2W56zl9uOes2qfQ1ABpGfnMmfVPoMqMo70\nQghr8HR346mbW1K7ivef/p+rn7OmCG6ZbF5AeiGEtSRdKHpvb1c+Z00R3M4mmNtxsrmzv1kp+Hnv\nqXKuRgiS7307AAAIo0lEQVThTGpmDtMW78HZyWZX5pcpgtsME6PNoqheeHu4Ub+qN498uZ1nvgvn\njMWndwhhdRv2JzHgzQ18ufUwvVvVwcfTMUpdnV8lmfLucjLlvYCzydWDAxvywa8HefeXWDbGJjHt\n9vbc3rERSimDKxbCPs6lZTFj2V4W7DhOi7qV+fHxHgT71yIsPL5cJ96b4qqSy2TKe/H2n7rAhAUR\n7Dp2jlva1mPGiA40rG6/U0pClLcVkQm89NMezqZl8cSNLXi6byt8Cr06/issd1WJKLnW9auy8B89\neXFIOzYfPE3/uRv4Zpu1pncIYSWJFzL4x9c7+Mc3O6lfzZvFY0N4fmDbMg3t0jLFqRJROu5uikd7\nt2BAQAMmhUbwwqIoluw+wayRQfjXqWx0eUJUCFprFuw4zoxle0nPzmXCrW14rHcLPN2NX+8aX4G4\nZk1rV+KbR29g1shA9sSfZ+C8DczfYP7pHUKY3bHkNO7/7HeeXxBB6/pVWPFsb568qaUpQhtkxW15\nSinu7NaUm9rU48WwKF5bHsOyiARmjw6ibYNqRpcnhKXk5Wn+u/Uwr6/ahwKmD2vPPTc0w83NXBcB\nmOOfD/GXNajuw8f3d+Hduztx/Gw6Q9/exNw1+005vUMIMzqQeJE7PtrKtCXRdPWvxapxfbivh7/p\nQhtkxV2hKKUYGtSIkOvq8MrSaN7+OZYVkfmr785NaxpdnhCmdHnPkbfWxlLJ2525d3RkRCc/U19q\nKyvuCqhmZS/e/Pv1fP5gVy5m5jDqgy1MXxpNWpY5pncIYRZR8SkMe3czc1bto39AfdaMu5GRnRub\nOrRBVtwV2s1t67F6XB9mr4zh002HWB19klkjgwhpWcfo0oQwVEZ2Lm/9HMv8DXHUquzFh/d24dYO\nDYwuq8RkxV3BVfXxZMbwQL4f0x0PNzfu+WQbkxZGkJJu3PQOIYz0x+FkBr+1kQ9+Pcjozo1ZO+5G\nS4U2yIrbNm5oUZsVz/Zm3tpYPt4Yx7qYRGYM78CA9tY6YIW4Vhczc3h9ZQz/3XqExjV9+fqRG+jV\nypqvPmXFbSM+nu5MGtSWsCdDqF3FmzFf7WDstzs5LZtWiQrul32JDJi7nq9+O8LDIc1ZPa6PZUMb\nZMVtS4GNq7N4bAgfrT/I2z8fYNOB00y9LYDh15v7nXQhSutsahbTl0YTGh5Py3pVWPBET7o0s/4V\nVhLcNuXp7sbYvq24tUMDJiyIYNz3u/lp1wleHRGInw33QRcVi9aa5ZEnmbo4inNp2TzTtyVP9W2J\nt4dx+4uUpRKdKlFK3aqU2qeUOqCUmuTqokT5aVmvKj8+0ZOptwWwLS75/19OyqZVwqoSz2fw+Fc7\neOrbnTSs7svisb0YP6BNhQltKMG2rkopd2A/0B84DvwB3KW1jnZ2H5nybk3HktOYsiiSjbGn6eZf\ni34B9fhyy5Fy22PYmfLe61jqsE4djjX40LtVXZZFJpCVk8f4/q15pFdzPEyyv0hxynTKu1KqBzBN\naz3w0teTAbTWM53dR6a8W9flHdFeCoskI8fx2DDiMTHLsSF1mK+OomoAaFGnMp8+2JXmFtsps6yD\nezRwq9b60Utf3wfcoLUe6+w+pQ3ukFnriC9isKZfDV82T+pb4p8jyk73137m5PmMP33fw02V6xPi\n0OlUcoo4bSN1SB3OamhUw4ctk24plxrKUmmCu8zenFRKjQHGADRt2rRU95XJ5uZzqojQBsjJ07Sq\nX6Xc6ohNvCh1SB2lqiHhXNHHbkVSkuCOB5pc8XXjS99zoLWeD8yH/BV3aYpoVMO3yBW3Hae8m4Wz\nx8Svhi/v39Ol3Oq42qsxqcPedTirwQ65UZKz9n8ArZRSzZVSXsCdwOKyLEKmvJuPWR4TqUPqMHMN\nRil2xa21zlFKjQVWAe7AZ1rrPWVZhLPJ5vLGpHHM8phIHVKHmWswiqmmvAshhF3JlHchhKjAJLiF\nEMJiJLiFEMJiJLiFEMJiJLiFEMJiXHJViVIqCThyjXevA5wuw3KsTHrhSPrhSPpRoCL0opnWum5J\nbuiS4P4rlFLbS3pJTEUnvXAk/XAk/Shgt17IqRIhhLAYCW4hhLAYMwb3fKMLMBHphSPphyPpRwFb\n9cJ057iFEEJcnRlX3EIIIa7CNMEtA4kLKKWaKKV+UUpFK6X2KKWeNbomoyml3JVS4UqppUbXYjSl\nVA2l1AKlVIxSau+l8YK2pZQad+l5EqWU+k4p5WN0Ta5miuC+NJD4PWAQEADcpZQKMLYqQ+UA/9Ra\nBwDdgads3g+AZ4G9RhdhEm8BK7XWbYGO2LgvSik/4BkgWGvdgfytp+80tirXM0VwA92AA1rrOK11\nFvA/YJjBNRlGa52gtd556b8vkP/ErPibDDuhlGoMDAE+MboWoymlqgN9gE8BtNZZWutzxlZlOA/A\nVynlAVQCThhcj8uZJbj9gGNXfH0cGwfVlZRS/kAnYJuxlRhqHjAByDO6EBNoDiQBn186dfSJUspa\n48zLkNY6HngDOAokACla69XGVuV6ZgluUQSlVBVgIfCc1vq80fUYQSk1FEjUWu8wuhaT8AA6Ax9o\nrTsBqYBt3xNSStUk/9V5c6ARUFkpda+xVbmeWYK7RAOJ7UQp5Ul+aH+jtQ41uh4DhQC3K6UOk38K\nra9S6mtjSzLUceC41vryK7AF5Ae5XfUDDmmtk7TW2UAo0NPgmlzOLMHt8oHEVqKUUuSfw9yrtZ5r\ndD1G0lpP1lo31lr7k39crNNaV/gVlTNa65PAMaXU5Ym4twDRBpZktKNAd6VUpUvPm1uwwZu1xQ4L\nLg/lMZDYYkKA+4BIpdSuS9+borVebmBNwjyeBr65tMiJAx4yuB7DaK23KaUWADvJvxorHBt8ilI+\nOSmEEBZjllMlQgghSkiCWwghLEaCWwghLEaCWwghLEaCWwghLEaCWwghLEaCWwghLEaCWwghLOb/\nAIZeRHq4D2a1AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10da0eda0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "rows = [location[0] for location in path]\n",
    "cols = [location[1] for location in path]\n",
    "plt.plot(rows,cols,'o-');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 0),\n",
       " (1, 1),\n",
       " (2, 2),\n",
       " (3, 3),\n",
       " (4, 4),\n",
       " (5, 5),\n",
       " (6, 6),\n",
       " (7, 7),\n",
       " (8, 8),\n",
       " (9, 9)]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path = breadthFirstSearch((0, 0), (9, 9), gridSuccessors)\n",
    "path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHVtJREFUeJzt3Xd8lfXd//HXl5ANCSNhBxI2gYBgWOIeBcWB0FatVau3\n1bt3bfVuf0xHsS4ctdpWbcW6bm2tJSBDEEtRSx1oQEhCElZYIQkJI4MkJ+t8f3+AFpCYA5yT64z3\n8y/IOSRvj8n7ceU61/X5GGstIiISONo4HUBERE6NiltEJMCouEVEAoyKW0QkwKi4RUQCjIpbRCTA\nqLhFRAKMiltEJMCouEVEAkxbX3zShIQEm5yc7ItPLSISlNatW7ffWpvoyXN9UtzJyclkZmb64lOL\niAQlY8wuT5+rUyUiIgFGxS0iEmBU3CIiAUbFLSISYFTcIiIBxidXlYiIhJJ3vtzLkys3U1ReS48O\n0UyfOIgpI3v67OupuEVEzsA7X+5l9sJsahuaANhbXsvshdkAPitvnSoRETkDT67c/HVpf6W2oYkn\nV2722ddUcYuInIGi8tpT+rg3qLhFRE7Th5tLaWPMSR/r0SHaZ19X57hFRE7Roep6Hno3l4Xr99Kl\nfSQVtQ3UNbq/fjw6PIzpEwf57OuruEVEPGStZUVOCQ8szqG8poGfXdyfuy7uz4rsEl1VIiLib0or\nXdy/OIeVm/aR1jOe128bS2qPOODI1SO+LOoTqbhFRL6FtZa/ryvk4WW51DW6mX35YP7r3BTahjn3\nFqGKW0SkGXsO1jB7YTb/3rafMSmdmDc1jb6J7ZyOpeIWETlRk9vy2ic7eXLlZsLaGB6eMowfjOlN\nmzYnv4Kktam4RUSOsXVfFTMzsli/u5wLByXy6LVpPr2073SouEVEgIYmN3/8cDu/X72N2Mgwnrnu\nLK45qwemmeu0naTiFpGQl11YwfQFG8kvqeKqET341VWpJLSLdDpWs1TcIhKyXA1N/HbVFub/q4DE\n9pHMvzmdy1K7Oh2rRSpuEQlJnxUcYFZGFjsP1HDDmCRmXT6E+Ohwp2N5RMUtIiGlytXAvBX5vLl2\nN707xfCX28dyTv8Ep2OdEhW3iISMD/JLmbMom32VLm4/N4VffGcgMRGBV4OBl1hE5BQdrK7n10s3\n8c6GIgZ2bcfzN57DyN4dnY512lTcIhK0rLUszSpm7pJNVLkauPuSAfz0ov5EtA3sidYqbhEJSiUV\nLu57J4dVefsY0Suex787lsHd4pyO5RUqbhEJKtZa3vpiD4++m0eD2829VwzhtnNTCPOT29W9waPi\nNsb8L3A7YIFs4FZrrcuXwUREWnLidvVbJyTzz7xSPi04wLi+nZg3dTjJCbFOx/S6FovbGNMT+DmQ\naq2tNca8DVwPvOrjbCIizTrZdvWH380jMszw2NQ0rh+d5Je3q3uDp6dK2gLRxpgGIAYo8l0kEZGW\nnWy7OkDH2EhuGNPbgUStp8W3Vq21e4GngN1AMVBhrX3/xOcZY+4wxmQaYzLLysq8n1RE5BjNbVHf\nVxn8Z3FbLG5jTEfgGiAF6AHEGmN+eOLzrLUvWmvTrbXpiYmJ3k8qInLUhj3lzb7Z6G8jWH3Bk4sZ\nLwV2WGvLrLUNwELgHN/GEhH5ptr6Jh55N5epz39MTEQYESesD/P1dnV/4ck57t3AOGNMDFALXAJk\n+jSViMgJPtm+n1kZ2ew+WMONY3sz8/LBrM4rbdXt6v6ixeK21q41xiwA1gONwJfAi74OJiICUOlq\n4LHl+fz1890kd47hrTvGMa5vZ6D1t6v7C4+uKrHW/gr4lY+ziIgcZ1XuPu59J5uyqjruPL8v91w6\nkOiIMKdjOU53ToqI3zlwuI65S3NZurGIwd3aM//mdIb36uB0LL+h4hYRv2GtZcnGIuYu2cThukZ+\ncdlA/vuCfgE/FMrbVNwi4heKymu5750cVueXclZSB5747nAGdm3vdCy/pOIWEUe53Za/frGbx5bn\n0+S23H9lKj86JzmohkJ5m4pbRByzY381szKyWLvjIBP6d+axa4fTu3OM07H8nopbRFpdY5Oblz/e\nwW/e30JE2zY8Pi2N76cH71Aob1Nxi0iryiuuZGZGFlmFFVyW2pWHpwyja1yU07ECiopbRFpFXWMT\nz63exvMfbqdDTDjP/WAUV6R101H2aVBxi4jPrd99iJkLsthaepipI3ty/5WpdIyNcDpWwFJxi4jP\n1NQ38tTKLbzyyQ66x0Xxyq2juWhQF6djBTwVt4j4xMfb9jNrYRZ7DtZy07g+zJg0iPZR4U7HCgoq\nbhHxqoraBh59N4+/Ze4hJSGWv90xjrFHh0KJd6i4RcRr3t9Uwn3v5HCgup7/vqAf91w6gKhwDYXy\nNhW3iJyWYzesd42Lolt8JBv2VDCkexx/vmU0ab3inY4YtFTcInLKTtywXlLpoqTSxeS0bjxz/UjC\nwzQUypf06orIKWtuw/qGPRUq7VagV1hETonbbdnbzIb15javi3epuEXEYwVlh7n+xc+afTwUNqz7\nAxW3iLSoscnNCx9uZ9Kza8gvqeSGMUlEh4fmhnV/oDcnReRbbSqqYGZGFjl7K5k0tBu/njKULu2j\nGJvSOSQ3rPsDFbeInJSroYnfr97KHz8qoGNMBC/cOIrL07p//Xioblj3BypuEfmGdbsOMmNBFtvL\nqpk2qhf3XzmEDjEaCuUvVNwi8rXqukaeXLmZ1z7dSY/4aF67bQwXDEx0OpacQMUtIgD8a0sZsxdm\nU1RRyy3jk5k+cRCxkaoIf6T/KyIhrrymnoffzWPBukL6Jsby9zvHk57cyelY8i1U3CIhbEV2Mfcv\n3sShmnp+elE/fnaxhkIFAhW3SAgqrXLxq8WbWJFTwtAecbx222iG9tBQqECh4hYJIdZaFqwr5OF3\n86htaGLmpMHcfl6K5osEGBW3SIjYc7CGOYuyWbN1P6OTOzJv2nD6JbZzOpacBhW3SJBzuy2vf7qT\nJ1ZuxgAPXTOUG8f2oU0bbVcPVCpukSC2rbSKmRnZrNt1iAsGJvLItcPo1THG6VhyhlTcIkGoocnN\ni/8q4NlVW4mJDOPp74/g2pE9MUZH2cFAxS0SZHL2VjB9QRZ5xZVMHt6duVcNJbF9pNOxxItU3CJB\nwtXQxDOrtjJ/TQGdYiP4001nM3FoN6djiQ94VNzGmA7AS8AwwAK3WWs/9WUwEfHc5zsOMisji4L9\n1VyXnsScK4YQHxPudCzxEU+PuJ8F3rPWftcYEwHo3Q0Rhxy7Xb1bfBR9E2L5ePsBkjpF88Z/jeXc\nAQlORxQfa7G4jTHxwPnAjwCstfVAvW9jicjJnLhdvbjCRXGFiwsGJPDCTWcTE6Gzn6HAk9ulUoAy\n4BVjzJfGmJeMMbE+ziUiJ9HcdvVtZdUq7RDiSXG3BUYBL1hrRwLVwKwTn2SMucMYk2mMySwrK/Ny\nTBGxVtvV5QhPirsQKLTWrj369wUcKfLjWGtftNamW2vTExM1eF3Em/ZVurjz/9Y1+7i2q4eWFovb\nWlsC7DHGfLW++RIg16epRAQ4cpT9ty92c+nTH/HRljKuHtGdKG1XD3menhT7GfDm0StKCoBbfRdJ\nRAB2H6hh9qIsPt52gLEpnXh82nCSE2KPu6pE29VDk7HWev2Tpqen28zMTK9/XpFQ0OS2vPrJTp5a\nuZmwNobZVwzmhtG9NRQqyBlj1llr0z15rt6GFvEjW/ZVMWNBFhv2lHPx4C48cu0wusfr/LUcT8Ut\n4gfqG9388aPt/H71VtpFtuXZ68/i6hE9NBRKTkrFLeKwjXvKmZmRRX5JFVeN6MHcq1Lp3E5DoaR5\nKm4Rh9TWN/HMqi3MX1NAYvtI5t+czmWpXZ2OJQFAxS3igM8KDjArI4udB2q4YUxvZl8xmLgoDYUS\nz6i4RVpRlauBeSvyeXPtbvp0juEvPx7LOf00FEpOjYpbpJWszt/HvYty2Ffp4sfnpfCLywYRHRHm\ndCwJQCpuER87cLiOXy/LZfGGIgZ1bc8LPzybs5I6OB1LApiKW8RHrLUszSpm7pJNVLkauOfSAfzP\nhf2JaOvJiCCR5qm4RXygpMLFfe9ksyqvlBFJHXhi2nAGdWvvdCwJEipuES+y1vLWF3t49N08Gtxu\n7ps8hFsnpBCm29XFi1TcIl6y60A1szKy+bTgAOP7dmbetDT6dNbOEfE+FbfIGWpyW175eAdPvb+Z\n8DZteGxqGtePTtLt6uIzKm6RM7C5pIoZGVls3FPOpUO68PCUNLrFRzkdS4KcilvEQ8fOwe4eH0Va\nz3hWby4lLiqc398wkiuHd9dRtrQKFbeIB07crl5U4aKowsXZvTsw/5bRdIqNcDihhBJdUCrigea2\nq5dU1qm0pdWpuEU8oO3q4k90qkTkW1S6GnhseV6zj2u7ujhBxS3SjFW5+7j3nWzKquq4eFAinxQc\nwNXg/vpxbVcXp6i4RU6w/3AdDy7NZenGIgZ3a8/8m9MZ3quDtquL31BxixxlrWXxhiIeXLqJ6rom\nfnnZQO68oN/XQ6GmjOypoha/oOIW4cibjPe9k8Pq/FJG9j4yFGpAVw2FEv+k4paQ5nZb/vL5buat\nyKfJbXngylRuOSdZQ6HEr6m4JWTt2F/NrIws1u44yLn9E3hsahpJnWKcjiXSIhW3hJzGJjd//vcO\nnv7HFiLatuGJacP5Xnov3a4uAUPFLSElr7iSmRlZZBVW8J3Urjw0ZRhd4zQUSgKLiltCQl1jE39Y\nvY0XPtxOh5hwnvvBKK5I66ajbAlIKm4Jeut2HWJmRhbbSg8zdVRP7p+cSkfNF5EApuKWoFVT38iT\nKzfz6ic76R4XxSu3juaiQV2cjiVyxlTcEpT+vXU/sxZmUXiolpvH92HGpMG0i9S3uwQHfSdLUKmo\naeCR5bm8nVlI34RY3r5zPGNSOjkdS8SrVNwSNN7LKeH+xTkcrK7nJxf24+5LBhAVHuZ0LBGvU3FL\nwCurqmPukk28m11Mavc4XvnRaIb1jHc6lojPqLglYFlrWbh+L79elkttfRPTJw7ijvP7Eh6m/SAS\n3DwubmNMGJAJ7LXWXum7SCIt21tey5yF2Xy0pYyz+3Tk8WnD6d+lndOxRFrFqRxx3w3kAXE+yiJy\nUsdtV+8Qxfi+nXkvpwQLPHj1UG4a14c2GgolIcSj4jbG9AImA48Av/BpIpFjfGO7ermLjPV7GdS1\nHS/dMlpDoSQkeXoy8BlgBuBu6Yki3tTcdvXDdY0qbQlZLRa3MeZKoNRau66F591hjMk0xmSWlZV5\nLaCEtua2qBeVu1o5iYj/8OSIewJwtTFmJ/AWcLEx5o0Tn2StfdFam26tTU9MTPRyTAk1roYmnlyZ\nj23mcW1Xl1DWYnFba2dba3tZa5OB64HV1tof+jyZhKzMnQe54ndreO6D7YxJ7khU+PHfptquLqFO\n13GL3zhc18iT7+Xz+me76BEfzeu3jeH8gYnari5yAmNtc7+Mnr709HSbmZnp9c8rweujLWXMWZhN\nUUUtt4xPZvrEQcRqKJSEEGPMOmttuifP1U+GOKq8pp6HluWRsb6Qfomx/P3O8aQnayiUyLdRcYtj\nVmQXc//iTRyqqeeui/pz18X9NRRKxAMqbml1pZUuHli8ifc2lTC0Rxyv3TaaoT00FErEUypuaTXW\nWv6+rpCHl+XianQzc9JgfnxeCm01FErklKi4pVXsOVjDnEXZrNm6nzHJnZg3LY2+iRoKJXI6VNzi\nU01uy+uf7uTJlZsxwEPXDOXGsRoKJXImVNziM9tKq5iZkc26XYe4YGAij05No6fueBQ5Yypu8bqG\nJjd/+mg7v/vnNmIiw3j6+yO4dmRPjNFRtog3qLjFq7ILK5i+YCP5JVVMHt6duVcNJbF9pNOxRIKK\nilu8wtXQxDOrtjJ/TQGdYyP4001nM3FoN6djiQQlFbecsbUFB5i1MJsd+6u5Lj2JOZOHEB8d7nQs\nkaCl4pbTVuVq4In3NvN/n+0iqVM0b94+lgn9E5yOJRL0VNxyWj7YXMq9C7MprnRx24QU/t/EgcRE\n6NtJpDXoJ01OycHqeh5alsuiL/cyoEs7Mn5yDqN6d3Q6lkhIUXFLs46fgx3FpUO6siyrmIraBn5+\nyQB+elE/IttqKJRIa1Nxy0mduF19b7mL1z7dRVLHaN64fSxDusc5nFAkdGm6j5xUc9vVm6xVaYs4\nTMUtJ9XcdvVibVcXcZxOlchxmtyWVz/Z2ezj2q4u4jwVt3xty74qZizIYsOecoZ0a0/B/mrqGt1f\nP67t6iL+QcUt1De6eeHD7fzhg620i2zLs9efxdUjerB4Q5G2q4v4IRV3iNu4p5yZGVnkl1Rx1Yge\nzL0qlc7tjgyFmjKyp4paxA+puENUbX0Tv121hZfWFJDYPpL5N6dzWWpXp2OJiAdU3CHo0+0HmL0w\ni50HarhhTBKzrxhCXJSGQokEChV3CKl0NTBvRT5/Wbub3p1i+MvtYzlHQ6FEAo6KO0T8M28f9y7K\nobTKxY/PS+EXlw0iOkK3q4sEIhV3kDtwuI4Hl+ayZGMRg7q25483nc1ZSR2cjiUiZ0DFHaSstSzZ\nWMSDS3OpcjVwz6UD+J8L+xPRVjfLigQ6FXcQKq6o5b5FOfwzv5QRSR14YtpwBnVr73QsEfESFXcQ\ncbstb32xh8eW59HgdnPf5CHcOiGFsDbari4STFTcQWLn/mpmLczis4KDjO/bmXnT0ujTOdbpWCLi\nAyruANfY5Oblj3fwm/e3EBHWhnlT07hudBLG6ChbJFipuANYfkklMxdksbGwgkuHdOHhKWl0i49y\nOpaI+JiKOwDVNTbx3Afbef6DbcRHh/P7G0Zy5fDuOsoWCREq7gDz5e5DzMzIYsu+w0w5qwcPXDWU\nTrERTscSkVbUYnEbY5KA14GugAVetNY+6+tgcrya+kZ+8/4WXv54B93ionj5R+lcPFhDoURCkSdH\n3I3AL621640x7YF1xph/WGtzfZwtZB2/XT2aa87qwbKsYnYfrOGH43ozc9Jg2msolEjIarG4rbXF\nQPHRP1cZY/KAnoCK2we+uV29luc/3E5CbDhv3TGOcX07O5xQRJx2Svc/G2OSgZHAWl+Ekea3q0e0\nDVNpiwhwCsVtjGkHZAD3WGsrT/L4HcaYTGNMZllZmTczhpRmt6tXaLu6iBzhUXEbY8I5UtpvWmsX\nnuw51toXrbXp1tr0xMREb2YMCdZaFn1ZCM1c0aft6iLyFU+uKjHAn4E8a+3Tvo8UeorKa7l3UTYf\nbC6jT6doSirrtF1dRJrlyVUlE4CbgGxjzIajH5tjrV3uu1ihwe22vPn5bh5fkU+T2/LAlancck4y\nSzdqu7qINM+Tq0r+TbO/wMvpKig7zKyMbD7feZBz+yfw2NQ0kjrFANquLiLfTndOtrLGJjcv/XsH\nv/3HFiLatuGJacP5Xnov3a4uIh5Tcbei3KJKZmRsJGdvJd9J7cpDU4bRNU5DoUTk1Ki4W0FdYxN/\nWL2NFz7cToeYcJ6/cRSXD+umo2wROS0qbh9bt+vIUKhtpYeZOqon909OpaOGQonIGVBx+0h1XSNP\nvb+ZVz/ZSY/4aF69dTQXDuridCwRCQIqbh9Ys7WM2QuzKTxUy83j+zBj0mDaReqlFhHvUJt4UUVN\nA48sz+XtzEL6JsTy9p3jGZPSyelYIhJkVNxe8l5OCfcvzuFgdT0/ubAfd18ygKjwMKdjiUgQUnGf\nodIqF3OXbGJ5dgmp3eN45UejGdYz3ulYIhLEVNynyVrLwvV7+fWyXGobmpg+cRB3nN+X8LBTmpQr\nInLKVNynofBQDXMW5fCvLWWc3acjj08bTv8u7ZyOJSIhQsV9Ctxuyxtrd/H4inws8ODVQ7lpXB/a\ntNGNNCLSelTcHtpedphZGVl8sfMQ5w1I4NFr/zMUSkSkNam4W9DQ5Gb+mgKeWbWV6PAwnvreCKaN\n6qnb1UXEMSruExy7YT2hfSQRYYa95S6uSOvG3KuH0qW9hkKJiLNU3Mc4ccN6WVUdALdO6MOvrhrm\nZDQRka/p2rVjNLdh/f1NpQ6kERE5ORX3UYfrGtnbzIb15javi4g4QcUNfLSljIm//Vezj2vDuoj4\nk5Au7vKaen759kZueflzosLbcPcl/Yk+Yb6INqyLiL8J2Tcnl2cX88DiHMprGrjrov7cdXF/osLD\nSElopw3rIuLXQq64SytdPLB4E+9tKmFYzzheu20MQ3v8ZyiUNqyLiL8LmeK21vL3dYU8vCwXV6Ob\nmZMG8+PzUmiroVAiEmBCorj3HKxhzqJs1mzdz5jkTsyblkbfRA2FEpHAFNTF3eS2vP7pTp5cuRkD\nPHTNUG4cq6FQIhLYgra4t5VWMWNBFut3l3PhoEQeuTaNnrqsT0SCQNAVd0OTmz99tJ3f/XMbMZFh\n/Pa6EUw5S0OhRCR4BFVxZxdWMH3BRvJLqpg8vDsPXj2UhHaRTscSEfGqoChuV0MTz6zayvw1BXSO\njeBPN53NxKHdnI4lIuITAV/cawsOMGthNjv2V3NdehJzJg8hPjrc6VgiIj4TsMVd5Wrg8ffyeeOz\n3SR1iubN28cyoX+C07FERHwuIIv7g/xS7l2UTXGli/86N4VffmcgMREB+Z8iInLKAqrtDlbX89Cy\nXBZ9uZcBXdqR8ZNzGNW7o9OxRERaVUAUt7WWZVnFzF2yiYraBn5+yQB+elE/ItuGtfyPRUSCjN8X\n975KF/cuymFV3j6G94rnjdvHMqR7nNOxREQc41FxG2MmAc8CYcBL1tp5Pk3FkaPsv32xh0eW51Hf\n6GbOFYO5bYKGQomItFjcxpgw4DngMqAQ+MIYs8Ram+vNIMduV+8SF0lcVFu2llYzNqUTj08bTnJC\nrDe/nIhIwPLkiHsMsM1aWwBgjHkLuAbwWnGfuF19X2Ud+yrr+F56Lx6fOlxDoUREjuHJeYeewJ5j\n/l549GNe09x29U+2HVBpi4icwGsnjI0xdxhjMo0xmWVlZaf0b5vboq7t6iIi3+RJce8Fko75e6+j\nHzuOtfZFa226tTY9MTHxlEI0t0Vd29VFRL7Jk+L+AhhgjEkxxkQA1wNLvBli+sRB2q4uIuKhFt+c\ntNY2GmPuAlZy5HLAl621m7wZ4qvlvNquLiLSMmOt9fonTU9Pt5mZmV7/vCIiwcoYs85am+7Jc3U3\ni4hIgFFxi4gEGBW3iEiAUXGLiAQYFbeISIDxyVUlxpgyYNdp/vMEYL8X4wQyvRbH0+txPL0e/xEM\nr0Ufa61Hdy/6pLjPhDEm09NLYoKdXovj6fU4nl6P/wi110KnSkREAoyKW0QkwPhjcb/odAA/otfi\neHo9jqfX4z9C6rXwu3PcIiLy7fzxiFtERL6F3xS3MWaSMWazMWabMWaW03mcZIxJMsZ8YIzJNcZs\nMsbc7XQmpxljwowxXxpjljmdxWnGmA7GmAXGmHxjTJ4xZrzTmZxkjPnfoz8nOcaYvxpjopzO5Gt+\nUdzHLCS+HEgFbjDGpDqbylGNwC+ttanAOOCnIf56ANwN5Dkdwk88C7xnrR0MjCCEXxdjTE/g50C6\ntXYYR0ZPX+9sKt/zi+LmmIXE1tp64KuFxCHJWltsrV1/9M9VHPnBDNnh5MaYXsBk4CWnszjNGBMP\nnA/8GcBaW2+tLXc2lePaAtHGmLZADFDkcB6f85fi9vlC4kBljEkGRgJrnU3iqGeAGYDb6SB+IAUo\nA145euroJWNMrNOhnGKt3Qs8BewGioEKa+37zqbyPX8pbjkJY0w7IAO4x1pb6XQeJxhjrgRKrbXr\nnM7iJ9oCo4AXrLUjgWogZN8TMsZ05Mhv5ylADyDWGPNDZ1P5nr8Ut0cLiUOJMSacI6X9prV2odN5\nHDQBuNoYs5Mjp9AuNsa84WwkRxUChdbar34DW8CRIg9VlwI7rLVl1toGYCFwjsOZfM5fitvnC4kD\niTHGcOQcZp619mmn8zjJWjvbWtvLWpvMke+L1dbaoD+iao61tgTYY4z5apP2JUCug5GcthsYZ4yJ\nOfpzcwkh8GZti8uCW0NrLCQOMBOAm4BsY8yGox+bY61d7mAm8R8/A948epBTANzqcB7HWGvXGmMW\nAOs5cjXWl4TAXZS6c1JEJMD4y6kSERHxkIpbRCTAqLhFRAKMiltEJMCouEVEAoyKW0QkwKi4RUQC\njIpbRCTA/H+15xU4ZYbDfgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10ddf85f8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "rows = [location[0] for location in path]\n",
    "cols = [location[1] for location in path]\n",
    "plt.plot(rows,cols,'o-');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "depthFirstSearch((0, 0), (9, 20), gridSuccessors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Extra Credit\n",
    "\n",
    "For extra credit, use your functions to solve the Camels Puzzle, described at [Logic Puzzles](http://www.folj.com/puzzles/).\n",
    "The following code illustrates one possible state representation and shows results of a breadth-first and a dept-first search.  You must define a new successors function, called `camelSuccessorsf`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('R', 'R', 'R', 'R', ' ', 'L', 'L', 'L', 'L')"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "camelStartState"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('L', 'L', 'L', 'L', ' ', 'R', 'R', 'R', 'R')"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "camelGoalState"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('R', 'R', 'R', ' ', 'R', 'L', 'L', 'L', 'L'),\n",
       " ('R', 'R', 'R', 'R', 'L', ' ', 'L', 'L', 'L')]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "camelSuccessorsf(camelStartState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('R', 'R', 'R', ' ', 'R', 'L', 'L', 'L', 'L')\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[('R', 'R', ' ', 'R', 'R', 'L', 'L', 'L', 'L'),\n",
       " ('R', 'R', 'R', 'L', 'R', ' ', 'L', 'L', 'L')]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "children = camelSuccessorsf(camelStartState)\n",
    "print(children[0])\n",
    "camelSuccessorsf(children[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Breadth-first solution: ( 25 steps)\n",
      "('R', 'R', 'R', 'R', ' ', 'L', 'L', 'L', 'L')\n",
      "('R', 'R', 'R', ' ', 'R', 'L', 'L', 'L', 'L')\n",
      "('R', 'R', 'R', 'L', 'R', ' ', 'L', 'L', 'L')\n",
      "('R', 'R', 'R', 'L', 'R', 'L', ' ', 'L', 'L')\n",
      "('R', 'R', 'R', 'L', ' ', 'L', 'R', 'L', 'L')\n",
      "('R', 'R', ' ', 'L', 'R', 'L', 'R', 'L', 'L')\n",
      "('R', ' ', 'R', 'L', 'R', 'L', 'R', 'L', 'L')\n",
      "('R', 'L', 'R', ' ', 'R', 'L', 'R', 'L', 'L')\n",
      "('R', 'L', 'R', 'L', 'R', ' ', 'R', 'L', 'L')\n",
      "('R', 'L', 'R', 'L', 'R', 'L', 'R', ' ', 'L')\n",
      "('R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', ' ')\n",
      "('R', 'L', 'R', 'L', 'R', 'L', ' ', 'L', 'R')\n",
      "('R', 'L', 'R', 'L', ' ', 'L', 'R', 'L', 'R')\n",
      "('R', 'L', ' ', 'L', 'R', 'L', 'R', 'L', 'R')\n",
      "(' ', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R')\n",
      "('L', ' ', 'R', 'L', 'R', 'L', 'R', 'L', 'R')\n",
      "('L', 'L', 'R', ' ', 'R', 'L', 'R', 'L', 'R')\n",
      "('L', 'L', 'R', 'L', 'R', ' ', 'R', 'L', 'R')\n",
      "('L', 'L', 'R', 'L', 'R', 'L', 'R', ' ', 'R')\n",
      "('L', 'L', 'R', 'L', 'R', 'L', ' ', 'R', 'R')\n",
      "('L', 'L', 'R', 'L', ' ', 'L', 'R', 'R', 'R')\n",
      "('L', 'L', ' ', 'L', 'R', 'L', 'R', 'R', 'R')\n",
      "('L', 'L', 'L', ' ', 'R', 'L', 'R', 'R', 'R')\n",
      "('L', 'L', 'L', 'L', 'R', ' ', 'R', 'R', 'R')\n",
      "('L', 'L', 'L', 'L', ' ', 'R', 'R', 'R', 'R')\n",
      "Depth-first solution: ( 25 steps)\n",
      "('R', 'R', 'R', 'R', ' ', 'L', 'L', 'L', 'L')\n",
      "('R', 'R', 'R', ' ', 'R', 'L', 'L', 'L', 'L')\n",
      "('R', 'R', 'R', 'L', 'R', ' ', 'L', 'L', 'L')\n",
      "('R', 'R', 'R', 'L', 'R', 'L', ' ', 'L', 'L')\n",
      "('R', 'R', 'R', 'L', ' ', 'L', 'R', 'L', 'L')\n",
      "('R', 'R', ' ', 'L', 'R', 'L', 'R', 'L', 'L')\n",
      "('R', ' ', 'R', 'L', 'R', 'L', 'R', 'L', 'L')\n",
      "('R', 'L', 'R', ' ', 'R', 'L', 'R', 'L', 'L')\n",
      "('R', 'L', 'R', 'L', 'R', ' ', 'R', 'L', 'L')\n",
      "('R', 'L', 'R', 'L', 'R', 'L', 'R', ' ', 'L')\n",
      "('R', 'L', 'R', 'L', 'R', 'L', 'R', 'L', ' ')\n",
      "('R', 'L', 'R', 'L', 'R', 'L', ' ', 'L', 'R')\n",
      "('R', 'L', 'R', 'L', ' ', 'L', 'R', 'L', 'R')\n",
      "('R', 'L', ' ', 'L', 'R', 'L', 'R', 'L', 'R')\n",
      "(' ', 'L', 'R', 'L', 'R', 'L', 'R', 'L', 'R')\n",
      "('L', ' ', 'R', 'L', 'R', 'L', 'R', 'L', 'R')\n",
      "('L', 'L', 'R', ' ', 'R', 'L', 'R', 'L', 'R')\n",
      "('L', 'L', 'R', 'L', 'R', ' ', 'R', 'L', 'R')\n",
      "('L', 'L', 'R', 'L', 'R', 'L', 'R', ' ', 'R')\n",
      "('L', 'L', 'R', 'L', 'R', 'L', ' ', 'R', 'R')\n",
      "('L', 'L', 'R', 'L', ' ', 'L', 'R', 'R', 'R')\n",
      "('L', 'L', ' ', 'L', 'R', 'L', 'R', 'R', 'R')\n",
      "('L', 'L', 'L', ' ', 'R', 'L', 'R', 'R', 'R')\n",
      "('L', 'L', 'L', 'L', 'R', ' ', 'R', 'R', 'R')\n",
      "('L', 'L', 'L', 'L', ' ', 'R', 'R', 'R', 'R')\n"
     ]
    }
   ],
   "source": [
    "bfs = breadthFirstSearch(camelStartState, camelGoalState, camelSuccessorsf)\n",
    "print('Breadth-first solution: (', len(bfs), 'steps)')\n",
    "for s in bfs:\n",
    "    print(s)\n",
    "\n",
    "dfs = depthFirstSearch(camelStartState, camelGoalState, camelSuccessorsf)\n",
    "print('Depth-first solution: (', len(dfs), 'steps)')\n",
    "for s in dfs:\n",
    "    print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grading\n",
    "\n",
    "Your notebook will be run and graded automatically. Download [A1grader.tar](http://www.cs.colostate.edu/~anderson/cs440/notebooks/A1grader.tar)  and extract A1grader.py from it. Run the code in the following cell to demonstrate an example grading session. You should see a perfect score of 80/100 if your functions are defined correctly. \n",
    "\n",
    "The remaining 20% will be based on your writing.  In markdown cells, explain what your functions are doing and summarize the algorithms.\n",
    "\n",
    "Add at least one markdown cell that describes problems you encountered in trying to solve this assignment."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Check-in"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do not include this section in your notebook.\n",
    "\n",
    "Name your notebook ```Lastname-A1.ipynb```.  So, for me it would be ```Anderson-A1.ipynb```.  Submit the file using the ```Assignment 1``` link on [Canvas](https://colostate.instructure.com/courses/55296).\n",
    "\n",
    "Grading will be based on \n",
    "\n",
    "  * correct behavior of the required functions, and\n",
    "  * readability of the notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Searching this graph:\n",
      " {'c': ['e'], 'a': ['b'], 'e': ['g', 'h', 'i'], 'd': ['f', 'i'], 'b': ['c', 'd']}\n",
      "Looking for path from a to b.\n",
      "20/20 points. Your breadthFirstSearch found correct solution path of ['a', 'b']\n",
      "20/20 points. Your depthFirstSearch found correct solution path of ['a', 'b']\n",
      "Looking for path from a to i.\n",
      "20/20 points. Your breadthFirstSearch found correct solution path of ['a', 'b', 'd', 'i']\n",
      "20/20 points. Your depthFirstSearch found correct solution path of ['a', 'b', 'c', 'e', 'i']\n",
      "\n",
      "assign1 Grade is 80/100\n",
      "Up to 20 more points will be given based on the qualty of your descriptions of the method and the results.\n"
     ]
    }
   ],
   "source": [
    "%run -i A1grader.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}