{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Backtracking algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The branch and bound algorithm is very useful whenever you have to solve a maximisation/minimisation problem with constraints, such as the knapsack problem. \n",
    "\n",
    "The <b>backtracking algorithm</b> is basically the same as the branch and bound but without the function to maximise/minimise. Therefore the algorithm chooses as branch to explore always the deepest one, i.e. the one closer to the possible ending."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A problem for which it can be applied easily is the timetable problem, for which is it is for sure more efficient than the brute-force approach and, probably, also the optimized fuzzy approach.\n",
    "\n",
    "Let's review the problem:\n",
    "- a weekly scheduling \n",
    "- two hours slot, only 8-10, 10-12, 12-14, 14-16, 16-18\n",
    "- from 8:00 to 18:00 \n",
    "- from Monday to Friday \n",
    "- 4 courses (Coletti, Fedele, Kraus, Simonelli) to accomodate in the timetable.\n",
    "\n",
    "and the constraints:\n",
    "- each course exactly 6 hours in the week (it's not true), i.e. three slots\n",
    "- no lesson on Monday morning, i.e. slots first and second must be 0;\n",
    "- maximum 1 slot every day for each course\n",
    "- Coletti never lesson on two consecutive days\n",
    "- Fedele and Kraus can never meet, i.e. their lessons cannot be consecutive\n",
    "- no lesson on Friday afternoon, i.e. fourth and fifth slot of Friday must be 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backtracking example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let'a apply the backtracking algorithm to the timetable problem. \n",
    "\n",
    "We start with an empty timetable and that is our first branch and only branch at depth 0. \n",
    "\n",
    "We take it and branch into five branches at depth 1, each one with a different assignment for slot 1 of day 1: nobody, Coletti, Fedele, Kraus, Simonelli. We check them against our constraints and we see that already Coletti, Fedele, Kraus, Simonelli fail to satisfy our \"no lesson on Monday morning\" constraint and thus they are deleted. The only remaining branch in the tree is nobody at slot 1 and it is a branch at depth 1.\n",
    "\n",
    "<img src=\"http://www.paolocoletti.it/algorithmicthinking/images/backtracking1.jpg\">\n",
    "\n",
    "We branch it into five branches at depth 2, each one with a different assignment for slot 2 of day 1: nobody, Coletti, Fedele, Kraus, Simonelli. We check them against our constraints and we see that already Coletti, Fedele, Kraus, Simonelli fail to satisfy our \"no lesson on Monday morning\" constraint and thus they are deleted. The only remaining branch in the tree is nobody at slot 1 and nobody at slot 2 and it is a branch at depth 2.\n",
    "\n",
    "<img src=\"http://www.paolocoletti.it/algorithmicthinking/images/backtracking2.jpg\">\n",
    "\n",
    "We branch it into five branches at depth 3, each one with a different assignment for slot 3 of day 1: nobody, Coletti, Fedele, Kraus, Simonelli. We check them against our constraints and we see that all of them satisfy the constraints. Thus we currently have 5 branches in the tree all at depth 3.\n",
    "\n",
    "<img src=\"http://www.paolocoletti.it/algorithmicthinking/images/backtracking3.jpg\">\n",
    "\n",
    "At this point we take randomly one of them (we could also take one of them using a rule if you have any heuristic rule that helps you, perhaps you can take the most problematic professor first which in this example is Coletti). For example let's take the branch with nobody, nobody, Kraus. We branch it into five branches at depth 4, each one with a different assignment for slot 4 of day 1: nobody, Coletti, Fedele, Kraus, Simonelli. We check them against our constraints and we see that all of them satisfy the constraints, except putting Kraus again and putting Fedele. So we delete the Kraus's and Fedele's branches and currently we have 4 branches in the tree at depth 3 and 3 branches at depth 4.\n",
    "\n",
    "<img src=\"http://www.paolocoletti.it/algorithmicthinking/images/backtracking4.jpg\">\n",
    "\n",
    "We take always the deepest branch (this is a <b>depth-first algorithm</b>), i.e. one of the 3 branches at depth 4. For example, let's take the one with nobody, nobody, Kraus, Simonelli. We branch it into five branches and check their validiy. Only nobody, Coletti and Fedele are valid (if you wrote the condition on Coletti as \"Coletti never on two consecutive days\". On the other hand, if you wrote is as \"always on Monday, Wednesday and Friday\" only Coletti's branch is valid). We now have 4 branches at depth 3, 2 branches at depth 4 and 3 branches at depth 5. \n",
    "\n",
    "<img src=\"http://www.paolocoletti.it/algorithmicthinking/images/backtracking5.jpg\">\n",
    "\n",
    "We take one of the three branches at depth 5 and...\n",
    "\n",
    "Sooner or later you will probably end up with all the branches which are not valid and you will have to take into consideration branches at one upper depth. That's why it is called \"<u>back</u>tracking\".\n",
    "\n",
    "<img src=\"http://www.paolocoletti.it/algorithmicthinking/images/backtrackingAll.jpg\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backtracking description"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's describe the algorithm theoretically.\n",
    "\n",
    "First of all the algorithm needs a function which checks the validity of a partial solution. The algorithm starts with an empty solution, where nothing has been decided and which obviously must be valid. This is the branch at depth 0.\n",
    "\n",
    "Then the algorithm starts its main loop. It takes the deepest open branch. In case there are more branches at the maximum depth it takes one randomly or following any heuristic rule you like. The algorithm considers one of the possible still unsolved microproblems of this branch (in our example it is \"who teaches at day X slot Y\") and creates all the possible partial solutions. Each one is checked for its validity and discarded if not valid. The valid ones are inserted as open branches at depth 1 more.\n",
    "\n",
    "When the algorithm analyses a branch for which no more microproblem is open (in our example all the timeslots have been assigned) this is a leaf. It can be easily recognized as it has reached a depth equal to the number of microproblems (in our example 25). It checks the validity of the leaf using the check function for a complete solution, as there may be constraints which can only be checked when the timetable is complete (in our example the fact that each professor teaches 3 hours per day). If it is not valid, it is cancelled and the algorithm goes on. If it is valid, it is a solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exactly as for the branch and bound, the backtracking algorithm does not reduce the complexity in the worst case. If your problem is such nasty that all the constraints can be checked only on the final solution, you will have to go everytime up to the leaf which corresponds to a brute-force approach. \n",
    "\n",
    "However, many problems allow you to check also the validity of partial solutions. You can see in the example above that cutting 4 branches at depth 1 reduces the complexity to 20% and cutting other 4 branches at depth 2 further reduced the complexity to 20%. Only with these two steps the complexity is now 4% of the original one. \n",
    "\n",
    "Therefore it is important to put as many constraints as possible in the function which checks the validity of partial solutions, to make it work and cut useless branches as soon as possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Data structure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We shall indicate each partial timetable TT as <font color=GREEN><b>[ [0,0,3,4,1] , [2,4] , [ ] , [ ] , [ ] ]</b></font> . Obviously, unless you are looking for troubles, the assigned slots will be the first ones and the unassigned will be the last ones. \n",
    "\n",
    "Therefore, together with TT, it is useful to indicate also the depth (in this case 7), the last day in which we have assignments (in this case 1) and the last slot for which we have assignments (in this case 1). These data can be deduces from the partial timetable, buy having them handy will make our life easier for the ckeckPartial function below.\n",
    "\n",
    "Thus our structure BT will be a list which contains elements such as <font color=BLUE>[depth, last filled day, last filled slot of that day, TT]</font>, in our example: <font color=GREEN><b>[ 7 , 1 , 1 , [ [0,0,3,4,1] , [2,4], [ ] , [ ] , [ ] ] ]</b></font> . "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Check function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to rite two check functions here. One is the one that you also used for the brute force approach and is used only to check the validity of the leaves. The other function must be able to check the validity of partial solution, so:\n",
    "- some constraints can be checked only on the final timetable and these ones are skipped\n",
    "- some constraints can be in part checked on the partial timetable and it is worthwhile to modify them to check whatever you can check, because any restriction you check early will cut useless branches\n",
    "- some constraints can be fully checked also on the partial timetable, probably paying attention that some slots now can be unassigned"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Take your own original check function. Keep it and build another checkPartial function which takes as input a partial timetable, its last filled day and its last filled slot and checks its validity. Pay attention that it must take care that some slots are unassigned. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check(TT):\n",
    "# write here your original own check function\n",
    "\n",
    "\n",
    "def checkPartial(D,S,TT):\n",
    "# Obvisouly some checks need to be adjusted. You have two possible strategies here. \n",
    "# Strategy 1: your function checks the entire calendar that is available, up to day D-1 and for day=D it checks \n",
    "# only up to slot S. For this strategy it will be much much easier to use for loops rather than while loops, as\n",
    "# in this way you do not have to check how many elements are in the list.\n",
    "# Strategy 2, easier: your function takes for granted that everything up the the second-last slot is correct and\n",
    "# it checks only that the newly inserted element, which is in day D and slot S, is correct with respect to the rest.\n",
    "# This perhaps require more rewriting, but it is honestly easier to think at\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do not forget to test it!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(checkPartial(0,0,[ [0],[],[],[],[] ]))\n",
    "print(checkPartial(0,3,[ [0,0,4,1],[],[],[],[] ]))\n",
    "print(checkPartial(1,1,[ [0,0,3,4,1] , [2,3],[],[],[] ]))\n",
    "print(checkPartial(1,1,[ [0,0,3,1,2] , [2,4],[],[],[] ]))\n",
    "print(checkPartial(1,4,[ [0,0,3,1,2] , [2,4,0,0,1],[],[],[] ]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's build here the algorithm!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy\n",
    "import random \n",
    "\n",
    "def insertBT(BT, depth, day, slot, TT):\n",
    "    # this function inserts [depth,day,slot,TT] into the data structure BT in its right place, \n",
    "    # keeping BT sorted from largest depth to smallest. \n",
    "    # In case you must insert an element with the same depth as an existing one, it doesn't matter whether inserting it before or after\n",
    "\n",
    "# how do you make it? Well, copy my insertBB function and modify it to adapt it to the current situation.\n",
    "# that's how 95% of modern programs are written....\n",
    "    \n",
    "\n",
    "    \n",
    "    \n",
    "\n",
    "# we set up the first branch, i.e. the ROOT, with depth 0, current filled day -1, current filled slot 4 \n",
    "# (setting -1 and 4 will help you branching correctly into branches with current day 0 and current slot 0)\n",
    "BT=[[0,-1,4,[[],[],[],[],[]]]]\n",
    "\n",
    "# now we loop and write the core of the algorithm\n",
    "while True:\n",
    "    # we take the first element out from the list and store it in a variable. Do not forget that the element is made up of \n",
    "    # [depth,day,slot,TT]\n",
    "    # please write the code here\n",
    "    \n",
    "\n",
    "    # we check whether the element we just took out is a leaf, i.e. depth is 25\n",
    "    # In this case, we check its validity and if it is a valid complete solution we print the result. \n",
    "    # If it is not valid, we have already popped it out and we just go back with the while loop\n",
    "    \n",
    "    # please write the code here\n",
    "\n",
    "\n",
    "    \n",
    "    # else when the first element of BT is not a leaf, we have to branch \n",
    "    # building all the branches and inserting them in the data structure BT (if they are valid)\n",
    "    # pay attention when building TT that if slot is equal to 4, you will have to insert a new day\n",
    "\n",
    "    # NOTE: if for any reason you need to copy a list, beware that a=b is not a duplication of the list but only of the pointer\n",
    "    # to copy a list duplicating it, use  a=copy.deepcopy(b)  In this way a and b will be two different objects using two different spaces in the memory\n",
    "\n",
    "    # please write the code here\n",
    "           \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimisations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The biggest problem when running the above code is that when you have to insert something like [2,0,2,[0,0,1] ] in a structure such as [ [2,0,2,[0,0,0] ]] . They have the same depth. Do you insert it before or after? \n",
    "\n",
    "If you insert it after, you will have as first place most of the times a structure with several zeroes and you will see that your algorithm quickly arrives with a timetable full of zeroes and only at that point it realises that there are too few slots for professors 1,2,3,4 and starts to backtrack trying to put them somewhere.\n",
    "\n",
    "If you insert it before, you will have as first place most of the times Simonelli. This is much better, as Simonelli cannot go in more than 3 slots (i.e. the algorithm realises very soon that there are non valid branches). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertBTbefore(BT, depth, day, slot, TT):\n",
    "    # very easy, if you understand WHERE does the previous insertBT inserts, you see immediatley the one modification that will insert before\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Fuzzy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We randomly choose the place to put a branch, but only among the ones which have the same depth. You have to deduce the value of iStart and iEnd (the indexes where the branches with the same depth start and end) and pick up a random integer number between iStart and iEnd where you will insert the new branch."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Modify the insertBT accordingly and test the algorith with it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertBTrandom(BT, depth, day, slot, TT):\n",
    "    # this function inserts [depth,day,slot,TT] into the data structure BT in its right place, \n",
    "    # keeping BT sorted from largest depth to smallest. \n",
    "    # In case you must insert an element with the same depth as an existing one, it inserts it randomly\n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Most problematic first, otherwise randomly"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the current branch contains Coletti as the last slot, then insert it before all the branches with its same depth. Otherwise, insert it randomly among the branches with the same depth. \n",
    "\n",
    "In this way the algorithm will first try to fix Coletti who has the strongest constaint which will eliminate a lot of non valid branches. The rest randomly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Modify the inserBT accordingly and test the algorithm with it. With this technique I was able to find a solution instantly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertBTColetti(BT, depth, day, slot, TT):\n",
    "    # this function inserts [depth,day,slot,TT] into the data structure BT in its right place, \n",
    "    # keeping BT sorted from largest depth to smallest. \n",
    "    # In case you must insert an element with the same depth as an existing one, \n",
    "    # if it is a slot with Coletti at the end (day,slot) it is inserted first, otherwise randomly \n",
    "\n",
    "    # if you were not able to do the previous function, then if it is not Coletti \n",
    "    # insert it after all the ones with the same depth\n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
