{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment 2:  solving puzzles with search\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Type your name here*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this assignment we will solve a sliding block puzzle not unlike the Eight Puzzle that we have seen in class.  The puzzle is called \"Making two L's meet\".  It's played on a 5 x 5 grid with nine pieces that are placed as follows:![](https://www.cs.colostate.edu/~cs440/fall19/assignments/images/initial.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The pieces are numbered from 1 to 9, and the two L-shaped pieces are numbered 2 and 7.  The un-numbered regions are empty.  A piece can be moved into an adjacent empty space that can accommodate it.  For example, piece number 9 can be moved left or right, and piece number 7 can be moved down.  Note that pieces 1,2,7,8 take up three squares, 3,4,5,6 take up two squares, and 9 takes up a single square.  The following is an example of a valid solution to the puzzle:\n",
    "![](https://www.cs.colostate.edu/~cs440/fall19/assignments/images/goal.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To write a program that solves the puzzle we need to define the possible actions at a given state.  Whereas for the Eight Puzzle, an action could be specified by the direction in which the empty square is moved, this is no longer possible in this puzzle.  Here an action is a tuple `(piece, direction)` where `piece` is the piece that needs to be moved, numbered between 1 and 9, and `direction` is one of `'UP', 'DOWN', 'LEFT', 'RIGHT'`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As discussed in class, uninformed search can be costly to run.  Therefore we will focus on solving this problem using the A* algorithm.  For that, you will need to propose and implement heuristics that will assist the algorithm in finding the solution in a timely manner."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For your implementation use the code provide in `search.py`.  Using this framework, what you need to do is to write a class that inherits from the generic class `Problem`.  We'll call that class `two_Ls`.  A stub that you need to complete is provided below.  You will need to add methods that will allow you to solve the puzzle with the search algorithms implemented in `search.py`.  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from search import Problem\n",
    "\n",
    "class two_Ls(Problem) :\n",
    "    \"\"\"\n",
    "    A class that encapsulates the 'Making two Ls meet' puzzle\n",
    "    \"\"\"\n",
    "    # fill in the necessary methods to make the class work in conjuntion\n",
    "    # with search functions in search.py\n",
    "    # this incl. methods such as actions, goal_test etc.\n",
    "    # see the implementation of EightPuzzle in search.py for an example\n",
    "    # you can follow\n",
    "    def __init__(self, initial=(1,1,1,2,2, 3,3,4,4,2, 7,5,5,6,6, 7,7,8,8,8, 0,0,0,9,0)) :\n",
    "        self.initial = initial\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following two cells, implement and describe two admissible heuristics for the problem.  Explain why they are admissible.  Make sure that the two heuristics are distinct from each other and capture different notions of the idea of a \"good search direction\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def h1(node):\n",
    "    return 0\n",
    "def h2(node):\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*description of your heuristics and why they are admissible*\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given the above code that you have written, you can now solve the puzzle.  Fill in the following method that is supposed to return a list of actions, that when applied to the initial state, will lead to a goal state:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_puzzle(puzzle) :\n",
    "    \"\"\"Receives and instance of the class two_Ls and returns\n",
    "    a list of actions, that when applied to an initial state, lead to a \n",
    "    goal state.\n",
    "    \"\"\"\n",
    "    return [(9, 'RIGHT'), (7, 'DOWN'), (8, 'LEFT')]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the list `[(9, 'RIGHT'), (7, 'DOWN'), (8, 'LEFT')]` comprises the first three actions found by our solution to the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To test your `solve_puzzle` we will test whether the state/action sequence returned by the method is valid under the rules of the puzzle, and that they lead to a solution.  We will also test your `two_Ls` class in detail."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Answer the following:\n",
    "\n",
    "* Run your code, and compare the number of nodes expanded by A* with the heuristics you have proposed.  \n",
    "* Which heuristic worked better?  Can you explain why?  \n",
    "* Do you expect DFS or BFS to yield a result in a reasonable amount of time?  Explain!\n",
    "\n",
    "For retrieving the number of nodes expanded during the search, you may use the `InstrumentedProblem` class in `search.py`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code for comparing heuristics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Show your results and discuss them here*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grading\n",
    "\n",
    "Your notebook will be run and graded automatically.  So make sure your code satisfies the specified API, i.e. correct naming and behavior of your methods and classes.  In addition, the TAs will read the description of the heuristics.  \n",
    "\n",
    "Grading Rubric:\n",
    "\n",
    "60 pts:  Correctness of your code for solving the puzzle.\n",
    "\n",
    "20 pts:  The proposed heuristics make sense, are distinct, and their admissibility is discussed in a convincing manner.\n",
    "\n",
    "20 pts:  Comparison of the heuristics and discussion of your results"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}