week11_backtracking.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Backtracking\n",
    "\n",
    "Many computational problems can be solved by systematically searching over the set of possible solutions:\n",
    "\n",
    "* to solve a maze, you can try every possible path from the starting point\n",
    "* to solve a sudoku puzzle, you can set the first empty square to a 1, and then try to solve the rest of the\n",
    "puzzle\n",
    "    * if you don't find a solution, then undo everything and set the first empty square to a 2, and then try\n",
    "    to solve the rest of the puzzle\n",
    "        * repeat the process until you find a solution\n",
    "* \n",
    "\n",
    "Backtracking is a possible strategy when the solution to a problem involves one or more steps, and at each\n",
    "step there is one or more choices that can be made. Backtracking builds a solution recursively by attempting\n",
    "all of the choices at each step. If a point is reached where no solution is possible, then we backtrack to\n",
    "a previous step and make a different choice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The JumpIt problem\n",
    "\n",
    "We begin by examining a problem that has a simple recursive solution that does not use backtracking, and then\n",
    "we examine a variation of the problem that requires backtracking.\n",
    "\n",
    "The JumpIt problem is a game played on a linear board made up of $n \\geq 2$ squares where each square is\n",
    "marked with a non-negative number equal to the cost of stepping on the square. The game starts on the\n",
    "leftmost square. On each move, you can move one or two squares to the right with the goal of reaching the\n",
    "rightmost square. The problem is to find the sequence of moves having the lowest total cost.\n",
    "\n",
    "The following figure shows an example of a small JumpIt board.\n",
    "\n",
    "![](week11/jumpit1.png)\n",
    "\n",
    "The reader can easily verify that the sequence of moves producing the smallest cost is to move 1 square, then \n",
    "2 squares, and then 2 squares for a total cost of $0 + 3 + 6 + 10 = 19$:\n",
    "\n",
    "![](week11/jumpit2.png)\n",
    "\n",
    "The solution in the above figure corresponds to choosing to move to the next square having the lowest cost. Such\n",
    "strategies are called *greedy strategies* because they make a decision by choosing the best next move without\n",
    "considering whether such a decision in fact leads to best overall solution. In the JumpIt problem, a greedy\n",
    "strategy does not always lead to the lowest cost as illustrated in the following example:\n",
    "\n",
    "![](week11/jumpit3.png)\n",
    "\n",
    "**Exercise 1** Why does the greedy strategy sometimes not produce the sequence of moves having the lowest\n",
    "total cost?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A recursive solution\n",
    "\n",
    "We would like to write a recursive function `cost(board)` that returns the lowest cost for the given `board`. A\n",
    "recursive solution is possible because we know that the total cost is equal to the cost of the leftmost square\n",
    "plus the *minimum* of two possible values:\n",
    "\n",
    "* `cost(<board after moving 1 square>)`\n",
    "* `cost(<board after moving 2 squares>)`\n",
    "\n",
    "There are two base cases to consider. The first base case occurs for the smallest possible board size of\n",
    "$n=2$ where the total cost is simply the sum of the costs of the two squares. The second base occurs for a\n",
    "board size of $n=3$ where the total cost is the sum of the costs of the first and last squares.\n",
    "\n",
    "A recursive solution for finding the smallest total cost for JumpIt is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "19\n",
      "23\n"
     ]
    }
   ],
   "source": [
    "def cost(board):\n",
    "    n = len(board)\n",
    "    if n == 2:\n",
    "        return board[0] + board[1]\n",
    "    elif n == 3:\n",
    "        return board[0] + board[2]\n",
    "    else:\n",
    "        c1 = board[0] + cost(board[1:])\n",
    "        c2 = board[0] + cost(board[2:])\n",
    "        return min(c1, c2)\n",
    "    \n",
    "board = [0, 3, 80, 6, 57, 10]\n",
    "print(cost(board))\n",
    "board = [17, 1, 5, 6, 1]\n",
    "print(cost(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exericse 2** Rewrite `cost` so that it avoids slicing or copying the board. You will need to introduce a\n",
    "helper method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3** Why is the base case for $n=3$ required? What happens if you remove it? Can you replace it with\n",
    "a different base case?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A variation of JumpIt\n",
    "\n",
    "Consider the following variation of JumpIt played on a board such as the one shown below:\n",
    "\n",
    "![](week11/board1.png)\n",
    "\n",
    "Starting from the leftmost square, we want to know if it is possible to reach the rightmost square (which always\n",
    "has the number 0 on it). You can move\n",
    "$m$ squares left or right from the current square where $m$ is equal to the number on the square, but you cannot\n",
    "move off of the board; for example, on the board shown above, the first move must be two squares to the right.\n",
    "\n",
    "The board shown above has at least two different solutions:\n",
    "\n",
    "| Starting square | Move direction | Landing square |\n",
    "| :- | :- | :- |\n",
    "| 2 | right | 4 |\n",
    "| 4 | right | 1 |\n",
    "| 1 | right | 6 |\n",
    "| 6 | left | 3 |\n",
    "| 3 | right | 5 |\n",
    "| 5 | right | 0 |\n",
    "\n",
    "| Starting square | Move direction | Landing square |\n",
    "| :- | :- | :- |\n",
    "| 2 | right | 4 |\n",
    "| 4 | right | 1 |\n",
    "| 1 | left | 2 |\n",
    "| 2 | left | 2 |\n",
    "| 2 | left | 3 |\n",
    "| 3 | right | 5 |\n",
    "| 5 | right | 0 |\n",
    "\n",
    "Unlike the original version of JumpIt, it is possible to find cycles where a move takes you back to square\n",
    "that you have already visited; for example, a cycle exists between the two squares marked with a 2:\n",
    "\n",
    "![](week11/board2.png)\n",
    "\n",
    "It is possible to create boards with longer cycles. For example, if we change the square marked with a 3 to a 1\n",
    "then it is possible to create a sequence of moves that returns to the starting leftmost square.\n",
    "\n",
    "On the following board, every sequence of moves eventually leads to a cycle which means that no solution\n",
    "exists:\n",
    "\n",
    "![](week11/board3.png)\n",
    "\n",
    "Even without cycles, it is easy to create a board where no solution exists:\n",
    "\n",
    "![](week11/board4.png)\n",
    "\n",
    "From the above discussion, we can observe that when considering a sequence of moves we can reject the sequence\n",
    "as a candidate solution if it:\n",
    "\n",
    "* visits a square that has already been visited, or\n",
    "* visits a square where there are no legal moves\n",
    "\n",
    "To determine if a square has been previously visited, we require someway to record which squares have been\n",
    "visited. We could create a list of visited squares where we store the index of the visited squares, but this\n",
    "requires additional memory of order $O(n)$ if there are $n$ squares in the board. An alternative approach is\n",
    "to modify the board to indicate that a square has been visited. We can do this by changing the value of the\n",
    "number on a square by negating the value; all visited squares will then have a negative value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A general backtracking algorithm\n",
    "\n",
    "A backtracking alorithm explores all possible candidate solutions but abandons (or backtracks) a candidate solution\n",
    "when it can determine that the candidate does not lead to a solution. A general backtracking algorithm has the\n",
    "following structure:\n",
    "\n",
    "```\n",
    "explore(scenario):\n",
    "    if a solution is reached:\n",
    "        return the solution\n",
    "    else:\n",
    "        for each choice:\n",
    "            if the choice is not a dead end:\n",
    "                make the choice\n",
    "                solution = explore(updated scenario)\n",
    "                if there is a solution:\n",
    "                    return the solution\n",
    "                else:\n",
    "                    undo the choice\n",
    "        return no-solution\n",
    "```\n",
    "\n",
    "In the algorithm shown above, the `scenario` is all of the information needed to describe the current state of\n",
    "a candidate solution. In our problem, the `scenario` would consist of a board and the current location\n",
    "(index) on the board.\n",
    "\n",
    "We know that a solution has been obtained if the current location on the board is the last square of the board.\n",
    "\n",
    "For any square of the board, there are two possible choices for the next move: We can move $m$ squares to the\n",
    "left or we can move $m$ squares to the right where $m$ is the value of the current square.\n",
    "\n",
    "A choice is a dead end if it results in moving off of the board or if it moves to an already visited square.\n",
    "\n",
    "Making a choice means moving $m$ squares left or right. To make the choice, we:\n",
    "\n",
    "1. update the square that we are currently on by negating its value (to indicate that we have visited the square)\n",
    "2. create a variable `next_loc` equal to the index of the square that we have chosen to move to\n",
    "\n",
    "`next_loc` is passed to the recursive call as part of the `updated scenario`.\n",
    "\n",
    "To undo a choice, we:\n",
    "\n",
    "1. unmark the square that we are currently on by negating its value (making it positive to indicate that the\n",
    "square has not been visited)\n",
    "\n",
    "The following cell contains an implementation of the `explore` algorithm shown above. `explore` is called\n",
    "as a recursive helper function by the function `is_solvable`. A separate function `is_dead_end` implements\n",
    "the tests that determine if a scenario is a dead end (does not lead to a solution)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def is_dead_end(board, loc):\n",
    "    # is loc off of the board?\n",
    "    if loc < 0 or loc >= len(board):\n",
    "        return True\n",
    "    # is loc already visited?\n",
    "    if board[loc] < 0:\n",
    "        return True\n",
    "    return False\n",
    "    \n",
    "\n",
    "def explore(board, curr_loc):\n",
    "    n = len(board)\n",
    "    if curr_loc == n - 1:\n",
    "        return True\n",
    "    else:\n",
    "        # value of square we are currently on\n",
    "        m = board[curr_loc]\n",
    "        # choices are the indexes of the squares m spots to the left and right\n",
    "        choices = [curr_loc - m, curr_loc + m]\n",
    "        for choice in choices:\n",
    "            if not is_dead_end(board, choice):\n",
    "                # make the choice\n",
    "                board[curr_loc] = -board[curr_loc]\n",
    "                next_loc = choice\n",
    "                # explore the choice\n",
    "                has_solution = explore(board, next_loc)\n",
    "                if has_solution:\n",
    "                    return True\n",
    "                else:\n",
    "                    # undo the choice\n",
    "                    board[curr_loc] = -board[curr_loc]\n",
    "        return False\n",
    "\n",
    "\n",
    "def is_solvable(board):\n",
    "    return explore(board, 0)\n",
    "\n",
    "\n",
    "board = [2, 3, 4, 2, 5, 2, 1, 6, 9, 0]\n",
    "print(is_solvable(board))\n",
    "board = [2, 1, 2, 2, 2, 2, 2, 6, 3, 0]\n",
    "print(is_solvable(board))\n",
    "board = [1, 100, 2, 0]\n",
    "print(is_solvable(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 4** Modify the function `explore` so that it returns a list of the indexes of the squares that are\n",
    "moved to during a solution, or an empty list if there is no solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The eight queens puzzle\n",
    "\n",
    "The [eight queens puzzle](https://en.wikipedia.org/wiki/Eight_queens_puzzle) is a very common problem used\n",
    "to teach recursive backtracking. The goal of the puzzle is to place eight queens on a chessboard so that no\n",
    "queen is attacking another queen:\n",
    "\n",
    "![](week11/queens.png)\n",
    "\n",
    "In chess, a queen can move any number of squares horizontally, vertically, or diagonally. A solution for the\n",
    "eight queens puzzle places the queens so that no row, column, or diagonal has more than one queen.\n",
    "\n",
    "One way to solve the puzzle is to start by placing one queen and then building the solution one queen at a time\n",
    "until all eight queens are successfully placed. Because two queens cannot appear in the same row or column, we\n",
    "can start by placing the first queen in column 0, followed by the second queen in column 1, followed by \n",
    "the third queen in column 2, and so on.\n",
    "\n",
    "To use the general backtracking algorithm, we need to determine:\n",
    "\n",
    "* how to define the scenario\n",
    "* when is a solution reached\n",
    "* what choices exist when placing a queen\n",
    "* if a choice is a dead end\n",
    "* how to make a choice\n",
    "* how to undo a choice\n",
    "\n",
    "The scenario is described the locations of the currently placed queens. If we imagine the board to be an\n",
    "$8 \\times 8$ grid where each row and column is numbered from 0 to 7, then we can use a list `queens` containing the\n",
    "row indexes of each queen\n",
    "\n",
    "A solution is reached when all eight queens are successfully placed.\n",
    "\n",
    "When placing a queen in column $i$, we have a choice of eight rows to place the queen in. Therefore, our choices\n",
    "are the eight indexes 0, 1, 2, ..., 8.\n",
    "\n",
    "A choice of row is a dead end if there is another queen in the same row or on a diagonal location relative to \n",
    "the choice. Finding the diagonal locations relative to another location is the only tricky part of this problem.\n",
    "\n",
    "To make a choice, we add the chosen row index to the end of the list `queens`.\n",
    "\n",
    "To undo a choice, we remove the last element from the list `queens`.\n",
    "\n",
    "The cell below contains an implementation of the general backtracking algorithm that solves the eight queens\n",
    "puzzle. `explore` does not return a list of queen locations; instead, it fills in the list `queens` with the\n",
    "row index of each queen so that `queens[i]` contains the row index of the queen in column `i`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 7, 4, 2, 0, 6, 1, 5]\n"
     ]
    }
   ],
   "source": [
    "def is_dead_end(queens, row):\n",
    "    # is there another queen in the specified row?\n",
    "    if row in queens:\n",
    "        return True\n",
    "    n = len(queens)\n",
    "    # offset is the change in row index for a column somewhere\n",
    "    # to the left of the next queen to be placed\n",
    "    offset = 1\n",
    "    for col in range(n - 1, -1, -1):\n",
    "        # the row index of the queen in col\n",
    "        r = queens[col]\n",
    "        # is r diagonal to row?\n",
    "        if r == row + offset or r == row - offset:\n",
    "            return True\n",
    "        offset = offset + 1\n",
    "    return False\n",
    "    \n",
    "import random\n",
    "def explore(queens):\n",
    "    n = len(queens)\n",
    "    if n == 8:\n",
    "        return\n",
    "    else:\n",
    "        rows = list(range(0, 8))\n",
    "        random.shuffle(rows)\n",
    "        for choice in rows:\n",
    "        #for choice in range(0, 8):\n",
    "            if not is_dead_end(queens, choice):\n",
    "                # make the choice by placing the next queen in row choice\n",
    "                queens.append(choice)\n",
    "                # explore the choice\n",
    "                explore(queens)\n",
    "                if len(queens) == 8:\n",
    "                    # placed all eight queens, done\n",
    "                    return\n",
    "                else:\n",
    "                    # undo choice by removing the previously placed row\n",
    "                    queens.pop()\n",
    "\n",
    "def eight_queens():\n",
    "    queen_locs = []\n",
    "    explore(queen_locs)\n",
    "    return queen_locs\n",
    "\n",
    "print(eight_queens())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 5** `explore` always produces the list `[0, 4, 7, 5, 2, 6, 1, 3]` because the row choices are always\n",
    "in the order 0, 1, 2, ..., 7. Modify `explore` so that the row choices are shuffled in a random order."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 6** The [subset sum problem](https://en.wikipedia.org/wiki/Subset_sum_problem) is a well known\n",
    "problem in computing science that can be solved using backtracking. Given a list of positive integer values and\n",
    "a positive integer target value $t$, is there a subset of the values in the list that sum exactly to $t$?\n",
    "Formulate a recursive backtracking solution for the subset sum problem. You may assume that the list of\n",
    "values is sorted from largest to smallest value and that the values in the list are unique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 7** The mini-Sudoku problem requires you to arrange the numbers 1, 1, 1, 2, 2, 2, 3, 3, 3 on a\n",
    "$3 \\times 3$ grid so that no number is repeated in any row or column. An example of a solvd mini-Sudoku\n",
    "puzzle is:\n",
    "\n",
    "```\n",
    "1 2 3\n",
    "3 1 2\n",
    "2 3 1\n",
    "```\n",
    "\n",
    "Given an incomplete $3 \\times 3$ array of values `arr`, write a recursive backtracking function that fills in the\n",
    "missing values to complete the mini-Sudoku puzzle. Use the value 0 to indicate a missing value; for example,\n",
    "if `arr` is defined as:\n",
    "\n",
    "```python\n",
    "arr = [[0, 0, 0],\n",
    "       [0, 0, 2],\n",
    "       [0, 3, 1]]\n",
    "```\n",
    "\n",
    "then your solution should replace the zeros with the appropriate values to complete the puzzle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 8** (Longer problem; no solution will be provided) Repeat Exercise 7 for the $9 \\times 9$ version\n",
    "of Sudoku."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}