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

 
       

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.