In this chapter, you will explore some advanced aspects around recursion. You’ll start with the optimization technique called memoization. After that, you’ll look at backtracking as a problem-solving strategy that relies on trial and error and tries out possible solutions. Although this is not optimal in terms of performance, it can keep various implementations comprehensible.
7.1 Memoization
In Chapter 3, you saw that recursion is feasible for describing many algorithms and calculations in an understandable and, at the same time, elegant way. However, you also noticed that recursion sometimes leads to many self calls, which can harm performance. This applies, for example, to the calculation of Fibonacci numbers or of Pascal’s triangle. How can this problem be overcome?
For this purpose, there is a useful technique called memoization . It follows the same ideas as the caching or buffering of previously calculated values. It avoids multiple executions by reusing already calculated results for subsequent actions.
7.1.1 Memoization for Fibonacci Numbers
Conveniently, memoization can often be easily added to an existing algorithm and only requires minimal modification. Let’s do this for the calculation of Fibonacci numbers.
Performance comparison If you run both variants for the fortieth Fibonacci number, the purely recursive variant on my iMac 4GHz delivers a result after about 25 seconds, but the calculation of the forty-seventh Fibonacci number takes over 800 seconds, which corresponds to about 13 minutes! With memoization, on the other hand, you receive a result for both after a few milliseconds.
It should be noted that there is a variant of the Fibonacci calculation that starts at the value 0. Then fib(0) = 0 holds as well as fib(1) = 1 and afterwards recursively fib(n) = fib(n − 1) + fib(n − 2). This produces the same sequence of numbers as the initial definition, only with the value for 0 added.
Data type: The calculated Fibonacci numbers can get huge quite quickly. Conveniently, the Python number types scale, so unlike other languages, it should not be necessary to define a special type yourself so soon if necessary.
Recursive termination: For implementation purposes, it’s worth considering recursive termination before processing with memoization. This would probably be minimally more performant, but then the algorithm can’t be reformulated that clearly from the existing one. Especially if you are not familiar with memoization yet, the shown variant seems a bit more catchy.
7.1.2 Memoization for Pascal’s Triangle
Pascal’s triangle is defined recursively, as are the Fibonacci numbers:
A closer look reveals that you cannot use a basic type like int or str for the key but rather need a more special variant consisting of a row and a column due to the two-dimensional layout. For this purpose, you use a tuple consisting of row and column.
Performance comparison To compare the performance, I chose a call with the parameters for line 36 and column 12. The purely recursive variant requires a rather long running time of about 80 seconds for the selected values on an iMac with 4GHz. The optimized variant completes after a few milliseconds.
Conclusion
For the two examples presented here, the purely recursive definition results in many self calls. Without memoization, they cause the same intermediate results to be calculated and discarded over and over again. This is unnecessary and costs performance.
Memoization is a remedy that is as simple as it is ingenious and efficient. Additionally, many problems may still be solved elegantly with the help of a recursive algorithm, but without the need to accept the disadvantages in terms of performance. All in all, memoization can often reduce the running time (very) significantly.
The term “memoization,” which seems a bit strange, goes back to Donald Michie (https://en.wikipedia.org/wiki/Memoization). As described earlier, it is a technique to optimize the processing of computations by caching partial results. In such a way, nested calls with the same input can be accelerated significantly. However, for memoization to be used, the wrapped recursive functions must be pure functions . This means that such a function returns the same value if it is called with a particular input. In addition, these functions must be free of any side effects.
7.1.3 Memoization with Python On-Board Tools
- 1.
Separation of concerns: Application code and auxiliary code are slightly interwoven. Although the two are quite easy to separate visually, clarity and elegance are somewhat lost.
- 2.
Source code duplication: Memoization is actually a cross-cutting concern that should be solved in a general way. If, on the other hand, a separate implementation is made in each case, careless errors may creep in—even if this is unlikely due to the low complexity.
Memoization using a decorator
Built-in memoization with lru_cache from the module functools
Memoization with a Decorator
The example uses the concept of decorators, which is briefly introduced in Appendix B. In general, decorators work like aspect-oriented programming or proxies, wrapping the original functionality with some functionality of their own. Therefore, the original function is passed to the decorator, and the decorator returns a modified function.
Since you use a dictionary to manage data, the keys stored there must be immutable. Thus, the arguments may only use immutable types, such as numbers, strings, or tuples.
Decorator for Fibonacci numbers In Appendix B I explain how to use decorators for argument checks, leaving the actual function code unaffected. Therefore, the problem to be solved is reflected as closely as possible without special treatments.
Decorator for Pascal’s triangle Your memoization decorator has been designed so far to accept one parameter. But how do you proceed if you need to support two parameters for Pascal’s triangle computation and possibly even more for other functionalities?
Built-in Memoization with lru_cache from the functools Module
You have seen wrapping with a decorator before. By using a LRU cache (Least Recently Used) from the functools module, the whole thing can be written even more elegantly and shorter. Moreover, there is no longer the danger of erroneous calls because the memoization functionality is not realized by yourself.
7.2 Backtracking
Backtracking is a problem-solving strategy based on trial and error, and it investigates all possible solutions. When detecting an error, previous steps are reset, hence the name backtracking. The goal is to reach a solution step by step. When an error occurs, you try another path to the solution. Thus, potentially all possible (and therefore perhaps also a lot of) ways are followed. However, this also has a disadvantage, namely a rather long running time until the problem is solved.
Solving the n-Queens Problem
Finding a solution to a Sudoku puzzle
Finding a way out of a maze given as a 2D array or nested lists
7.2.1 The n-Queens Problem
Algorithm
You start with a queen in row 0 and position 0 (upper left corner). After each placement, a check is made to ensure that there are no collisions in the vertical and diagonal left and right directions upwards with already placed queens. A check downwards is not necessary because no queens can be placed there yet since the filling is done from top to bottom. This is also the reason why a check in the horizontal direction is not necessary.
Provided the position is valid, move to the next row, trying all positions from 0 to n − 1. This procedure is repeated until you have finally placed the queen in the last row. If there is a problem in positioning a queen, use backtracking: remove the last placed queen and try again at the next possible position. If the end of the row is reached without a solution, this is an invalid situation, and the preceding queen must also be placed again. You can observe that backtracking sometimes goes back up one row, in extreme cases up to the first row.
Notice that you arrive at a solution through a few trial-and-error steps.
In the following, you will now take a rough look at the implementation of the algorithm.
Implementation of backtracking You again subdivide the previously described algorithm for solving the n-Queens Problem into a couple of functions so that one subproblem can be solved at a time.
Additionally, I want to mention how to process modifications in algorithms with backtracking. As one variation (used here), modifications made before the recursion steps are reverted. As a second variation, you can pass copies during the recursion step and perform the modification in the copy. Then no undo or delete is necessary anymore.
What Is Still Missing in the Implementation? What Is the Next Step?
As an exercise in Section 7.3.9 you are left with the task of implementing the is_valid_position(board, col, row) function. This is to check whether a playfield is valid. Due to the chosen algorithm of the line-by-line approach and because only one queen can be placed per line, possible collisions may be excluded only vertically and diagonally.
7.3 Exercises
7.3.1 Exercise 1: Towers of Hanoi (★★★✩✩)
In the Towers of Hanoi problem, there are three towers or sticks named A, B, and C. At the beginning, several perforated discs are placed on stick A in order of size, with the largest at the bottom. The goal is now to move the entire stack (i. e., all the discs) from A to C. The discs must be placed on the top of the stack. The goal is to move one disk at a time and never place a smaller disc below a larger one. That’s why you need the helper stick B. Write function solve_tower_of_hanoi(n) that prints the solution on the console in the form of the movements to be executed.
Example
7.3.2 Exercise 2: Edit Distance (★★★★✩)
Add a character (+),
Delete a character (−), or
Change a character (⤳).
Write function edit_distance(str1, str2) that tries the three actions character by character and checks the other part recursively.
Examples
Input 1 | Input 2 | Result | Actions |
---|---|---|---|
“Micha” | “Michael” | 2 | |
“rapple” | “tables” | 4 |
Bonus (★★★✩✩) Optimize Edit Distance with Memoization
7.3.3 Exercise 3: Longest Common Subsequence (★★★✩✩)
The previous exercise was about how many changes are needed to transform two given strings into each other. Another interesting problem is to find the longest common but not necessarily contiguous sequence of letters in two strings that occurs in two strings in the same sequence. Write function lcs(str1, str2) that recursively processes the strings from the back. In case of two parts of the same length, it uses the second one.
Examples
Input 1 | Input 2 | Result |
---|---|---|
“ABCE” | “ZACEF” | “ACE” |
“ABCXY” | “XYACB” | “AB” |
“ABCMIXCHXAEL” | “MICHAEL” | “MICHAEL” |
“sunday-Morning” | “saturday-Night-Party” | “suday-ig” |
Bonus Use Memoization for Longest Common Subsequence
7.3.4 Exercise 4: Way Out of a Labyrinth (★★★✩✩)
In this assignment, you are asked to find the way out of a maze. Assume a maze is given as a two-dimensional array or nested lists with walls symbolized by # and target positions (exits) symbolized by X. From any position, a path to all exits is supposed to be determined. If there are two exits in a row, only the first of the two has to be supplied. It is only allowed to move in the four compass directions, but not diagonally. Write function find_way_out(values, x, y) that logs each found exit with FOUND EXIT at ....
Example
Based on the output, it is also clear that two of the target fields marked with X are not detected from the start position. One is the X at the very top right corner, which cannot be reached due to a missing link. The other is the lower middle X, which is behind another exit.
7.3.5 Exercise 5: Sudoku Solver (★★★★✩)
Write function solve_sudoku(board) that determines a valid solution, if any, for a partially initialized playfield passed as a parameter.
Example
7.3.6 Exercise 6: Math Operator Checker (★★★★✩)
This assignment is about a mathematically inclined puzzle. For a set of digits and another set of possible operators, you want to find all combinations that result in the desired value. The order of the digits cannot be changed. Still, it is possible to insert any operator from the possible operators between the digits, except before the first digit. Write function all_combinations_with_value(n) that determines all combinations that result in the value passed as parameter. Check this for the digits 1 to 9 and the operations + and −, and combining the digits. Start with function find_all_combinations(values), which is passed the corresponding digits.
Examples
Let’s consider two combinations only for the digits 1, 2, and 3:
1 + 2 + 3 = 6
1 + 23 = 24
Input | Result (all_combinations()) |
---|---|
[1, 2, 3] | {12−3=9, 123=123, 1+2+3=6, 1+2−3=0, 1−2+3=2, 1−23=−22, 1−2−3=−4, 1+23=24, 12+3=15} |
Suppose you wanted to generate the value 100 from the given digits 1 to 9 and the set of available operators (+, −, and combining the digits). This is possible, for example, as follows:
1 + 2 + 3 − 4 + 5 + 6 + 78 + 9 = 100
Input | Result (allCombinationsWithValue()) |
---|---|
100 | [1+23−4+5+6+78−9, 123+4−5+67−89, 123−45−67+89, 12+3−4+5+67+8+9, 1+23−4+56+7+8+9, 12−3−4+5−6+7+89, 123−4−5−6−7+8−9, 1+2+34−5+67−8+9, 12+3+4+5−6−7+89, 123+45−67+8−9, 1+2+3−4+5+6+78+9] |
7.3.7 Exercise 7: Water Jug Problem (★★★✩✩)
Let’s say you have two jugs with capacities of m and n liters. Unfortunately, these jugs have no markings or indications of their fill level. The challenge is to measure x liters, where x is less than m or n. At the end of the procedure, one jug should contain x liters and the other should be empty. Write function solve_water_jugs(size1, size2, desired_liters), which displays the solution on the console. If successful, it returns True, otherwise False.
Examples
State | Action |
---|---|
Jug 1: 0/Jug 2: 0 | Both jugs initial empty |
Jug 1: 4/Jug 2: 0 | Fill jug 1 (unnecessary, but due to the algorithm) |
Jug 1: 4/Jug 2: 3 | Fill jug 2 |
Jug 1: 0/Jug 2: 3 | Empty jug 1 |
Jug 1: 3/Jug 2: 0 | Pour jug 2 into jug 1 |
Jug 1: 3/Jug 2: 3 | Fill jug 2 |
Jug 1: 4/Jug 2: 2 | Pour jug 2 in jug 1 |
Jug 1: 0/Jug 2: 2 | Empty jug 1 |
Solved |
On the other hand, measuring 2 liters is impossible with two jugs of 4 liters capacity each.
7.3.8 Exercise 8: All Palindrome Substrings (★★★★✩)
In this assignment, you want to determine for a given word whether it contains palindromes and, if so, which ones. Write recursive function all_palindrome_parts_rec(input) that determines all palindromes with at least two letters in the passed string and returns them sorted alphabetically.1
Examples
Input | Result |
---|---|
“BCDEDCB” | [“BCDEDCB”, “CDEDC”, “DED” ] |
“ABALOTTOLL” | [“ABA”, “LL”, “LOTTOL”, “OTTO”, “TT”] |
“racecar” | [“aceca”, “cec”, “racecar”] |
Bonus Find the longest of all palindrome substrings. This time there is no requirement for maximum performance.
7.3.9 Exercise 9: The n-Queens Problem (★★★✩✩)
In the n-Queens Problem , n queens are to be placed on an n × n board in such a way that no two queens can beat each other according to chess rules. Thus, other queens must not be placed on the same row, column, or diagonal. To do this, extend the solution shown in Section 7.2.1 and implement function is_valid_position(board, col, row). Also write function print_board(board) to display the board as well as output the solution to the console.
Example
7.4 Solutions
7.4.1 Solution 1: Towers of Hanoi (★★★✩✩)
In the Towers of Hanoi problem, there are three towers or sticks named A, B, and C. At the beginning, several perforated discs are placed on stick A in order of size, with the largest at the bottom. The goal is now to move the entire stack (i. e., all the discs) from A to C. The discs must be placed on the top of the stack. The goal is to move one disk at a time and never place a smaller disc below a larger one. That’s why you need the helper stick B. Write function solve_tower_of_hanoi(n) that prints the solution on the console in the form of the movements to be executed.
Example
- 1.
First, the tower, which is smaller by one slice, is transported from the source to the auxiliary stick.
- 2.
Then, the last and largest slice is moved from the source to the target stick.
- 3.
Finally, the remaining tower must be moved from the auxiliary to the target stick.
Although the problem sounds rather tricky at first, it can be solved quite easily with recursion. This assignment shows again that recursion is useful to reduce the difficulty by decomposing a problem into several smaller subproblems that are not so difficult to solve.
Bonus: Create a Console-Based Graphical Format
Verification
7.4.2 Solution 2: Edit Distance (★★★★✩)
Add a character (+),
Delete a character (−), or
Change a character (~).
Write function edit_distance(str1, str2) that tries the three actions character by character and checks the other part recursively.
Examples
Input 1 | Input 2 | Result | Actions |
---|---|---|---|
“Micha” | “Michael” | 2 | |
“rapple” | “tables” | 4 |
Algorithm Let’s start to consider how you can proceed here. If both strings match, then the edit distance is 0. If one of the two strings contains no (more) characters, then the distance to the other is the number of characters remaining in the other string. This means inserting the corresponding characters several times. This defines the recursive termination.
- 1.
Insert: Recursive call for the next characters
- 2.
Remove: Recursive call for the next characters
- 3.
Replace: Recursive call for the next characters
You examine three possible paths and then calculate the minimum from these three values.
Verification
The running times increase significantly the more the two inputs differ. So how can you make it work better? The solution of the bonus task shows this.
Bonus: Optimize Edit Distance with Memoization (★★★✩✩)
Suppose you perform the same checks as before. Even with the last calculation of the Edit Distance of 16, only a minimum running time of less than one millisecond can be determined.
Using the memoization decorator In Section 7.1.3, you learned how to add memoization by using decorators to recursive functions to optimize running time.
Let’s recap: An initial parameterization is done by the construct with the helper function. For all calls to edit_distance_helper(), the two inputs str1 and str2 remain unchanged. The variance is in the positions. Therefore, in the manual implementation, the key in the dictionary consists only of the positions. However, the universal variant cannot distinguish this and therefore uses a key consisting of all four parameter values.
7.4.3 Solution 3: Longest Common Subsequence (★★★✩✩)
The previous exercise was about how many changes are needed to transform two given strings into each other. Another interesting problem is to find the longest common but not necessarily contiguous sequence of letters in two strings that occurs in two strings in the same sequence. Write function lcs(str1, str2) to recursively process the strings from the back. In case of two parts of the same length, it uses the second one.
Examples
Input 1 | Input 2 | Result |
---|---|---|
“ABCE” | “ZACEF” | “ACE” |
“ABCXY” | “XYACB” | “AB” |
“ABCMIXCHXAEL” | “MICHAEL” | “MICHAEL” |
“sunday-Morning” | “saturday-Night-Party” | “suday-ig” |
Modified algorithm Alternatively, you can run from front to back until the end of the strings is reached. Interestingly, the same results are almost always produced because with the variant from the end, only for the second input combination, you get XY instead of AB as a result.
Verification
In the accompanying project, for the sake of completeness, you also test the variant with the LCS determination from the start (not shown here).
Bonus: Use Memoization for Longest Common Subsequence
7.4.4 Solution 4: Way Out of a Labyrinth (★★★✩✩)
In this assignment, you are asked to find the way out of a maze. Assume a maze is given as a two-dimensional array or nested lists with walls symbolized by # and target positions (exits) symbolized by X. From any position, a path to all exits is supposed to be determined. If there are two exits in a row, only the first of the two has to be supplied. It is only allowed to move in the four compass directions, but not diagonally. Write function find_way_out(values, x, y) that logs each found exit with FOUND EXIT at ....
Example
Based on the outputs, it is also clear that two of the target fields marked with X are not detected from the start position. One is the X at the very top right corner, which cannot be reached due to a missing link. The other is the lower middle X, which is behind another exit.
Note that you use the natural alignment of x and y coordinates in the functions. Still, when accessing the array or nested lists, the order is [y][x] because you are working in rows, as discussed in the introductory section of the chapter on arrays in Section 6.1.2.
Verification
Alternative
The implementation shown nicely prepares the paths to the target fields graphically. However, it has two minor disadvantages. On the one hand, it breaks off directly when an exit is encountered and thus does not find an exit behind it. On the other hand, if there are several paths to a target field, the program also logs the finding of an exit several times. The latter could be solved quite easily by collecting all solution paths in a set.
7.4.5 Solution 5: Sudoku Solver (★★★★✩)
Write function solve_sudoku(board) that determines a valid solution, if any, for a partially initialized playfield passed as a parameter.
Example
Algorithm To solve Sudoku, you use backtracking. As with other backtracking problems, Sudoku can be solved by step-by-step trial and error. In this case, that means trying different numbers for each of the empty squares. According to the Sudoku rules, the current digit must not already exist horizontally, vertically, or in a 3 × 3 block. If you find a valid value assignment, you can continue recursively at the next position to test whether you arrive at a solution. If none is found, then you try the procedure with the next digit. However, if none of the digits from 1 to 9 lead to a solution, you need backtracking to examine other possible paths to the solution.
- 1.
Check if all rows have been processed; then you have a solution.
- 2.
Find the next empty field. To do this, skip all fields that are already filled. This can also change lines.
- 3.
If no empty field exist until the last row, you have found the solution.
- 4.Otherwise you try out the digits from 1 to 9.
- a.
Is there a conflict? Then you have to try the next digit.
- b.
The digit is a possible candidate. You call your function recursively for the following position (next column or even next row).
- c.
If the recursion returns False, this digit does not lead to a solution and you use backtracking.
Looking at this implementation, you might already doubt whether this variant is really optimal, even without knowing the details of the helper functions shown in the following. Why? You keep checking the entire playfield for validity at every step, and even worse, doing that in combination with backtracking! I’ll go into this in more detail later.
Verification
The solution is displayed within a few fractions of a second. So far, everything has worked really well. But what happens if the given playfield contains hardly any digits but lots of empty fields?
In principle, this is already possible with your algorithm, but it takes several minutes. Although this is quite long, you probably couldn’t solve difficult puzzles by hand in this time span—but with the computer, it should be even faster. So what can you improve?
Reasonable Optimizations
This optimization results in running times in the range of a few seconds—between 20 and 50 seconds for complicated playfields. This is already much better, but it can still be much more performant.
You optimized this test twice. First, you changed the initial function is_valid_position(board) to is_valid_position(board, row, col) so that it also gets the row and column as parameters. As a further improvement, you pass the number to be checked is_valid_position(board, row, col, num).
Results of the optimizations made Due to your optimizations—which, by the way, do not lead to any restrictions in readability or comprehensibility—you can save yourself from trying out many solution paths that never lead to the goal. The solutions were always determined in about 1 minute on my iMac (i7 4Ghz), even for more complex playing fields.
The naive way of implementation with the overall check of the board at each step led to running times of more than 20 minutes for more complex boards. While the first optimization finds a solution after about 3.5 minutes, the combination of ideas 2 and 3 leads to a running time of about 1 minute.
7.4.6 Solution 6: Math Operator Checker (★★★★✩)
This assignment is about a mathematically inclined puzzle. For a set of digits and another set of possible operators, you want to find all combinations that result in the desired value. The order of the digits cannot be changed. Still, it is possible to insert any operator from the possible operators between the digits, except before the first digit. Write function all_combinations_with_value(n) that determines all combinations that result in the value passed as parameter. Check it for the digits 1 to 9 and the operations +, −, and combining the digits. Start with function find_all_combinations(values) which is passed the corresponding digits.
Examples
Let’s consider two combinations only for the digits 1, 2, and 3:
1 + 2 + 3 = 6
1 + 23 = 24
Input | Result (all_combinations()) |
---|---|
[1, 2, 3] | {12−3=9, 123=123, 1+2+3=6, 1+2−3=0, 1−2+3=2, 1−23=−22, 1−2−3=−4, 1+23=24, 12+3=15} |
Suppose you want to generate the value 100 from the given digits 1 to 9 and the set of available operators (+, −, and combining the digits). This is possible, for example, as follows:
1 + 2 + 3 − 4 + 5 + 6 + 78 + 9 = 100
Input | Result (allCombinationsWithValue()) |
---|---|
100 | [1+23−4+5+6+78−9, 123+4−5+67−89, 123−45−67+89, 12+3−4+5+67+8+9, 1+23−4+56+7+8+9, 12−3−4+5−6+7+89, 123−4−5−6−7+8−9, 1+2+34−5+67−8+9, 12+3+4+5−6−7+89, 123+45−67+8−9, 1+2+3−4+5+6+78+9] |
Verification
7.4.7 Solution 7: Water Jug Problem (★★★✩✩)
Say you have two jugs with capacities of m and n liters. Unfortunately, these jugs have no markings or indications of their fill level. The challenge is to measure x liters, where x is less than m or n. At the end of the procedure, one jug should contain x liters and the other should be empty. Write function solve_water_jugs(size1, size2, desired_liters) to display the solution on the console and, if successful, return True, otherwise False.
Examples
State | Action |
---|---|
Jug 1: 0/Jug 2: 0 | Both jugs initial empty |
Jug 1: 4/Jug 2: 0 | Fill jug 1 (unnecessary, but due to the algorithm) |
Jug 1: 4/Jug 2: 3 | Fill jug 2 |
Jug 1: 0/Jug 2: 3 | Empty jug 1 |
Jug 1: 3/Jug 2: 0 | Pour jug 2 into jug 1 |
Jug 1: 3/Jug 2: 3 | Fill jug 2 |
Jug 1: 4/Jug 2: 2 | Pour jug 2 in jug 1 |
Jug 1: 0/Jug 2: 2 | Empty jug 1 |
Solved |
On the other hand, measuring 2 liters is impossible with two jugs of 4 liters capacity each.
Empty jug 1 completely.
Empty jug 2 completely.
Fill jug 1 completely.
Fill jug 2 completely.
Fill jug 1 from jug 2 until the source jug is empty or the jug to be filled is full.
Fill jug 2 from jug 1 until the source jug is empty or the jug to be filled is full.
Verification
7.4.8 Exercise 8: All Palindrome Substrings (★★★★✩)
In this assignment, you want to determine for a given word whether it contains palindromes and, if so, which ones. Write recursive function all_palindrome_parts_rec(input) that determines all palindromes with at least two letters in the passed string and returns them sorted alphabetically.2
Examples
Input | Result |
---|---|
“BCDEDCB” | [“BCDEDCB”, “CDEDC”, “DED” ] |
“ABALOTTOLL” | [“ABA”, “LL”, “LOTTOL”, “OTTO”, “TT”] |
“racecar” | [“aceca”, “cec”, “racecar”] |
- 1.
Is the entire text a palindrome?
- 2.
Is the part shortened on the left a palindrome (for all positions from the right)?
- 3.
Is the right-shortened part a palindrome (for all positions from the left)?
As previously applied several times, a two-step variant is used here. In this case, the first method primarily initializes the result object and then starts the recursive call appropriately.
Although the algorithm is quite comprehensible, it seems rather awkward with all the loops and index accesses. In fact, an exquisite solution exists.
Verification
Bonus: Find the Longest of All Palindrome Substrings
This time there is no requirement for maximum performance.
Verification
7.4.9 Solution 9: The n-Queens Problem (★★★✩✩)
In the n-Queens Problem, n queens are to be placed on an n × n board in such a way that no two queens can beat each other according to chess rules—thus, other queens must not be placed in the same row, column, or diagonal. To do this, extend the solution shown in Section 7.2.1 and implement the function is_valid_position(board, col, row). Also write function print_board(board) to display the board as well as output the solution to the console.
Example
Algorithm Let’s recall and repeat the algorithm presented in the introduction.
You attempt to place the queens one after the other at different positions. You start with a queen in row 0 and position 0 (upper left corner). After each placement, a check is made to ensure that there are no collisions in the vertical and diagonal left and right directions upwards with queens that have already been placed. A check downwards is logically not necessary in any case because no queens can be placed there yet. After all, the filling is done from top to bottom. Since you also proceed line by line, a check in the horizontal direction is unnecessary.
Provided the position is valid, move to the next row, trying all positions from 0 to n − 1. This procedure is repeated until you have finally placed the queen in the last row. If there is a problem positioning a queen, use backtracking: remove the last-placed queen and try again at the next possible position. If the end of the row is reached without a solution, this is an invalid situation, and the previous queen must also be placed again. You can see that backtracking sometimes goes back up one row, in extreme cases to the first row.
Actually, the horizontal check is superfluous since you are just checking a new row where no other queen can be placed yet—for the sake of illustration, you implement and call the function anyway.
Verification
Alternative Solution Approach
Although the previously chosen representation as a two-dimensional array (or more precisely as two-dimensional nested lists) is absolutely catchy, there is an optimization. Because only one queen may be placed per row, it is possible to use a list for modeling the playfield and the queens’ positioning, which simplifies a lot. Sounds strange at first. How is it supposed to work?
For the solution of the n-Queens Problem, you need in each case x- and y- coordinates. You reconstruct them by the following trick: The y-coordinate results from the position in the list. For the x-coordinate, you store a corresponding numerical value in the list. The presence of a queen, previously indicated by the character Q, can now be determined indirectly. If the list contains a numerical value greater than or equal to 0 at the position of the y-coordinate, then a queen is present.
Verification
The results are identical to the previous ones and are therefore not shown again.
7.5 Summary: What You Learned
Basic recursion is a very nice technique. When using it a bit more intensively, you see that simple recursion, besides the advantages, sometimes requires some patience due to long running times.
In this advanced chapter on recursion, you have significantly expanded your toolbox with memoization and backtracking. Memoization allows you to increase performance, and backtracking helps solve entertaining and amusing puzzles, such as Sudoku puzzles or the n-Queens problem. It is also possible to find a way out of a maze.
Now that you are fluent in recursion, you are well prepared to expand and use your knowledge for various algorithms on trees, which are special, very helpful, and exciting data structures suitable for various kinds of challenges. Let’s get in touch.