Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

7. Advanced Recursion

Michael Inden¹

(1)

Zurich, Switzerland

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.

Let’s briefly repeat the recursive definition of Fibonacci numbers:

$fib(n)=left{egin{array}{cc}1,kern14em & n=1\ {}1,kern14em & n=2\ {} fibleft(n-1 ight)+ fibleft(n-2 ight),& forall n>2end{array} ight.$

The recursive implementation in Python follows the mathematical definition exactly:

def fib_rec(n):

if n <= 0:

raise ValueError("n must be >= 1")

# recursive termination

if n == 1 or n == 2:

return 1

# recursive descent

return fib_rec(n - 1) + fib_rec(n - 2)

So how do you add memoization? In fact, it is not too difficult. You need a helper function that calls the actual calculation function, and most importantly, a data structure to store intermediate results. In this case, you use a dictionary that is passed to the computation function.

def fibonacci_optimized(n):

return fibonacci_memo(n, {})

In the original function, you surround the actual computation with the actions for memoization. For every computation step, you first look in the dictionary to see if a suitable result already exists and return it if it does. Otherwise, you execute the algorithm as before, with the minimal modification that you store the computation result in a variable, to be able to deposit it at the end suitably in the lookup dictionary.

def fibonacci_memo(n, lookup_map):

if n <= 0:

raise ValueError("n must be > 0")

# MEMOIZATION: check if there is a suitable pre-calculated result

if n in lookup_map:

return lookup_map.get(n)

# normal algorithm with helper variable for storing the result

result = 0

if n == 1 or n == 2:

# recursive termination

result = 1

else:

# recursive descent

result = fibonacci_memo(n - 1, lookup_map) +

fibonacci_memo(n - 2, lookup_map)

# MEMOIZATION: store calculated result

lookup_map[n] = result

return result

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.

Notes

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.

Furthermore, there are the following points to consider:

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:

Let’s first look at the purely recursive implementation again:

def pascal_rec(row, col):

# recursive termination: top

if col == 1 and row == 1:

return 1

# recursive termination: borders

if col == 1 or col == row:

return 1

# recursive descent

return pascal_rec(row - 1, col) + pascal_rec(row - 1, col - 1)

For the computation of Pascal’s triangle by using memoization, the original algorithm hardly changes. You merely surround it with the accesses to the lookup dictionary and the storage:

def pascal_optimized(row, col):

return calc_pascal_memo(row, col, {})

def calc_pascal_memo(row, col, lookup_map):

# MEMOIZATION

key = (row, col)

if key in lookup_map:

return lookup_map[key]

result = 0

# recursive termination: top

if col == 1 and row == 1:

return 1

# recursive termination: borders

if col == 1 or col == row:

return 1

else:

# recursive descent

result = calc_pascal_memo(row - 1, col, lookup_map) +

calc_pascal_memo(row - 1, col - 1, lookup_map)

# MEMOIZATION

lookup_map[key] = result

return result

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.

NOTE: BACKGROUND KNOWLEDGE ON MEMOIZATION

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

You know that memoization leads to a vast speedup of recursive computations. When implemented directly according to the purely recursive definition, there is exponential growth for the Fibonacci numbers in running time. In combination with the implementation of memoization, you can achieve enormous speed gains. For this purpose, data from previous calculations are cached, and each call is first checked to see if a result is already available. You use a dictionary to store the data. The explicit wrapping and subsequent calling of the actual functionality can be programmed by hand. However, the whole thing has the following (cosmetic) disadvantages:

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.

Python permits memoization to be implemented with less effort and in a standardized way. You will briefly look at the following techniques:

Memoization using a decorator
Built-in memoization with lru_cache from the module functools

The nice thing about these variants is that to implement memoization, you don’t mix the application code with the source code. Better yet, this allows you to provide memoization as a cross-cutting concern. The prerequisite is an import as follows:

import functools

Memoization with a Decorator

As for the manual implementation, you again use an additional function, here decorate_with_memo(func), which defines a data store. In contrast to the manual implementation, a helper function helper implements the memoization here. For this purpose, a function is returned, which is identical to the function func but enriched with memoization, or more precisely, which retrieves or stores its results in the dictionary. Here is a variant that is closer to the completely manual implementation as well as a slightly modified one where memoization is less visible.

# hand knitted

def decorate_with_memo(func):

lookup_map = dict()

@functools.wraps(func)

def helper(n):

# MEMOIZATION: check if precalculated result exists

if n in lookup_map:

return lookup_map[n]

result = func(n)

# MEMOIZATION: store calculated result

lookup_map[n] = result

return result

return helper

# memoization not so obvious

def decorate_with_memo_shorter_one_param(func):

lookup_map = dict()

@functools.wraps(func)

def helper(n):

if n not in lookup_map:

lookup_map[n] = func(n)

return lookup_map[n]

return helper

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.

NOTE: USABLE TYPES

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.

With the knowledge gained, you can implement the memoization-optimized version as follows—the source code reflects the mathematical (recursive) definition. The cross-cutting concern of parameter checking and memoization are implemented separately as independent decorators.

@check_argument_is_positive_integer

@decorate_with_memo_shorter_one_param

def fib_rec(n):

# recursive termination

if n == 1 or n == 2:

return 1

# recursive descent

return fib_rec(n - 1) + fib_rec(n - 2)

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?

It would be awkward and time-consuming to define a decorator with a suitable number of parameters each time. Conveniently, in Python, parameters can be evaluated and passed as tuples. Thus, you can implement the decorator in a general manner with the parameters (*args) as follows:

def decorate_with_memo_shorter(func):

lookup_map = dict()

@functools.wraps(func)

def helper(*args):

if args not in lookup_map:

lookup_map[args] = func(*args)

return lookup_map[args]

return helper

Let’s take a quick look at the usage for Pascal’s triangle:

@decorate_with_memo_shorter

def pascal_rec(row, col):

# recursive termination: top

if col == 1 and row == 1:

return 1

# recursive termination: borders

if col == 1 or col == row:

return 1

# recursive descent

return pascal_rec(row - 1, col) + pascal_rec(row - 1, col - 1)

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.

LRU cache for Fibonacci numbers As usual, you use the calculation of Fibonacci numbers as an example. They are also used in the description of the module functools online (https://docs.python.org/3/library/functools.html), here minimally adapted. By marking a function with @lru_cache, the caching of previous calculation results can be activated. Here the number may be limited by the argument maxsize. By default, the value is 128. Specifying None makes the size unlimited but also disables the LRU functionality.

>>> @functools.lru_cache(maxsize=None)

... @check_argument_is_positive_integer

... def fib_rec(n):

... if n == 1 or n == 2:

... return 1

...

... return fib_rec(n-1) + fib_rec(n-2)

Let’s try a few things. With cache_info() it is possible to output information about the cache. This is done before calling the function and after the calculation.

>>> fib.cache_info()

CacheInfo(hits=0, misses=0, maxsize=None, currsize=0)

>>> [fib(n) for n in range(1, 19)]

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]

>>> fib.cache_info()

CacheInfo(hits=32, misses=18, maxsize=None, currsize=18)

LRU cache for Pascal’s triangle Memoization can also be added to Pascal’s triangle calculation very easily as follows:

@functools.lru_cache(maxsize=None)

def pascal_rec(row, col):

# recursive termination: top

if col == 1 and row == 1:

return 1

# recursive termination: borders

if col == 1 or col == row:

return 1

# recursive descent

return pascal_rec(row - 1, col) + pascal_rec(row - 1, col - 1)

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.

To keep the implementation manageable, backtracking is often used in combination with recursion for the following problems:

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

The n-Queens Problem is a puzzle to be solved on an n × n board. Queens (from the chess game) must be placed so that no two queens can beat each other according to the chess rules. Thus, other queens may not be placed on the same row, column, or diagonals. As an example, here is the solution for a 4 × 4 board, where the queens are symbolized by a Q (for queen):

---------

| |Q| | |

---------

| | | |Q|

---------

|Q| | | |

---------

| | |Q| |

---------

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.

Backtracking by example Let’s look at the steps to the solution, where on the horizontal level, some intermediate steps are partly omitted and invalid positions are marked with x:

--------------- --------------- ---------------

Q | | | Q | | | Q | | |

--------------- --------------- ---------------

| | | x | x | Q | | | Q |

--------------- => --------------- => ---------------

| | | | | | x | x | x | x

--------------- --------------- ---------------

| | | | | | | | |

--------------- --------------- ---------------

=> Backtracking

No correct placement of a queen in the second row can be found with a queen in the first row and second position. So, a solution is tried at the following position in the first row like so:

--------------- --------------- ---------------

Q | | | Q | | | Q | | |

--------------- --------------- ---------------

x | x | x | Q | | | Q | | | Q

--------------- => --------------- => ---------------

| | | x | Q | | | Q | |

--------------- --------------- ---------------

| | | | | | x | x | x | x

--------------- --------------- ---------------

=> Backtracking

Even with the queen in the third position in the first row, no valid position for a queen in the second row can be found. So, you have to go back not only one row but two rows and start the search again with the queen in row zero in position one:

--------------- --------------- --------------- ---------------

| Q | | | Q | | | Q | | | Q | |

--------------- --------------- --------------- ---------------

x | x | x | Q | | | Q | | | Q | | | Q

--------------- => --------------- => --------------- => ---------------

| | | | | | Q | | | Q | | |

--------------- --------------- --------------- ---------------

| | | | | | | | | x | x | Q |

--------------- --------------- --------------- ---------------

=> Solution found

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.

First, think about how you want to model the playfield. A list of lists as a two-dimensional data model offers itself formally. Here, a Q represents a queen, and a blank means an empty board. To initially create a blank board, write function initialize_board(). Then you call the actual recursive backtracking function solve_n_queens(), which determines the solution inplace on the data model. If one is found, the helper function returns True, otherwise False. To allow callers to evaluate easily, you return a tuple with a solution flag and the playfield.

def solve_n_queens(size):

board = initialize_board(size)

# Start the recursive solution finding

solved = solve_n_queens_helper(board, 0)

return solved, board # (solved, board)

def initialize_board(size):

return [[' ' for col in range(size)] for row in range(size)]

Now let’s get back to the main task of finding a solution using recursion and backtracking. As described, the algorithm proceeds row by row and then tries the respective columns.

def solve_n_queens_helper(board, row):

max_row, max_col = get_dimension(board)

# recursive termination

if row >= max_row:

return True

solved = False

col = 0

while col < max_col and not solved:

if is_valid_position((board, col, row):

place_queen(board, col, row)

# recursive descent

solved = __solve_n_queens_helper(board, row + 1)

# Backtracking, if no solution found

if not solved:

remove_queen(board, col, row)

col += 1

return solved

To keep the algorithm as free of details and list accesses as possible as well as thereby understandable, you define two helper functions place_queen() und remove_queen().

def place_queen(board, col, row):

board[row][col] = 'Q'

def remove_queen(board, col, row):

board[row][col] = ' '

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.

For the sake of completeness, the implementation of the initialization of the playfield is shown here:

def get_dimension(values2dim):

if (isinstance(values2dim, list)):

return (len(values2dim), len(values2dim[0]))

if (isinstance(values2dim, np.ndarray)):

return values2dim.shape

raise Exception("unsupported type", type(values2dim)) '

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

The whole thing looks something like Figure 7-1.

Figure 7-1
Task definition for the Towers of Hanoi problem

The following solution should be provided for three slices:

Tower Of Hanoi 3

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

Bonus Create a console-based graphical format. For two slices, this would look something like this:

Tower Of Hanoi 2

A B C

| | |

#|# | |

##|## | |

------- ------- -------

Moving slice: 1 : Tower [A] -> Tower [B]

A B C

| | |

##|## #|# |

------- ------- -------

Moving slice: 2 : Tower [A] -> Tower [C]

A B C

| | |

| #|# ##|##

------- ------- -------

Moving slice: 1 : Tower [B] -> Tower [C]

A B C

| | |

| | #|#

| | ##|##

------- ------- -------

7.3.2 Exercise 2: Edit Distance (★★★★✩)

For two strings, compute how many changes they are—case-insensitive—apart; that is, how to transition one string to the other by applying any of the following actions one or more times:

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

The following modifications are required for the inputs shown:

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

A larger playfield with four target fields is shown below. The bottom figure shows each of the paths indicated by a dot (.). In between you see the logging of the found positions of the exits. For this example, the search starts from the upper left corner with coordinates x=1, y=1.ons of the exits. The search starts from the upper left corner with coordinates x=1, y=1.

##################################

# # # # # # X#X#

# ##### #### ## ## # # ### #

# ## # # ## ## # # # #

# # ### # ## ## # ### # #

# # #### ## ## ### # #

#### # #### # # #### #

###### ######### ## # ### #

## # X X####X # # # ### ##

##################################

FOUND EXIT: x: 30, y: 1

FOUND EXIT: x: 17, y: 8

FOUND EXIT: x: 10, y: 8

##################################

#.# #....#.....# #...X#X#

#..##### ####.##...##..# #.### #

# .## # #..## ## .# #.. # #

# ...# ###..#.## ## ..#...### # #

# # ..####.....## ##.... ### # #

#### ..#... #### ....# # #### #

######...#########...## # ### #

## #..X X####X.# # # ### ##

##################################

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

A valid playfield with some blanks is shown here:

This should be completed to the following solution:

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

In total, these digits allow the following different combinations to be formed:

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

In total, the following variants should be determined:

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

For two jugs, one with a capacity of 4 liters and one with a capacity of 3 liters, you can measure 2 liters in the following way:

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.¹

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

For a 4 × 4 playfield, there is the following solution, with the queens symbolized by a Q.

---------

| |Q| | |

---------

| | | |Q|

---------

|Q| | | |

---------

| | |Q| |

---------

7.4 Solutions

7.4.1 Solution 1: Towers of Hanoi (★★★✩✩)

Example

The whole thing looks something like Figure 7-2.

Figure 7-2
Task definition for the Towers of Hanoi problem

The following solution should be provided for three slices:

Tower Of Hanoi 3

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

Algorithm The movement of the disks is implemented in function move_tower(n, source, helper, destination), which gets the number of slices to be moved, the initial source stick, the auxiliary stick, and the target stick. Initially you use n and ‘A’, ‘B ‘, and ‘C’ as initial parameters. The function move_tower() splits the problem into three smaller problems:

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.

The action move source to target serves as a recursive termination when the height is 1. It gets a little tricky by swapping the source, target, and auxiliary stick during the actions.

def move_tower(n, source, helper, destination):

if n == 1:

print(source + " -> " + destination)

else:

# move all but last slice from source to auxiliary stick

# destination thus becomes the new auxiliary stick

move_tower(n - 1, source, destination, helper)

# move the largest slice from source to target

print(source + " -> " + destination)

# move_tower(1, source, helper, destination); // unverständlicher

# move tower reduced by one from auxiliary staff to target

move_tower(n - 1, helper, source, destination)

In order to show fewer details, it is advisable to use the definition of the following function:

def solve_tower_of_hanoi(n):

print("Tower Of Hanoi", n)

move_tower(n, 'A', 'B', 'C')

To solve the problem, the function must be called with the desired number of slices, like this:

>>> solve_tower_of_hanoi(3)

Tower Of Hanoi 3

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C

HINT: RECURSION AS A TOOL

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

For two slices, this would look something like this:

Tower Of Hanoi 2

A B C

| | |

#|# | |

##|## | |

------- ------- -------

Moving slice: 1 : Tower [A] -> Tower [B]

A B C

| | |

##|## #|# |

------- ------- -------

Moving slice: 2 : Tower [A] -> Tower [C]

A B C

| | |

| #|# ##|##

------- ------- -------

Moving slice: 1 : Tower [B] -> Tower [C]

A B C

| | |

| | #|#

| | ##|##

------- ------- -------

First, let’s look at how the graphical output algorithm changes. This part for finding the solution remains absolutely the same. You just add class Tower to your implementation and an action that you pass as a lambda expression when solving. You modify the function solve_tower_of_hanoi(n) in such a way that three Tower objects are created there, and the desired number of disks is placed on the output tower accordingly.

def solve_tower_of_hanoi_v2(n):

print("Tower Of Hanoi", n)

source = Tower("A")

helper = Tower("B")

destination = Tower("C")

# Attention: reverse order: largest slice first

for i in range(n, 0, -1):

source.push(i)

action = lambda: print_towers(n + 1, source, helper, destination)

action()

move_tower_v2(n, source, helper, destination, action)

The realization of move_tower_v2() only gets an action as another parameter. This allows an action to be executed at the recursive termination.

def move_tower_v2(n, source, helper, destination, action):

if n == 1:

elem_to_move = source.pop()

destination.push(elem_to_move)

print("Moving slice:", elem_to_move, ":", source, "->", destination)

action()

else:

move_tower_v2(n - 1, source, destination, helper, action)

move_tower_v2(1, source, helper, destination, action)

move_tower_v2(n - 1, helper, source, destination, action)

The class Tower Let’s set about creating the Tower class, which uses a string for identification and a Stack to store the slices:

class Tower:

def __init__(self, name):

self.name = name

self.__values = Stack()

def __str__(self):

return "Tower [" + self.name + "]"

def push(self, item):

self.__values.push(item)

def pop(self):

return self.__values.pop()

Additions in the class Stack You can reuse the class Stack built in Section 5.3.2, but you still have to add two functions:

def size(self):

return len(self.__values)

def get_at(self, pos):

return self.__values[pos]

Console output of towers In Chapter 4 on strings, you learned about a first variant for drawing towers in Section 4.2.16 in Exercise 16. Taking advantage of the knowledge gained there, you modify the implementation appropriately. First, you draw the top part of the tower with draw_top(). Then you draw the slices with draw_slices() and finally a bottom boundary line with draw_bottom().

def print_tower(self, max_height):

height = self.values.size() - 1

visual = self.draw_top(max_height, height)

visual += self.draw_slices(max_height, height)

visual += self.draw_bottom(max_height)

return visual

def draw_top(self, max_height, height):

visual = [" " * max_height + self.name + " " * max_height]

for i in range(max_height - height - 1, 0, -1):

visual.append(" " * max_height + "|" + " " * max_height)

return visual

def draw_slices(self, max_height, height):

visual = []

for i in range(height, -1, -1):

value = self.values.get_at(i)

padding = max_height - value

visual.append(" " * padding + "#" * value + "|" +

"#" * value + " " * padding)

return visual

def draw_bottom(self, height):

return ["-" * (height * 2 + 1)]

Output all towers Finally, you combine the output functionality in the following function to print the towers represented as three lists side by side:

def print_towers(max_height, source, helper, destination):

tower1 = source.print_tower(max_height)

tower2 = helper.print_tower(max_height)

tower3 = destination.print_tower(max_height)

for (a,b,c) in zip(tower1, tower2, tower3):

print(a + " " + b + " " + c)

Verification

For testing, invoke the function. The output shows the correct operation:

>>> solve_tower_of_hanoi_v2(2)

Tower Of Hanoi 2

A B C

| | |

#|# | |

##|## | |

------- ------- -------

Moving slice: 1: Tower [A] -> Tower [B]

A B C

| | |

##|## #|# |

------- ------- -------

Moving slice: 2: Tower [A] -> Tower [C]

A B C

| | |

| #|# ##|##

------- ------- -------

Moving slice: 1: Tower [B] -> Tower [C]

A B C

| | |

| | #|#

| | ##|##

------- ------- -------

7.4.2 Solution 2: Edit Distance (★★★★✩)

For two strings, compute how many changes they are—case-insensitive—apart; that is, how to transition one string to the other by applying any of the following actions one or more times:

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

The following modifications are required for the inputs shown:

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.

Otherwise, you check both strings from their beginning and compare them character by character. If they are the same, you go one position further towards the end of the string. If they are different, you check three different modifications:

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.

Here’s how you implement this:

def edit_distance(str1, str2):

return __edit_distance_helper(str1.lower(), str2.lower(),

len(str1) - 1, len(str2) - 1)

def __edit_distance_helper(str1, str2, pos1, pos2):

# recursive termination

# if one of the strings is at the beginning and the other is

# not yet, then take the length of the remaining string

if pos1 < 0:

return pos2 + 1

if pos2 < 0:

return pos1 + 1

# check if the characters match and then advance to the next one

if str1[pos1] == str2[pos2]:

# recursive descent

return __edit_distance_helper(str1, str2, pos1 - 1, pos2 - 1)

else:

# recursive descent: check for insert, delete, change

insert_in_first = __edit_distance_helper(str1, str2, pos1, pos2 - 1)

delete_in_first = __edit_distance_helper(str1, str2, pos1 - 1, pos2)

change = __edit_distance_helper(str1, str2, pos1 - 1, pos2 - 1)

# minimum from all three variants + 1

return 1 + min(insert_in_first, delete_in_first, change)

Verification

For testing, you use the following inputs, which show the correct functionality:

@pytest.mark.parametrize("value1, value2, expected",

[("Micha", "Michael", 2),

("rapple", "tables", 4)])

def test_edit_distance(value1, value2, expected):

result = edit_distance(value1, value2)

assert result == expected

Performance Test You also want to check the performance—because it is only a rough classification that matters, no sophisticated profiling is needed here, but the accuracy of time.process_time() is sufficient:

def main():

inputs_tuples = [["Micha", "Michael"],

["rapple", "tables"],

["sunday-Morning", "saturday-Night"],

["sunday-Morning-Breakfast", "saturday-Night-Party"]]

for inputs in inputs_tuples:

start = time.process_time()

result = edit_distance(inputs[0], inputs[1])

end = time.process_time()

print(inputs[0] + " -> " + inputs[1] + " edits:", result)

print("editDistance() took %.2f ms" % ((end - start) * 1000))

If you run the above lines with (a lot of) patience, you get approximately the following output. In fact, I stopped the last calculation after a few minutes, which is why it is not shown here.

Micha -> Michael edits: 2

editDistance() took 0.26 ms

rapple -> tables edits: 4

editDistance() took 0.35 ms

sunday-Morning -> saturday-Night edits: 10

editDistance() took 137443.89 ms

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 (★★★✩✩)

At the beginning of the chapter, I described memoization as a technique and mentioned that one often uses a dictionary as a cache—so also here:

def edit_distance_optimized(str1, str2):

return __edit_distance_memo(str1.lower(), str2.lower(),

len(str1) - 1, len(str2) - 1, {})

def __edit_distance_memo(str1, str2, pos1, pos2, values):

# recursive termination

# if one of the strings is at the beginning and the other one

# not yet, then take the length of the remaining string

if pos1 < 0:

return pos2 + 1

if pos2 < 0:

return pos1 + 1

# MEMOIZATION

if (pos1, pos2) in values:

return values.get((pos1, pos2))

result = 0

# check if the characters match and then advance to the next one

if str1[pos1] == str2[pos2]:

# recursive descent

result = __edit_distance_memo(str1, str2, pos1 - 1, pos2 - 1, values)

else:

# recursive descent: check for insert, delete, change

insert = __edit_distance_memo(str1, str2, pos1, pos2 - 1, values)

delete = __edit_distance_memo(str1, str2, pos1 - 1, pos2, values)

change = __edit_distance_memo(str1, str2, pos1 - 1, pos2 - 1, values)

# minimum from all three variants + 1

result = 1 + min(insert_in_first, delete_in_first, change)

# MEMOIZATION

values[(pos1, pos2)] = result

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.

For both the calculation of Fibonacci numbers and Pascal’s triangle, it felt natural to annotate the decorator directly to the function calling itself. However, for Edit Distance, you have to think a bit. Here you have a two-step procedure, and it is not the initial function that must be annotated, but the one that performs the actual calculation.

# @decorate_with_memo_shorter

def edit_distance(str1, str2):

return __edit_distance_helper(str1.lower(), str2.lower(),

len(str1) - 1, len(str2) - 1)

@decorate_with_memo_shorter

def __edit_distance_helper(str1, str2, pos1, pos2):

....

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”

Algorithm You move from the back to the front. If the characters match, the character is included in the result. If the characters differ, the check has to be repeated recursively for the strings shortened by one character.

def lcs(str1, str2):

return __lcs_helper(str1, str2, len(str1) - 1, len(str2) - 1)

def __lcs_helper(str1, str2, pos1, pos2):

# recursive termination

if pos1 < 0 or pos2 < 0:

return ""

# are the characters the same?

if str1[pos1] == str2[pos2]:

# recursive descent

return __lcs_helper(str1, str2, pos1 - 1, pos2 - 1) + str1[pos1]

else:

# otherwise take away one of both letters and try it

# again, but neither letter belongs in the result

lcs1 = __lcs_helper(str1, str2, pos1, pos2 - 1)

lcs2 = __lcs_helper(str1, str2, pos1 - 1, pos2)

return lcs1 if len(lcs1) > len(lcs2) else lcs2

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.

In this variant, if the letters are the same, you have to add them in front. In addition, the skipping of non-matching characters must now be simulated by increasing the respective position. All in all, the implementation changes as follows:

def lcs_from_start(str1, str2):

return __lcs__from_start_helper(str1, str2, 0, 0)

def __lcs__from_start_helper(str1, str2, pos1, pos2):

# recursive termination: one input is a the end

if pos1 >= len(str1) or pos2 >= len(str2):

return ""

# are both character the same?

if str1[pos1] == str2[pos2]:

# recursive descent

return str1[pos1] +

__lcs__from_start_helper(str1, str2, pos1 + 1, pos2 + 1)

else:

# otherwise take away one of both letters and try it

# again, but neither letter belongs in the result

lcs1 = __lcs__from_start_helper(str1, str2, pos1, pos2 + 1)

lcs2 = __lcs__from_start_helper(str1, str2, pos1 + 1, pos2)

return lcs1 if len(lcs1) > len(lcs2) else lcs2

Verification

For testing, you use the following inputs, which show the correct operation:

@pytest.mark.parametrize("value1, value2, expected",

[("ABCE", "ZACEF", "ACE"),

("ABCXY", "XYACB", "AB"),

("ABCMIXCHXAEL", "MICHAEL", "MICHAEL")])

def test_lcs(value1, value2, expected):

result = lcs(value1, value2)

assert result == expected

In the accompanying project, for the sake of completeness, you also test the variant with the LCS determination from the start (not shown here).

Performance test Again, you want to look at the performance. Here it is also true that time.process_time() is sufficient for classification.

def main():

inputs_tuples = [["ABCMIXCHXAEL", "MICHAEL"],

["sunday-Morning", "saturday-Night-Party"],

["sunday-Morning-Wakeup", "saturday-Night"]]

for inputs in inputs_tuples:

start = time.process_time()

result = lcs(inputs[0], inputs[1])

end = time.process_time()

print(inputs[0] + " -> " + inputs[1] + " lcs:", result)

print("lcs() took %.2f ms" % ((end - start) * 1000))

Measure the following execution times (they will vary slightly for you):

ABCMIXCHXAEL -> MICHAEL lcs: MICHAEL

lcs() took 0.03 ms

sunday-Morning -> saturday-Night-Party lcs: suday-ig

lcs() took 141523.38 ms

sunday-Morning-Wakeup -> saturday-Night lcs: suday-ig

lcs() took 280070.26 ms

Bonus: Use Memoization for Longest Common Subsequence

This results in long running times for more significant differences in the two inputs since many possible subsequences exist. Therefore, pure recursion is not performant. So how do you do it better? Again, you use memoization for performance optimization. This time you use two-dimensional nested lists of strings for data storage.

def lcs_optimized(str1, str2):

values = [[None for _ in range(len(str2))] for _ in range(len(str1))]

return __lcs_with_memo(str1, str2, len(str1) - 1, len(str2) - 1, values)

The actual implementation uses memoization as follows:

def __lcs_with_memo(str1, str2, pos1, pos2, values):

# recursive termination

if pos1 < 0 or pos2 < 0:

return ""

# MEMOIZATION

if values[pos1][pos2] is not None:

return values[pos1][pos2]

lcs = ""

# are the characters the same?

if str1[pos1] == str2[pos2]:

# recursive descent

lcs = __lcs_with_memo(str1, str2, pos1 - 1, pos2 - 1, values) +

str1[pos1]

else:

# otherwise take away one of both letters and try it

# again, but neither letter belongs in the result

lcs1 = __lcs_with_memo(str1, str2, pos1, pos2 - 1, values)

lcs2 = __lcs_with_memo(str1, str2, pos1 - 1, pos2, values)

lcs = lcs1 if len(lcs1) > len(lcs2) else lcs2

# MEMOIZATION

values[pos1][pos2] = lcs

return lcs

With this optimization, the running times can be reduced to a few milliseconds. For evaluation, start the module EX03_LCS_TIMING_MEMO.PY and compare your execution times with these values:

ABCMIXCHXAEL -> MICHAEL lcs: MICHAEL

lcs_optimized() took 0.03 ms

sunday-Morning -> saturday-Night-Party lcs: suday-ig

lcs_optimized() took 0.21 ms

sunday-Morning-Wakeup -> saturday-Night lcs: suday-ig

lcs_optimized() took 0.31 ms

Use of the memoization decorator As already described for Edit Distance, the two-step procedure of LCS requires you to annotate not the initial function but the one that performs the actual computation:

# @decorate_with_memo_shorter

def lcs(str1, str2):

return __lcs_helper(str1, str2, len(str1) - 1, len(str2) - 1)

@decorate_with_memo_shorter

def __lcs_helper(str1, str2, pos1, pos2):

....

7.4.4 Solution 4: Way Out of a Labyrinth (★★★✩✩)

Example

A larger playfield with four target fields is shown below. The bottom part shows each of the paths indicated by a dot (.). In between you see the logging of the found positions of the exits. For this example, the search starts from the upper left corner with coordinates x=1, y=1.

##################################

# # # # # # X#X#

# ##### #### ## ## # # ### #

# ## # # ## ## # # # #

# # ### # ## ## # ### # #

# # #### ## ## ### # #

#### # #### # # #### #

###### ######### ## # ### #

## # X X####X # # # ### ##

##################################

FOUND EXIT: x: 30, y: 1

FOUND EXIT: x: 17, y: 8

FOUND EXIT: x: 10, y: 8

##################################

#.# #....#.....# #...X#X#

#..##### ####.##...##..# #.### #

# .## # #..## ## .# #.. # #

# ...# ###..#.## ## ..#...### # #

# # ..####.....## ##.... ### # #

#### ..#... #### ....# # #### #

######...#########...## # ### #

## #..X X####X.# # # ### ##

##################################

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.

Algorithm The algorithm for finding a way out of a labyrinth checks whether there is a way in the four compass directions, starting from the current position. To do this, neighboring fields that have already been visited are marked with the . character, just as you would do in reality with small stones, for example. The trial and error continues until you come to a X as a solution, a wall in the form of a #, or an already visited field (marked by .). If there is no possible direction left for a position, you use backtracking, resume the last chosen path, and try the remaining paths from there. This is implemented as follows:

def find_way_out(values, x, y):

if x < 0 or y < 0 or x > len(values[0]) or y >= len(values):

return False

# recursive termination

if get_at(values, x, y) == 'X':

print("FOUND EXIT: x: {}, y: {}".format(x, y))

return True

# wall or already visited?

if get_at(values, x, y) in '#.':

return False

# recursive descent

if get_at(values, x, y) == ' ':

# mark as visited

values[y][x] = '.'

# try all 4 cardinal directions

up = find_way_out(values, x, y - 1)

left = find_way_out(values, x + 1, y)

down = find_way_out(values, x, y + 1)

right = find_way_out(values, x - 1, y)

found_a_way = up or left or down or right

# backtracking because no valid solution

if not found_a_way:

values[y][x] = ' ' # wrong path, thus delete field marker

return found_a_way

raise ValueError("wrong char in labyrinth")

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

To try it out, you define the maze from the introduction. Next, you call the function find_way_out(), which logs the previously shown exits from the maze and finally visualizes the ways with dots (.). Here you use a version of print_array() that leaves no white space between characters to make the maze more recognizable.

def main():

world_big = [list("##################################"),

list("# # # # # # X#X#"),

list("# ##### #### ## ## # # ### #"),

list("# ## # # ## ## # # # #"),

list("# # ### # ## ## # ### # #"),

list("# # #### ## ## ### # #"),

list("#### # #### #### # #### #"),

list("###### ######### ## # ### #"),

list("## # X X####X # # # ### ##"),

list("##################################")]

print_array(world_big)

if find_way_out(world_big, 1, 1):

print_array(world_big)

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.

If you want to find all reachable exits, it is possible to modify the function shown before so that visited fields are marked with a #. However, this way, the field is quite filled up at the end and does not show the way anymore, which was an advantage of the initial variant.

def find_way_out_v2(board, x, y):

if board[y][x] == '#':

return False

found = board[y][x] == 'X'

if found:

print("FOUND EXIT: x: {}, y: {}".format(x, y))

board[y][x] = '#'

right = find_way_out_v2(board, x + 1, y)

left = find_way_out_v2(board, x - 1, y)

down = find_way_out_v2(board, x, y + 1)

up = find_way_out_v2(board, x, y - 1)

return found or right or left or down or up

Although the playing field is unrecognizable after that, four exits are found:

FOUND EXIT: x: 10, y: 8

FOUND EXIT: x: 12, y: 8

FOUND EXIT: x: 30, y: 1

FOUND EXIT: x: 17, y: 8

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

A valid playfield with some blanks is shown here:

This should be completed to the following solution:

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.

You proceed as follows in the implementation:

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.
1. a.
  Is there a conflict? Then you have to try the next digit.
2. b.
  The digit is a possible candidate. You call your function recursively for the following position (next column or even next row).
3. c.
  If the recursion returns False, this digit does not lead to a solution and you use backtracking.

def solve_sudoku(board):

return __solve_sudoku_helper(board, 0, 0)

def __solve_sudoku_helper(board, start_row, start_col):

# 1) check if all rows have been processed, then you have a solution.

if start_row > 8:

return True

row = start_row

col = start_col

# 2) skip fields with numbers until you reach the next empty field

while board[row][col] != 0:

col += 1

if col > 8:

col = 0

row += 1

# 3) already processed all lines?

if row > 8:

return True

solved = False

# 4) try for the current field all digits from 1 to 9 through

for num in range(1, 10):

board[row][col] = num

# 4a) check if the whole field with the digit is still valid

if is_valid_position(board):

# 4b) recursive descent for the following field

if col < 8:

# recursive descent: next field in x-direction

solved = __solve_sudoku_helper(board, row, col + 1)

else:

# recursive descent: next field in new line

solved = __solve_sudoku_helper(board, row + 1, 0)

# 4c) backtracking if recursion is not successful

if not solved:

# backtracking: no solution found

board[row][col] = 0

else:

return True

else:

# try next digit

board[row][col] = 0

return False

def is_valid_position(board):

return check_horizontally(board) and

check_vertically(board) and

check_boxes(board)

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.

Let’s first consider the three functions check_horizontally(board), check_vertically(board), and check_boxes(board). You implemented them in Exercise 9 in Section 6.3.9. They are shown again here for completeness:

def check_horizontally(board):

for row in range(9):

# collect all values of a row in a list

row_values = [board[row][x] for x in range(9)]

if not all_desired_numbers(row_values):

return False

return True

def check_vertically(board):

for x in range(9):

# collect all values of a column in a list

column_values = [board[row][x] for row in range(9)]

if not all_desired_numbers(column_values):

return False

return True

def check_boxes(board):

for y_box in range(3):

for x_box in range(3):

box_values = collect_box_values(board, y_box, x_box)

if not all_desired_numbers(box_values):

return False

return True

The following auxiliary functions still play an important role:

def collect_box_values(board, y_box, x_box):

box_values = [ ]

for y in range(3):

for x in range(3):

real_y = y_box * 3 + y

real_x = x_box * 3 + x

box_values.append(board[real_y][real_x])

return box_values

def all_desired_numbers(all_collected_values):

relevant_values = list(all_collected_values)

# remove empty fields

relevant_values = remove_all_occurences(relevant_values, 0)

# check that there are no duplicates

values_set = set(relevant_values)

if len(relevant_values) != len(values_set):

return False

# only 1 to 9?

return {1, 2, 3, 4, 5, 6, 7, 8, 9}.issuperset(values_set)

def remove_all_occurences(values, val):

return [value for value in values if value != val]

def print_array(values):

for y in range(len(values)):

for x in range(len(values[y])):

print(values[y][x], end=" ")

print()

Verification

Test this implementation with the example from the introduction:

def main():

board = [[1, 2, 0, 4, 5, 0, 7, 8, 9],

[0, 5, 6, 7, 0, 9, 0, 2, 3],

[7, 8, 0, 1, 2, 3, 4, 5, 6],

[2, 1, 4, 0, 6, 0, 8, 0, 7],

[3, 6, 0, 8, 9, 7, 2, 1, 4],

[0, 9, 7, 0, 1, 4, 3, 6, 0],

[5, 3, 1, 6, 0, 2, 9, 0, 8],

[6, 0, 2, 9, 7, 8, 5, 3, 1],

[9, 7, 0, 0, 3, 1, 6, 4, 2]]

if solve_sudoku(board):

print("Solved!")

print_array(board)

This provides the following result:

Solved!

1 2 3 4 5 6 7 8 9

4 5 6 7 8 9 1 2 3

7 8 9 1 2 3 4 5 6

2 1 4 3 6 5 8 9 7

3 6 5 8 9 7 2 1 4

8 9 7 2 1 4 3 6 5

5 3 1 6 4 2 9 7 8

6 4 2 9 7 8 5 3 1

9 7 8 5 3 1 6 4 2

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?

Playfields with more blanks When you tackle the challenge of trying to solve playfields with only a few given digits, there are many variations to be tried and a lot of backtracking comes into play. Suppose you wanted to solve something like the following playfield:

board2 = [

[6, 0, 2, 0, 5, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 4, 0, 3, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0],

[4, 3, 0, 0, 0, 8, 0, 0, 0],

[0, 1, 0, 0, 0, 0, 2, 0, 0],

[0, 0, 0, 0, 0, 0, 7, 0, 0],

[5, 0, 0, 2, 7, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 8, 1],

[0, 0, 0, 6, 0, 0, 0, 0, 0],

]

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

Idea 1: Optimization of the check Checking the entire playfield for validity in every step is neither useful, necessary, nor performant. As an optimization, you modify the check so that only a single column, row, and the relevant box are checked at a time. To do this, you first modify the function is_valid_position() slightly so that it receives a column and row as parameters:

def is_valid_position(board, row, col):

return check_single_horizontally(board, row) and

check_single_vertically(board, col) and

check_single_box(board, row, col)

Then you create specific test methods such as the following:

def check_single_horizontally(board, row):

column_values = [board[row][col] for col in range(9)]

return all_desired_numbers(column_values)

def check_single_vertically(board, col):

row_values = [board[row][col] for row in range(9)]

return all_desired_numbers(row_values)

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.

Idea 2: More clever testing If you look at the processes, you notice that you try all digits—this violates a bit of common sense. Wouldn’t it make more sense to only use potentially valid paths, and to do so, check in advance whether the current digit is even usable in the context? You can then directly exclude all those digits that already exist in a row, column, or box. To do this, you need to modify the check as follows and pass the potential digit as parameter.

def is_valid_position(board, row, col, num):

return check_num_not_in_column(board, col, num) and

check_num_not_in_row(board, row, num) and

check_num_not_in_box(board, row, col, num)

def check_num_not_in_column(board, col, num):

for row in range(9):

if board[row][col] == num:

return False

return True

def check_num_not_in_row(board, row, num):

for col in range(9):

if board[row][col] == num:

return False

return True

def check_num_not_in_box(board, row, col, num):

adjusted_row = row // 3 * 3

adjusted_col = col // 3 * 3

for y in range(3):

for x in range(3):

if board[adjusted_row + y][adjusted_col + x] == num:

return False

return True

Idea 3: Optimized sequence of setting and checking Finally, you modify the trial and error so that only after determining that the digit is valid is it placed on the playfield. So far, in the solve_sudoku() function as step 4, you have tried all the digit as follows:

def __solve_sudoku_helper(board, start_row, start_col):

...

solved = False

# 4) for the current field, try all digits from 1 to 9

for num in range(1, 10):

board[row][col] = num

# 4a) check if the whole playfield containing the digit is still valid

if is_valid_position(board, row, col, num):

...

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).

Now you go one step further and change the order of inserting the value and checking. Therefore you switch only two lines, namely the assignment and the if with the call of the optimized variant of the validity check:

# 4) for the current field, try all digits from 1 to 9

for num in range(1, 10):

# 4a) check if the whole playfield containing the digit is still valid

if is_valid_position(board, row, col, num)

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

In total, these digits allow the following different combinations:

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

In total, the following variants should be determined:

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]

Algorithm First, you subdivide the problem at a high level by computing all possible combinations by calling the function all_combinations() and then using find_by_value() to search for those combinations whose evaluation yields the desired value:

def all_combinations_with_value(base_values, desired_value):

all_combinations = find_all_combinations(base_values)

return find_by_value(all_combinations, desired_value)

def find_by_value(all_combinations, desired_value):

return {key for key, value in all_combinations.items()

if value == desired_value}

To calculate the combinations, the input is split into a left part and a right part. This results in three subproblems to be solved, namely l + r, l − r, and lr, where l and r stand for the left and right parts of the input. You compute the result with the function eval(). If there is only one digit left, this is the result and it constitutes the recursive termination.

def find_all_combinations(digits):

# recursive termination

if len(digits) == 0:

return {}

if len(digits) == 1:

last_digit = digits[0]

return {last_digit: last_digit}

# recursive descent

left = digits[0]

right = digits[1:]

results = find_all_combinations(right)

# create all combinations

solutions = {}

for expression, value in results.items():

right_expr = str(expression)

solutions[str(left) + "+" + right_expr] =

eval(str(left) + "+" + right_expr)

solutions[str(left) + "-" + right_expr] =

eval(str(left) + "-" + right_expr)

solutions[str(left) + right_expr] =

eval(str(left) + right_expr)

return solutions

This variant is quite understandable but has the disadvantage that here again various partial lists are generated. Since the list with the digits is probably rather short, this does not matter. Nevertheless, as a mini-optimization, let’s take a look at a variant that works with a position pointer.

def find_all_combinations(digits):

return __all_combinations_helper(digits, 0)

def __all_combinations_helper(digits, pos):

# recursive termination: last digit

# no calculation needed, just digit

if pos == len(digits) - 1:

last_digit = digits[len(digits) - 1]

return {last_digit: last_digit}

# recursive descent

results = __all_combinations_helper(digits, pos + 1)

# create all combinations

solutions = {}

current_digit = digits[pos]

left = str(current_digit)

for expression, value in results.items():

right = str(expression)

solutions[left + "+" + right] = eval(left + "+" + right)

solutions[left + "-" + right] = eval(left + "-" + right)

solutions[left + right] = eval(left + right)

return solutions

Verification

First, you write a unit test that checks the values shown in the introduction, namely the inputs 1 to 3, and which combinations can be built upon them.

@pytest.mark.parametrize("digits, expected",

[([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})])

def test_all_combinations(digits, expected):

result = find_all_combinations(digits)

assert result == expected

Additionally, you want to verify the functionality for the result value 100.

@pytest.mark.parametrize("digits, value, expected",

[([1, 2, 3, 4, 5, 6, 7, 8, 9], 100,

{"1+23-4+5+6+78-9",

"12+3+4+5-6-7+89",

"123-45-67+89",

"123+4-5+67-89",

"123-4-5-6-7+8-9",

"123+45-67+8-9",

"1+2+3-4+5+6+78+9",

"12+3-4+5+67+8+9",

"1+23-4+56+7+8+9",

"1+2+34-5+67-8+9",

"12-3-4+5-6+7+89"})])

def test_all_combinations_with_value(digits, value, expected):

result = all_combinations_with_value(digits, value)

assert result == expected

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

For two jugs, one with a capacity of 4 liters and one with a capacity of 3 liters, you can measure 2 liters in the following way:

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.

Algorithm To solve the water jug problem, you use recursion with a greedy algorithm. Here, at each point in time, you have the following next actions as possibilities:

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.

Try these six variants step by step until one of them succeeds. To do this, you need to test each time whether there is the desired number of liters in one of the jugs and whether the other is empty.

def is_solved(current_jug1, current_jug2, desired_liters):

return (current_jug1 == desired_liters and current_jug2 == 0) or

(current_jug2 == desired_liters and current_jug1 == 0)

Because trying out many solutions can be quite time-consuming, you remember for optimization the combinations you have already tried out. This speeds up the calculation by lengths but makes the implementation only minimally more complicated if you model the already calculated levels in the form of a tuple. To find the solution, you start with two empty jugs.

def solve_water_jugs(size1, size2, desired_liters):

return __solve_water_jugs_rec(size1, size2, desired_liters, 0, 0, {})

def __solve_water_jugs_rec(size1, size2, desired_liters,

current_jug1, current_jug2, already_tried):

if is_solved(current_jug1, current_jug2, desired_liters):

print("Solved Jug 1:", current_jug1, " / 2:", current_jug2)

return True

key = (current_jug1, current_jug2)

if key not in already_tried:

already_tried[key] = True

# try all 6 variants

print("Jug 1:", current_jug1, " / 2: ", current_jug2)

min_2_1 = min(current_jug2, (size1 - current_jug1))

min_1_2 = min(current_jug1, (size2 - current_jug2))

result = __solve_water_jugs_rec(size1, size2, desired_liters,

0, current_jug2, already_tried) or