Backtracking: Problems & Solutions
Here is a compilation of problems with solutions (visualisations) and explanations related to backtracking.
How do we solve a backtracking problem? usually most of the problems have multiple paths and output which is achieved out of these one or more paths.
The major problems faced in determining a solution are :
- Visualisation of the paths (decision tree)
- Find the base condition when to STOP (return).
- Also finding the minimum unit of work for small subset.
Once we are able to find the answers to the above questions, the problem becomes relatively solvable.
Let us try to apply this thought process to solve the below problems and see if we have a framework which we can reuse to address many problems of this kind.
Problem#1 : The most popular problem, given a string S find all the permutations.
How would do we visualise this problem?
As we see above we go by choosing a single character, to start with, then we are left with a remainder, out which we choose another character and so on…
also observe the order.
We stop when we have no more choices to make. Now this will be the point of return for us.
Smallest unit of work here is :
a. choose a character from a string.
b. recursively call the function with the remainder of the string and the
chosen character.
c.replace the chosen character with the next character.
Problem #2: Print the all binary numbers of length N(size).
I/P (input) : 2
O/P (output) : {00,01,10,11}
Visualising this problem is pretty straight forward as shown below.
As shown above we have only two choices to make at every stage.
When do We STOP? When we reach a string size of the desired length(= N).
What is the smallest unit of work that needs to be done? To answer this question let us take an example of size=2 as shown above we see.
a. at each stage we have only two choices to make.
b. we need to append the either Zero or One.
Corollary for this problem is : Print all the binary numbers of length N with K bits set.
Eg..
I/P : N = 2 and K =1
O/P : {01,10}
The code would look the same with an extra addition line 3. This is a easy way out but we can do better than this. I would leave that for now.
Problem #3: Print all the decimals of length N
It is a similar problem as print binary numbers but the only difference being the number of paths for each selection would be from Zero to Nine.
Let us look at the decision tree (visualisation) to validate the above claim.
We STOP when the size of the string is equal to N
To the unit of work involved is:
a. Iterate through the possible digits.
b. Select a digit
c. repeat the above two steps for every decimal place.
The code would look like below.
Problem#4: Given a set print all its subsets.
Eg.
Input: {1,2,3}
Output: {{}, {1}, {1,2}, {1,2,3},{1,3},{2,3},{2},{3}}
This problem is different from the problems we have explored till now.
It involves a set and none of the subsets repeats itself, but just changing the order.
So how do we get to the decision tree (visualisation)? Below is the decision tree for the problem.
We STOP when we find that the given subset is empty.
The unit of work involved is:
a. we iterate through the given set.
b. condense the original set leaving out the first member.
c. add to the subset from the first member
d. then call recursively with new working set and the subset, till working set length becomes Zero.
e. pop back from the subset and get ready to add a new one element to the set, to form a new combination.
The verbatim translation to code is shown below.
Problem#5: Given N dice print all the combinations the dices can be rolled.
The problem cries for a classical backtracking problem.
Each dice can roll from One to Six.
Eg. If N=2 i.e. you are given two dice.
The number of combinations both dice can be rolled would be 6x6 = 36 ways.
The decision tree would look like below
As we see at each level we iterate through all available choices for a dice.
We STOP when do not have anything to choose from.
The unit of work involved:
a. Iterating throw all the possibilities for a given dice.
b. We chose a possibility and add it to the subset.
c. Then we recurse to the next dice with the subset.
d.once we are done with all the possibilities for a dice we pop back till we are ready for the next combination.
Problem 5# : Non-attacking placement of N-Queens.
This is a famous problem solution for which was proved to exist for all N >3.
Let us take minimum small sample size N = 4 and see how the solution pans out.
How would the Decision Tree for the problem look like?
So from the above decision tree we can make out each time the subset of squares we look at decreases once we exhaust all the subset we backtrack to the previous subset and decide if have to continue are backtrack once more.
So when do we STOP? When we find that in the available subset of squares none of them are safe to place a queen(all the rows and cols). We backtrack!.
What is the unit of work?
a. iterate through all the rows for a safe square.
b. if you find a safe square then place the queen there.
c. Try to place the next queen in the next column in all the rows.
d. if we do not find a proper square then remove the previously placed.
This took around 0.912835ms for N=4 for the above code to execute which is pretty slow!.
Google does this in in 0ms (probably in nanoseconds) due to their optimisations would be interesting to see how!.
That is all folks!!
Hope you liked the small compilation of problems.
In future I will be adding optimisations to the N Queens problem and solutions to Suduku problem as well.
References:
