MTHSC 360 Triangle Puzzle -- Sage

Triangle Puzzle

Project 2

Consider an isoceles triangle with 4 slots on each side and 5

slots on the base. We can place the integers 0 through 9 on

the slots of the triangle as follows.

1 9

2 8

3 4 5 6 7

In this case the left side adds up to 6, the right side adds

up to 24, and the base adds up to 25. The goal of the triangle

puzzle is to find arrangements of the integers 0 through 9 so

that all three sides add up to the same number.

The goal of the project is to write a program which will generate

ALL the distinct solutions to the triangle puzzle in the most

efficient way possible. I have sent you a copy of Triangle1.m

which is a working - but very inefficient - program for

generating all the solutions.

The first strategy to improve the efficiency of the program is

to incorporate "pruning." Stop searching as soon as you can.

For example, as soon as two sides do not add up to the same

number, there is no value in examining the third side.

The second strategy is to exploit symmetries. For every solution

there are 47 other solutions which are related by reflection and

by three sets of permutations. To be truly efficient, the program

should NOT generate any of those 47 solutions which are known

implicitly. This means that we should only generate solutions

which are guaranteed to be in separate equivalence classes. We

can do that if we insure that we only pick pairs or triples which

are increasing wherever they could be permuted since the permutation

would destroy the increasing property.

For example,

7 5

8 9

1 3 4 6 2

Is a solution with each side adding up to 16. An arbitrary

permutation of this solution will not give us a solution.

For example if we exchange the two bottom corners

7 5

8 9

2 3 4 6 1

the bottom still adds up to 16, but the left side adds up to

17,and the right side adds up to 15. However there are some

permutations which are guaranteed to leave all three sums

invariant ("invariant" is the mathematician's $64 word for

"unchanged"). Specifically, other solutions can be obtained

by refecting the triangle;

5 7

9 8

2 6 4 3 1

by permuting the interior elements on the left side;

8 5

7 9

1 3 4 6 2

by permuting the interior elements on the right side;

7 9

8 5

1 3 4 6 2

by permuting the interior elements on the bottom;

7 5

8 9

1 6 3 4 2

or by combining any of these four operations.

5 8

9 7

2 3 6 4 1

There are a total of 48 (2 x 2 x 2 x 6) solutions which

are equivalent in the sense that we can move from one

to another by some combination of these reflections and

permutations. We can guarantee that we only examine one

candidate from each equivalence class by insisting that

if the entries are labled as shown

b j

c i

d e f g h

then we will only check those cases where

d < h; b < c; e < f < g; and j < i.

First, modify the program, Timing1.m, so that it incorporates

pruning. Call this version, Timing2.m, and obtain some

timing results.

Second, modify Timing2.m so that it exploits symmetries

and only generates one solution from each equivalence class.

Your program should report the total number of solutions

that it finds (explicit and implicit). If PrintOut is set

to 1, then your program should generate a list with one

and only one solution from each equivalence class.

You should also try to determine the complexity of your

program and make your program as efficient as possible.

Given sufficient mathematical insight, it is possible

to incorporate additional pruning, which can make this

program dramatically more efficient.Triangle Puzzle

Consider an isoceles triangle with 4 slots on each side and 5 slots on the base. We can place the integers 0 through 9 on the slots of the triangle as follows.

1 9

2 8

3 4 5 6 7

In this case the left side adds up to 6, the right side adds up to 24, and the base adds up to 25. The goal of the triangle puzzle is to find arrangements of the integers 0 through 9 so that all three sides add up to the same number.

The goal of the programming exercise is to write a program which will generate ALL the distinct solutions to the triangle puzzle in the most efficient way possible.

list = set(range(10)) print list s = 3 list.remove(s) print list list.add(s) print list

def Triangle_Puzzle01(): list = set(range(10)) count = 0 for t0 in list: list.remove(t0) for t1 in list: list.remove(t1) for t2 in list: list.remove(t2) for t3 in list: list.remove(t3) for t4 in list: list.remove(t4) for t5 in list: list.remove(t5) for t6 in list: list.remove(t6) for t7 in list: list.remove(t7) for t8 in list: list.remove(t8) for t9 in list: left_sum = t0+t1+t2+t3 right_sum = t3+t4+t5+t6+t7 bottom_sum = t7+t8+t9+t0 if left_sum==right_sum and right_sum==bottom_sum: count += 1 if count < 4: print ' ',t0 print ' ',t1,t9 print ' ',t2,' ',t8 print t3,t4,t5,t6,t7 print list.add(t8) list.add(t7) list.add(t6) list.add(t5) list.add(t4) list.add(t3) list.add(t2) list.add(t1) list.add(t0)

time Triangle_Puzzle01()

The first strategy to improve the efficiency of the program is

to incorporate "pruning." Stop searching as soon as you can.

For example, as soon as two sides do not add up to the same

number, there is no value in examining the third side.

def Triangle_Puzzle02(): list = set(range(10)) count = 0 for t0 in list: list.remove(t0) for t1 in list: list.remove(t1) for t2 in list: list.remove(t2) for t3 in list: left_sum = t0+t1+t2+t3 list.remove(t3) for t7 in list: list.remove(t7) for t8 in list: list.remove(t8) for t9 in list: right_sum = t7+t8+t9+t0 if left_sum == right_sum: list.remove(t9) for t4 in list: list.remove(t4) for t5 in list: list.remove(t5) for t6 in list: bottom_sum = t3+t4+t5+t6+t7 if left_sum == bottom_sum: count += 1 if count < 4: print ' ',t0 print ' ',t1,t9 print ' ',t2,' ',t8 print t3,t4,t5,t6,t7 print list.add(t5) list.add(t4) list.add(t9) list.add(t8) list.add(t7) list.add(t3) list.add(t2) list.add(t1) list.add(t0)

time Triangle_Puzzle02()

Pruning is good -- about 12 times as fast. But some really clever pruning is possible.

We have three equations

$t_0 + t_1 + t_2 + t_3 = s$

$t_3 + t_4 + t_5 + t_6 + t_7 = s$

$t_7 + t_8 + t_9 + t_0 = s$

We can also write down one other equation that is implied in the statement of the puzzle.

With a little bit of algebra we can milk these four equations for some important information.