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