# MTHSC 360 Triangle Puzzle

## 3652 days ago by warner

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.
0
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,
0
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
0
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; 0 5 7 9 8 2 6 4 3 1 by permuting the interior elements on the left side; 0 8 5 7 9 1 3 4 6 2 by permuting the interior elements on the right side; 0 7 9 8 5 1 3 4 6 2 by permuting the interior elements on the bottom; 0 7 5 8 9 1 6 3 4 2 or by combining any of these four operations. 0 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 a 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. 0 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 = st_3 + t_4 + t_5 + t_6 + t_7 = st_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. 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, 0 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 0 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;

0

5     7

9           8

2   6   4   3   1

by permuting the interior elements on the left side;

0

8     5

7           9

1   3   4   6   2

by permuting the interior elements on the right side;

0

7     9

8           5

1   3   4   6   2

by permuting the interior elements on the bottom;

0

7     5

8           9

1   6   3   4   2

or by combining any of these four operations.

0

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

a

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.