Sol Golomb’s Rectangle Puzzle

This problem was presented by Gary Antonik in his 14/4/14 New York Times Numberplay column.

Say you’re given the following challenge: create a set of five rectangles that have sides of length 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10 units. You can combine sides in a variety of ways: for example, you could create a set of rectangles with dimensions 1 x 3, 2 x 4, 5 x 7, 6 x 8 and 9 x 10.

  1. How many different sets of five rectangles are possible?

  2. What are the maximum and minimum values for the total areas of the five rectangles?

    Bonus Challenges

  3. What other values for the total areas of the five rectangles are possible?

  4. Which sets of rectangles may be assembled to form a square?

To me, these are interesting questions because, first, I have a (slight) personal connection to Solomon Golomb (my former colleague at USC) and to Nelson Blachman (the father of my colleague Nancy Blachman), who presented the problem to Antonik, and second, I find it interesting that the problems span the range from mathematical to computational. I wonder how the way I look at the problems compares to others who have a different mix of these two disciplines.

1. How many different sets of five rectangles are possible?

This is a basic combinatorics or counting problem. I will present three methods to count the sets. (Hopefully they will give the same answer.) The example set given in the problem was

{1 × 3, 2 × 4, 5 × 7, 6 × 8, 9 × 10}

and in general it would be

{A × B, C × D, E × F, G × H, I × J}

The question is: how many distinct ways can we assign values to the variables A through J?

Method 1: Count all permutations and divide by repetitions: There are 10 variables to be filled, so there are 10! = 3628800 permutations. But if we fill the first two variables with 1 × 3, that is the same rectangle as 3 × 1. So divide 10! by 25 to account for the fact that each of 5 rectangles can appear 2 ways. Similarly, if we fill A and B with 1 × 3, that yields the same set as if we filled C and D with 1 × 3. So divide again by 5! (the number of permutations of 5 things) to account for this. That gives us 10! / 25 / 5! = 945. (It is always gratifying when this "count and divide" method comes out to a whole number.)

Method 2: Count without repetitions: The example set is presented in lexicographical order: in each rectangle the smaller component is listed first, and in the set, the rectangles with smaller first components are listed first. An alternate to "count and divide" is to count directly how many sets there are in lexicographical order. We'll work from left to right. How many choices are there for variable A? Only one: A must always be 1, because we agreed that the smallest number comes first. Then, given A, there are 9 remaining choices for B. For C, given A and B, there is again only one choice: C must be the smallest of the remaining 8 numbers (it will be 3 if the first rectangle was 1 × 2; otherwise it will be 2, but either way there is only one choice). That leaves 7 choices for D, 5 for F, 3 for H and 1 for J. And 9 × 7 × 5 × 3 × 1 = 945. (It is always gratifying when two methods give the same answer.)

Method 3: Write a program to enumerate the sets: We'll represent the 1 × 3 rectangle as the tuple (1, 3) and the example set of rectangles as the set

{(1, 3), (2, 4), (5, 7), (6, 8), (9, 10)}

To generate all the sets of rectangles, we'll follow method 2: given a set of sides, first make all possible rectangles (A, B) where A is the shortest side, and B ranges over all the other sides. For each of (A, B) rectangle, consider all possible (C, D) rectangles, and so on. This is easy to write out if we know there will be exactly 5 rectangles in a set:

In [100]:
def sets_of_rectangles(sides):
    "Given exactly 10 sides, yield all sets of rectangles that can be made from them."
    A = min(sides)
    for (A, B) in each_rectangle(sides):
        for (C, D) in each_rectangle(sides - {A, B}):
            for (E, F) in each_rectangle(sides - {A, B, C, D}):
                for (G, H) in each_rectangle(sides - {A, B, C, D, E, F}):
                    for (I, J) in each_rectangle(sides - {A, B, C, D, E, F, G, H}):
                        yield {(A, B), (C, D), (E, F), (G, H), (I, J)}
                        
def each_rectangle(sides):
    "Yield all (A, B) pairs, where A is minimum of sides, and B ranges over all other sides."
    A = min(sides)
    for B in (sides - {A}):
        yield (A, B)    
In [101]:
sides = set(range(1, 11))
sets = list(sets_of_rectangles(sides))
len(sets)
Out[101]:
945

(Gratifying that once again we get the same answer.) But I don't like the fact that the code only works for exactly 10 sides, and it violates the "don't repeat yourself" maxim. So let's convert the nested-iterated algorithm into a recursive algorithm that chooses the first rectangle (in the same way as before), but then recursively solves for the remaining sides and unions the set of rectangles from the remaining sides with the first rectangle. (Note we have to also correctly handle the case when there are no sides; then there is one way to make a set of rectangles: the empty set.)

In [102]:
def sets_of_rectangles(sides):
    "Given a set of sides, yield all sets of rectangles that can be made from sides."
    if sides:
        A = min(sides)
        for B in (sides - {A}):
            for rest in sets_of_rectangles(sides - {A, B}):
                yield {(A, B)}.union(rest)
    else:
        yield set()
In [103]:
# For example, with 6 sides:
list(sets_of_rectangles({1, 2, 3, 4, 5, 6}))
Out[103]:
[{(1, 2), (3, 4), (5, 6)},
 {(1, 2), (3, 5), (4, 6)},
 {(1, 2), (3, 6), (4, 5)},
 {(1, 3), (2, 4), (5, 6)},
 {(1, 3), (2, 5), (4, 6)},
 {(1, 3), (2, 6), (4, 5)},
 {(1, 4), (2, 3), (5, 6)},
 {(1, 4), (2, 5), (3, 6)},
 {(1, 4), (2, 6), (3, 5)},
 {(1, 5), (2, 3), (4, 6)},
 {(1, 5), (2, 4), (3, 6)},
 {(1, 5), (2, 6), (3, 4)},
 {(1, 6), (2, 3), (4, 5)},
 {(1, 6), (2, 4), (3, 5)},
 {(1, 6), (2, 5), (3, 4)}]
In [104]:
# Reaffirm the answer with 10 sides
sets = list(sets_of_rectangles(sides))
len(sets)
Out[104]:
945

I don't want to print all 945 sets, but let's peek at every 100th one:

In [105]:
sets[::100]
Out[105]:
[{(1, 2), (3, 4), (5, 8), (6, 9), (7, 10)},
 {(1, 2), (3, 10), (4, 6), (5, 9), (7, 8)},
 {(1, 3), (2, 10), (4, 9), (5, 7), (6, 8)},
 {(1, 4), (2, 10), (3, 8), (5, 9), (6, 7)},
 {(1, 5), (2, 9), (3, 6), (4, 10), (7, 8)},
 {(1, 6), (2, 9), (3, 10), (4, 7), (5, 8)},
 {(1, 7), (2, 9), (3, 8), (4, 10), (5, 6)},
 {(1, 8), (2, 7), (3, 5), (4, 10), (6, 9)},
 {(1, 9), (2, 7), (3, 10), (4, 6), (5, 8)},
 {(1, 10), (2, 7), (3, 8), (4, 9), (5, 6)}]

2. What are the maximum and minimum values for the total areas of the five rectangles?

I think I know this one, but I'm not completely sure. I know that a rectangle with a fixed perimeter has maximum area when it is a square. My guess is that the maximum total area occurs when each rectangle is almost square: a 9 × 10 rectangle; 7 × 8; and so on. So that would give us a maximum area of:

In [106]:
(1 * 2) + (3 * 4) + (5 * 6) + (7 * 8) + (9  * 10)
Out[106]:
190

And the minimum area should be when the rectangles deviate the most from squares: a 1 × 10, and so on:

In [107]:
(1 * 10) + (2 * 9) + (3 * 8) + (4 * 7) + (5 * 6)
Out[107]:
110

Since I am not sure, I will double check by computing the set of all possible areas and then asking for the min and max of the set:

In [108]:
def area(rectangle): (w, h) = rectangle; return w * h

def total_area(rectangles): return sum(area(r) for r in rectangles)

areas = {total_area(s) for s in sets}
In [109]:
max(areas)
Out[109]:
190
In [110]:
min(areas)
Out[110]:
110

This verifies that the maximum and minimum are what I thought they were. But I still don't think I completely understand the situation. For example, suppose there are N sides that are not necessarily consecutive integers. Will the maximum total area always be formed by combining the two biggest sides, and so on?

3. What other values for the total areas of the five rectangles are possible?

I have no idea how to figure this out mathematically from first principles, but it is easy to compute with the code we already have:

In [111]:
print sorted(areas) 
[110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 177, 178, 179, 180, 181, 182, 183, 184, 186, 187, 190]

Is there a more succint way to describe these values?

In [112]:
set(range(110, 191)) - areas
Out[112]:
{176, 185, 188, 189}

Yes: All the integers between 110 and 190 inclusive, except 176, 185, 188, and 189.

4. Which sets of rectangles may be assembled to form a square?

The only way I can think about this is to write a program; I don't see any way to work it out by hand. I do know that the total area will have to be a perfect square, and that in the range of areas (110 to 190) the only perfect squares are 112 = 121, 122 = 144, and 132 = 169. We can find the rectangle sets that have a perfect square as their total area:

In [113]:
[s for s in sets if total_area(s) in {121, 144, 169}]
Out[113]:
[{(1, 2), (3, 5), (4, 9), (6, 10), (7, 8)},
 {(1, 2), (3, 7), (4, 9), (5, 6), (8, 10)},
 {(1, 2), (3, 7), (4, 6), (5, 10), (8, 9)},
 {(1, 2), (3, 8), (4, 5), (6, 10), (7, 9)},
 {(1, 3), (2, 5), (4, 8), (6, 9), (7, 10)},
 {(1, 3), (2, 7), (4, 8), (5, 6), (9, 10)},
 {(1, 3), (2, 7), (4, 5), (6, 10), (8, 9)},
 {(1, 3), (2, 9), (4, 10), (5, 7), (6, 8)},
 {(1, 3), (2, 10), (4, 8), (5, 7), (6, 9)},
 {(1, 3), (2, 10), (4, 7), (5, 9), (6, 8)},
 {(1, 4), (2, 5), (3, 7), (6, 9), (8, 10)},
 {(1, 5), (2, 3), (4, 9), (6, 7), (8, 10)},
 {(1, 5), (2, 4), (3, 8), (6, 7), (9, 10)},
 {(1, 5), (2, 6), (3, 8), (4, 10), (7, 9)},
 {(1, 5), (2, 7), (3, 4), (6, 8), (9, 10)},
 {(1, 6), (2, 3), (4, 8), (5, 7), (9, 10)},
 {(1, 6), (2, 9), (3, 10), (4, 8), (5, 7)},
 {(1, 6), (2, 10), (3, 8), (4, 9), (5, 7)},
 {(1, 6), (2, 10), (3, 9), (4, 7), (5, 8)},
 {(1, 7), (2, 4), (3, 8), (5, 9), (6, 10)},
 {(1, 7), (2, 9), (3, 5), (4, 6), (8, 10)},
 {(1, 7), (2, 10), (3, 6), (4, 9), (5, 8)},
 {(1, 8), (2, 6), (3, 10), (4, 9), (5, 7)},
 {(1, 8), (2, 7), (3, 10), (4, 6), (5, 9)},
 {(1, 8), (2, 9), (3, 7), (4, 6), (5, 10)},
 {(1, 8), (2, 10), (3, 5), (4, 9), (6, 7)},
 {(1, 9), (2, 5), (3, 7), (4, 6), (8, 10)},
 {(1, 9), (2, 6), (3, 5), (4, 7), (8, 10)},
 {(1, 9), (2, 7), (3, 8), (4, 6), (5, 10)},
 {(1, 9), (2, 7), (3, 10), (4, 5), (6, 8)},
 {(1, 9), (2, 7), (3, 6), (4, 10), (5, 8)},
 {(1, 9), (2, 8), (3, 6), (4, 7), (5, 10)},
 {(1, 10), (2, 4), (3, 5), (6, 8), (7, 9)},
 {(1, 10), (2, 5), (3, 9), (4, 8), (6, 7)},
 {(1, 10), (2, 8), (3, 7), (4, 5), (6, 9)}]
In [114]:
len(_)
Out[114]:
35

So 35 out of 945 rectangle sets might be assembled into a square; we don't know yet. Also I would like to see how the rectangles are packed into the square, not just which sets can be packed, so I'll need a visual display of rectangles packed into a square. To start, I'll represent a Grid as a two-dimensional array: a list of rows, each of which is a list of cells, with the idea that each cell will be covered by a rectangle. We'll initialize each cell to be empty:

In [115]:
empty = (0, 0)

def Grid(width, height):
    return [[empty for col in range(width)] for row in range(height)]

def Square(size): return Grid(size, size)
In [116]:
Square(5)
Out[116]:
[[(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
 [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
 [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
 [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
 [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)]]

Let's make a function to place a rectangle onto a grid. place_rectangle_at places a rectangle of width w and height h onto a grid at position (x0, y0). If the rectangle overlaps a non-empty cell, or goes off the grid, we return None to indicate that this is not a legal placement. If the rectangle does fit, we return a new grid with any old rectangles plus the new one (we do not modify the old grid):

In [117]:
def place_rectangle_at(rect, grid, pos):
    """Place the rectangle of size (w, h) onto grid at position (x0, y0).
    Return a new grid, or None if the rectangle cannot be placed."""
    (w, h) = rect
    (x0, y0) = pos
    newgrid = map(list, grid) # make a copy
    try:
        for x in range(x0, x0+w):
            for y in range(y0, y0+h):
                if newgrid[y][x] is not empty:
                    return None   
                newgrid[y][x] = rect
        return newgrid
    except IndexError: # went off the grid
        return None
In [118]:
# Place a 3 x 4 rectangle on a square grid, 2 cells over and 1 down:
place_rectangle_at((3, 4), Square(5), (2, 1))
Out[118]:
[[(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
 [(0, 0), (0, 0), (3, 4), (3, 4), (3, 4)],
 [(0, 0), (0, 0), (3, 4), (3, 4), (3, 4)],
 [(0, 0), (0, 0), (3, 4), (3, 4), (3, 4)],
 [(0, 0), (0, 0), (3, 4), (3, 4), (3, 4)]]
In [119]:
# Place two rectangles on a grid
grid2 = place_rectangle_at((3, 4), Square(5), (2, 1))
grid3 = place_rectangle_at((2, 5), grid2, (0, 0))
grid3
Out[119]:
[[(2, 5), (2, 5), (0, 0), (0, 0), (0, 0)],
 [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],
 [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],
 [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],
 [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)]]
In [120]:
# Now try to place a third rectangle that does not fit; should fail
print place_rectangle_at((6, 1), grid3, (0, 2))
None

Now we need a strategy for packing a set of rectangles onto a grid. I know that many variants of bin packing problems are NP-hard, but we only have 5 rectangles, so it should be easy: just exhaustively try each rectangle in each possible position in both possible orientations (horizontal and vertical). But placing rectangles is commutative, so we can do this two ways:

Way 1: Considering the rectangles in a fixed order, try every possible position for each rectangle.

or

Way 2: Considering the positions in a fixed order, try every possible rectangle for each position.

In Way 1, we could pre-sort the rectangles (say, biggest first). Then we try to put the biggest rectangle in all possible positions on the grid, and for each position that fits, try putting the second biggest rectangle in all remaining positions, and so on.

In Way 2, we consider the positions in some fixed order; say top-to-bottom, left-to right. Take the first empty position (the upper left corner). Try putting each of the rectangles there, and for each one that fits, try the next empty position, and consider all possible rectangles to go there, and so on.

Which way is better? I'm not sure—let us calculate. As a wild guess, assume there are on average about 10 ways to place a rectangle on a grid. Then Way 1 will look at 105 = 100,000 combinations. For Way 2, there are only 5! = 120 permutations of rectangles, and each rectangle can go either horizontaly or verticaly, so that's 5! × 25 = 3840. Since 3840 < 100,000, I'll go with Way 2. Here is a more precise description:

Way 2: To pack a set of rectangles onto a grid, find the first empty cell on the grid. Try in turn to place each rectangle (in either orientation) at that position. For each one that fits, try to recursively pack the remaining rectangles, and return the resulting grid if one of these recursive calls succeeds. If none succeeds, return None. Details: If there are no rectangles to pack, the solution is the original grid. If the grid is illegal, we can't place anything on it, so return None. The order we choose for the first empty cell is arbitrary; we will go top-to-bottom, left-to-right.

In [121]:
def pack(rectangles, grid):
    """Find a way to pack all rectangles onto grid and return the packed grid,
    or return None if not possible."""
    if not rectangles:
        return grid # Placing no rectangles give you the original grid
    elif not grid:
        return None  # Can't put rectangles on an illegal grid
    else:
        pos = first_empty_cell(grid)
        for (w, h) in rectangles: # for each rectangle
            for rect in [(w, h), (h, w)]: # in either orientation
                grid2 = place_rectangle_at(rect, grid, pos)
                solution = pack(rectangles - {(w, h)}, grid2)
                if solution:
                    return solution
        return None
    
def first_empty_cell(grid):
    "The uppermost, leftmost empty cell position on grid."
    for (y, row) in enumerate(grid):
        for (x, cell) in enumerate(row):
            if cell is empty:
                return (x, y)

Let's try a simple example that I know will fit:

In [122]:
pack({(1, 3), (2, 5), (3, 4)}, Square(5))
Out[122]:
[[(2, 5), (2, 5), (3, 1), (3, 1), (3, 1)],
 [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],
 [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],
 [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],
 [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)]]

Colored Rectangles

The grid output does show how the rectangles are packed into the square, but the output is hard to read. It would be nicer to have a graphical display of colored rectangles. IPython has an add-on module called ipythonblocks that does this. (If you are running this notebook in your copy of IPython notebook, you may need to do the shell command "pip install ipythonblocks" or "easy-install ipythonblocks".) I will define the function show which takes a grid and displays it as a matrix of colored rectangles.

In [123]:
import ipythonblocks

def show(grid):
    "Convert a python grid into an ipythonblocks BlockGrid and show it."
    (w, h) = (len(grid[0]), len(grid))
    bg = ipythonblocks.BlockGrid(w, h)
    for x in range(w):
        for y in range(h):
            bg[y,x] = color(grid[y][x])
    bg.show()
            
def color(rect):
    "Determine a color for a rectangle."
    # Base the color on the length of the sides of the rectangle
    # Choose R,G,B values to give rectangles different colors
    light = 240 # R,G,B = 240,240,240 is a light grey
    short, long = sorted(rect) # Find the short and long sides
    R, G, B = light-24*short, light-24*long, light-(50*(long%3) + 70*(short%3))
    return (R, G, B)
In [124]:
show(pack({(1, 3), (2, 5), (3, 4)}, Square(5)))

That's much easier to look at! Now we can create a function to show all the packable sets of rectangles:

In [125]:
def show_packable(sets):
    "Given a sequence of sets of rectangles, show the ones that can be packed into a square."
    for rectangles in sets:
        A = total_area(rectangles)
        side = int(A ** 0.5)
        if side ** 2 == A:
            grid = pack(rectangles, Square(side))
            if grid:
                show(grid)
In [126]:
%time show_packable(sets)
CPU times: user 488 ms, sys: 21.5 ms, total: 510 ms
Wall time: 495 ms

We see it takes about half a second to go through all 945 sets of rectangles, find the 35 sets whose total area is a perfect square, try to pack each set into a square, and display the four that work. (I had a couple of ideas for how to make this faster, but I won't bother because it is plenty fast enough.)

Animated Colored Rectangles

It is gratifying to see the final results, and have the computation be so fast, but I'd like to get a better understanding of the process of finding the results. I can try to visualize the process by animating the search that pack does: every time we consider placing a new rectangle, show the grid, and then pause for a short period. If you are running this in a live IPython notebook (not in nbviewer), you can see for yourself by running this cell:

In [127]:
import IPython.display 
import time

def pack(rectangles, grid):
    """Find a way to pack all rectangles onto grid and return the packed grid,
    or return None if not possible."""
    if not rectangles:
        return grid # Placing no rectangles give you the original grid
    elif not grid:
        return None  # Can't put rectangles on an illegal grid
    else:
        show(grid)                     # <<<<<<<<<<<<<<<< CHANGE HERE
        time.sleep(0.3)                # <<<<<<<<<<<<<<<< CHANGE HERE
        IPython.display.clear_output() # <<<<<<<<<<<<<<<< CHANGE HERE        
        pos = first_empty_cell(grid)
        for (w, h) in rectangles: # for each rectangle
            for rect in [(w, h), (h, w)]: # in each orientation
                grid2 = place_rectangle_at(rect, grid, pos)
                solution = pack(rectangles - {(w, h)}, grid2)
                if solution:
                    return solution
        return None

rectangles = {(1, 2), (3, 7), (4, 6), (5, 10), (8, 9)}
show_packable([rectangles])

And Now For Something Completely Different

On April 28, Gary Antonik had another Numberplay column that quotes my friend Bill Gosper. (Gosper often presents more advanced puzzles in the math-fun mailing list.) This puzzle was:

For the expression N U M + B E R = P L A Y,

Which distinct numerals (each different) can be substituted for letters to make a valid expression?

How many solutions are there?

I tackled this type of problem (known as a cryptarithmetic or alphametic problem) in my Udacity class CS 212. My approach was simple: try all permutations of digits replacing letters (that should be quick and easy—there can be at most 10 factorial or 3.6 million permutations), then for each one, use Python's eval function to see if the resulting string is a true expression. The basic idea is simple, but there are complications to worry about:

  1. Math uses = and Python uses == for equality; we'll allow either one.
  2. The more detailed rules for these problems say that a number with a leading zero (like 012) is illegal (but 0 itself is ok).
  3. By default, Python thinks that 3/2 is 1, because integer division rounds down. But we can import "proper" division from the future.
  4. If we try to eval an expression like 1/0, Python raises an error; we'll have to handle it.
In [137]:
from __future__ import division
import itertools, string, re

def solve_all(formula):
    """Given a formula like 'NUM + BER = PLAY', fill in digits to solve it.
    Input formula is a string; generate each digit-filled-in string."""
    for exp in replace_letters(formula.replace(' = ', ' == ')):
        if valid(exp):
            yield exp

def replace_letters(formula):
    "Generate all possible replacements of letters with digits in formula."
    letters = ''.join(set(re.findall('[A-Z]', formula)))
    for digits in itertools.permutations('1234567890', len(letters)):
        trans = string.maketrans(letters, ''.join(digits))
        yield formula.translate(trans)

def valid(exp):
    "Expression is valid iff it has no numbers with leading zero, and evals true."
    try:
        return not re.search(r'\b0[0-9]', exp) and (eval(exp) is True)
    except ArithmeticError:
        return False
In [141]:
% time list(solve_all('NUM + BER = PLAY'))
CPU times: user 50.8 s, sys: 1.77 s, total: 52.6 s
Wall time: 51.5 s

Out[141]:
['587 + 439 == 1026',
 '589 + 437 == 1026',
 '537 + 489 == 1026',
 '539 + 487 == 1026',
 '487 + 539 == 1026',
 '489 + 537 == 1026',
 '437 + 589 == 1026',
 '439 + 587 == 1026',
 '786 + 249 == 1035',
 '789 + 246 == 1035',
 '746 + 289 == 1035',
 '749 + 286 == 1035',
 '286 + 749 == 1035',
 '289 + 746 == 1035',
 '246 + 789 == 1035',
 '249 + 786 == 1035',
 '784 + 269 == 1053',
 '789 + 264 == 1053',
 '764 + 289 == 1053',
 '769 + 284 == 1053',
 '284 + 769 == 1053',
 '289 + 764 == 1053',
 '264 + 789 == 1053',
 '269 + 784 == 1053',
 '583 + 479 == 1062',
 '589 + 473 == 1062',
 '573 + 489 == 1062',
 '579 + 483 == 1062',
 '483 + 579 == 1062',
 '489 + 573 == 1062',
 '473 + 589 == 1062',
 '479 + 583 == 1062',
 '764 + 325 == 1089',
 '765 + 324 == 1089',
 '724 + 365 == 1089',
 '725 + 364 == 1089',
 '652 + 437 == 1089',
 '657 + 432 == 1089',
 '632 + 457 == 1089',
 '637 + 452 == 1089',
 '452 + 637 == 1089',
 '457 + 632 == 1089',
 '432 + 657 == 1089',
 '437 + 652 == 1089',
 '364 + 725 == 1089',
 '365 + 724 == 1089',
 '324 + 765 == 1089',
 '325 + 764 == 1089',
 '752 + 346 == 1098',
 '756 + 342 == 1098',
 '742 + 356 == 1098',
 '746 + 352 == 1098',
 '673 + 425 == 1098',
 '675 + 423 == 1098',
 '623 + 475 == 1098',
 '625 + 473 == 1098',
 '473 + 625 == 1098',
 '475 + 623 == 1098',
 '423 + 675 == 1098',
 '425 + 673 == 1098',
 '352 + 746 == 1098',
 '356 + 742 == 1098',
 '342 + 756 == 1098',
 '346 + 752 == 1098',
 '857 + 349 == 1206',
 '859 + 347 == 1206',
 '847 + 359 == 1206',
 '849 + 357 == 1206',
 '876 + 429 == 1305',
 '879 + 426 == 1305',
 '826 + 479 == 1305',
 '829 + 476 == 1305',
 '874 + 629 == 1503',
 '879 + 624 == 1503',
 '824 + 679 == 1503',
 '829 + 674 == 1503',
 '853 + 749 == 1602',
 '859 + 743 == 1602',
 '843 + 759 == 1602',
 '849 + 753 == 1602',
 '674 + 829 == 1503',
 '476 + 829 == 1305',
 '479 + 826 == 1305',
 '679 + 824 == 1503',
 '753 + 849 == 1602',
 '357 + 849 == 1206',
 '359 + 847 == 1206',
 '759 + 843 == 1602',
 '743 + 859 == 1602',
 '347 + 859 == 1206',
 '349 + 857 == 1206',
 '749 + 853 == 1602',
 '624 + 879 == 1503',
 '426 + 879 == 1305',
 '429 + 876 == 1305',
 '629 + 874 == 1503']
In [143]:
len(_)
Out[143]:
96

So there are 96 solutions, and we can see each one. It is a little disapointing that it takes about a minute to solve. In my Udacity class I show another approach that is about 20 times faster; you can go there to see it.