Skip to main content

Backtracking

Giving recursion structure a name

It's just a name we give for a certain structure of a recursive method.  it's simply a form of a recursion.

Backtracking is a name for a recursive structure
Agenda

Here is our agenda for this episode, we are going to try in free text and words to describe what backtracking means, how does it relate to other common types of recursions, why you should already know and even practice backtracking without even knowing it, what are the ingredients and structure and steps for creating a backtracking recursive solutions, and briefly describe two problem solutions that involved backtracking.

Backtracking Sudoku


Giving it a name

It's useful to give names to the type's of a recursive solution.  In this way if I tell you my recursion is a tail recursion or my recursion is a backtracking recursion you already have much information about what kind of solution we had in mind for our problem, or you could already imagine how the body of the recursive function looks like so you would be able to immediately actually understand the function.

Building a backtracing recursion

Did you know that when you search a binary tree in a recursive manner you are actually running the backtracking algorithm?

Binary tree search uses backtracking

When we look at merge sort or quick sort I could tell you that I used a recursive algorithm so you would already have hints into how I structured the code in this problem solution, but once I tell you I used a divide and conquer technique you already have many hints into my solution, that is, you know that in each call I divided the input into multiple parts and each such recursive call works on each of these parts as if it's the whole part.

Note that in a recursive divide and conquer merge sort algorithm we do not have a condition that tells the function no no I got this partial solution wrong I didn't manage to sort this half of this array so go back and start again differently, we don't have this, we keep on going and sorting shorter sequences of the whole array, and we just move on and sort them at no point do we say we got this sorting wrong, so we need to dump this solution and get back or in other words backtrack.

In divide and conquer we assume solutions correct

However, if I tell you that I solved a problem with backtracking, then this give you other hints into my recursive function, if I told you I have a backtracking solution, you would know this:

1. The function assumes it can solve fully part of the problem
2. The function has a condition - a test if this sub solution is right or not.
3. If sub solution is correct we move on
4. If sub solution with a condition was wrong we exit and move up the recursion tree.
5. Once we move up the recursion tree, we move on to next try so it's possible that we had a loop of 1..n and inside this for loop we do a recursive call and if this recursive call failed then it moves up.

The cases

Usually what we see is that we have multiple options, and we need to choose one of the options which means we have a condition for each of them.

We can look at a backtracking solution as a recursive tree, when we run this recursion, and we draw that tree all along, then some leaves would be correct solutions and some not, basically we scan the tree, we could look at it as scanning the tree left to right, getting to the most left bottom leaf checking if solution is good or not and continuing until we find a good solution

Look at backtrackign with recursive tree eyes

The general algorithm for backtracking

We get a problem to be solved, we check if we are on a leaf node, if it's the last node, if yes then we check if it's a good solution if true we return true or the solution itself that we saved otherwise we return false which means we backtrack because no good solution on this leaf.

If the current node that we got on the recursive call is not a leaf node then we need now to loop the solutions on this level that we have one by one, and then we call recursively on each such sub problem, and we ask if we have solution for it recursively if yes we return the solution otherwise we return false.

Note the importance of the condition here, as opposed to algorithms of recursive divide and concur such as merge sort where we simply divide the problem and solve each we don't ask if our sorting is correct or not.

There is also an option to do backtracking with non-recursive algorithms, this is pretty standard for recursive algorithms we use a stack.

Non recursive backtracking with a stack

Binary Tree Search

When you search a binary tree you are as we said running the backtracking algorithm when you do this recursively.

You start from the root node and you ask for each node is it the leaf node and if so did we found the target node or not.

We have a condition the condition is simply if we found the value that we wanted or not, if not then we return false, and we backtrack to continue the search.

We simply first check if our node that we accepted is null, if it's null, and we wanted to find a value which is not null then we return false as this value does not exist.

If this node is the value that we wanted we return true because we found the node.

Otherwise, we recursively call on left node to find the value and if found then we return true, and we recursively find on right now and if found we return true.

The n queens

The n queens problem is another canonical problem which can be solved with backtracking which is again just a fancy word of saying that the recursion type or form that we use in order to solve the n queen's problem is of this form:

1. Solve first row we have n options for placing the queen on first row, but we do a for loop for choosing the column for this queen and this would be the very same for loop that we are going to use for the backtracking.
2. Check if our solution is ok so far, if yes continue with calling the recursion on the rest of the problem,
3. if not then simply return from the function it could be that we just finish the function and this would serve as backtracking.


Summary

Backtracking is an important recursive technique where we construct a solution incrementally and in each such step of recursion we check if our current solution is correct or not, if correct we continue, if not we return from the recursive function and move on with our for loop to try the next solution.

Comments

Popular posts from this blog

Dev OnCall Patterns

Introduction Being On-Call is not easy. So does writing software. Being On-Call is not just a magic solution, anyone who has been On-Call can tell you that, it's a stressful, you could be woken up at the middle of the night, and be undress stress, there are way's to mitigate that. White having software developers as On-Calls has its benefits, in order to preserve the benefits you should take special measurements in order to mitigate the stress and lack of sleep missing work-life balance that comes along with it. Many software developers can tell you that even if they were not being contacted the thought of being available 24/7 had its toll on them. But on the contrary a software developer who is an On-Call's gains many insights into troubleshooting, responsibility and deeper understanding of the code that he and his peers wrote. Being an On-Call all has become a natural part of software development. Please note I do not call software development software engineering b

SQL Window functions (OVER, PARTITION_BY, ...)

Introduction When you run an SQL Query you select rows, but what if you want to have a summary per multiple rows, for example you want to get the top basketball for each country, in this case we don't only group by country, but we want also to get the top player for each of the country.  This means we want to group by country and then select the first player.  In standard SQL we do this with joining with same table, but we could also use partition by and windowing functions. For each row the window function is computed across the rows that fall into the same partition as the current row.  Window functions are permitted only in the  SELECT  list and the  ORDER BY  clause of the query They are forbidden elsewhere, such as in  GROUP BY ,  HAVING  and  WHERE  clauses. This is because they logically execute after the processing of those clauses Over, Partition By So in order to do a window we need this input: - How do we want to group the data which windows do we want to have? so  def c

Building Secure and Reliable Systems

A recent book was published this year by Google about site reliability and security engineering, I would like to provide you a brief overview of it and incorporate my own analysis and thoughts about this subject while saving you some time from reading, at least part of it. Take a few of your customers and ask them, what are the top 5 features on my product that you like.  The answer that you are likely to get is, I really like how polished the UI is, or the daily report I get by mail is just fantastic, or since I started using your product I was able to save one hour a day my productivity got up and the share /chat button on document that you added recently is doing a great job. Your customers are very unlikely to answer the question of what top 5 features of my product do you like with I really like its security or I really like that we lost no chat messages since I started using it.  No real customer will even think of it, moreover, assuming you did a very good job, they won&#