September 1998
We found the following solution using trial and error. Computers are good for that.
We used two different programs independently, and each found solutions.
One program repeatedly guessed six different integer values for the six vertices in the middle, then computed the other six from the solution of a system of linear equations. The integer at an outer vertex x is computed as x=(26+a+b-(c+d+e+f))/2, where c,d,e,f are the inner vertices closest to x, and a,b are the inner vertices farthest from x.
7 = (26 + 5+11 - (4+6+8+10)) /2
2 = (26 + 6+5 - (4+8+10+11))/2
It succeeded when the resulting twelve integers were exactly (1,2,...,12) in some order.
Another program used "hill climbing" techniques: place the twelve integers (1,2,...,12) on the vertices randomly, then repeatedly find and execute a "beneficial trade": a pair of integers such that when their positions are traded, some "figure of merit" is improved. In this case the figure of merit was the mean square error of the line sums, namely the sum, over the six lines, of the squares of the differences between their current line sum and the desired line sum of 26.
Both techniques have their place in solving problems; the first is faster for smaller problems, while the second is more robust for larger or more complicated problems.
Here are a couple of nice solutions sent in by a few of our early respondants:
Craig Arnold's solutionCraig Arnold's solution
This is a brute-force routine to find all possible solutions
(not
counting the rotated versions of existing solutions).
This routine doesn't distinguish between mirror-image solutions.
The total number of solutions found by this routine is 160
(about 1.4 seconds on a P100 with Linux - 0.122 seconds
if the output
is redirected), the first of which is:
1
/ \
9--10---2---5
\ / \ /
7 12
/ \ / \
8---4---3--11
\ /
6
Note on timing - Dos/Win/OS2 users will probably have to
use ftime
instead of gettimeofday (sys/timeb.h, and struct timeb).
The solution presented here works on Linux and HP-UX.
*/
#include <stdio.h>
#include <time.h>
#include <sys/time.h>
#include <unistd.h>
int main(int argc, char *argv[])
{
int point[12],
solutions = 0 ;
struct timeval start,
end ;
struct timezone tz ;
gettimeofday(&start, &tz) ;
for(point[ 0] = 1 ; point[ 0] < 3 ; point[ 0]++)
{
for(point[ 1] = 1 ; point[ 1] < 13 ; point[ 1]++)
{
if(point[ 1] != point[0])
{
for(point[ 2] = 1 ; point[ 2] < 13 ; point[
2]++)
{
if((point[ 2] != point[ 0]) &&
(point[ 2] != point[
1]))
{
for(point[ 3] = 1 ; point[ 3] <
13 ; point[ 3]++)
{
if((point[ 3]!= point[ 0])
&&
(point[
3] != point[ 1]) &&
(point[
3] != point[ 2]))
{
for(point[ 4] = 1 ;
point[ 4] < 13 ; point[ 4]++)
{
if((point[ 4]
!= point[ 0]) &&
(point[ 4] != point[ 1]) &&
(point[ 4] != point[ 2]) &&
(point[ 4] != point[ 3]) &&
(point[0] + point[1] + point[3] + point[4] == 26))
{
for(point[
5] = 1 ; point[ 5] < 13 ; point[ 5]++)
{
if((point[
5] != point[ 0]) &&
(point[ 5] != point[ 1]) &&
(point[ 5] != point[ 2]) &&
(point[ 5] != point[ 3]) &&
(point[ 5] != point[ 4]))
{
for(point[ 6] = 1 ; point[ 6] < 13 ; point[ 6]++)
{
if((point[ 6] != point[ 0]) &&
(point[ 6] != point[ 1]) &&
(point[ 6] != point[ 2]) &&
(point[ 6] != point[ 3]) &&
(point[ 6] != point[ 4]) &&
(point[ 6] != point[ 5]) &&
(point[2] + point[3] + point[5] + point[6] == 26))
{
for(point[ 7] = 1 ; point[ 7] < 13 ; point[ 7]++)
{
if((point[ 7] != point[ 0]) &&
(point[ 7] != point[ 1]) &&
(point[ 7] != point[ 2]) &&
(point[ 7] != point[ 3]) &&
(point[ 7] != point[ 4]) &&
(point[ 7] != point[ 5]) &&
(point[ 7] != point[ 6]))
{
for(point[ 8] = 1 ; point[ 8] < 13 ; point[ 8]++)
{
if((point[ 8] != point[ 0]) &&
(point[ 8] != point[ 1]) &&
(point[ 8] != point[ 2]) &&
(point[ 8] != point[ 3]) &&
(point[ 8] != point[ 4]) &&
(point[ 8] != point[ 5]) &&
(point[ 8] != point[ 6]) &&
(point[ 8] != point[ 7]) &&
(point[4] + point[5] + point[7] + point[8] == 26))
{
for(point[ 9] = 1 ; point[ 9] < 13 ; point[ 9]++)
{
if((point[ 9] != point[ 0]) &&
(point[ 9] != point[ 1]) &&
(point[ 9] != point[ 2]) &&
(point[ 9] != point[ 3]) &&
(point[ 9] != point[ 4]) &&
(point[ 9] != point[ 5]) &&
(point[ 9] != point[ 6]) &&
(point[ 9] != point[ 7]) &&
(point[ 9] != point[ 8]))
{
for(point[10] = 1 ; point[10] < 13 ; point[10]++)
{
if((point[10] != point[ 0]) &&
(point[10] != point[ 1]) &&
(point[10] != point[ 2]) &&
(point[10] != point[ 3]) &&
(point[10] != point[ 4]) &&
(point[10] != point[ 5]) &&
(point[10] != point[ 6]) &&
(point[10] != point[ 7]) &&
(point[10] != point[ 8]) &&
(point[10] != point[ 9]) &&
(point[ 6] + point[ 7] + point[ 9] + point[10] == 26))
{
for(point[11] = 1 ; point[11] < 13 ; point[11]++)
{
if((point[11] != point[ 0]) &&
(point[11] != point[ 1]) &&
(point[11] != point[ 3]) &&
(point[11] != point[ 4]) &&
(point[11] != point[ 2]) &&
(point[11] != point[ 5]) &&
(point[11] != point[ 6]) &&
(point[11] != point[ 7]) &&
(point[11] != point[ 8]) &&
(point[11] != point[ 9]) &&
(point[11] != point[10]) &&
(point[ 8] + point[ 9] + point[11] + point[ 0] == 26)&&
(point[10] + point[11] + point[ 1] + point[ 2] == 26))
{
gettimeofday(&end, &tz) ;
if(end.tv_usec < start.tv_usec)
{
end.tv_usec += 1000000 ;
end.tv_sec-- ;
}
printf("======== Solution %3d ============== time = %3d.%06d\n",
++solutions, end.tv_sec - start.tv_sec,end.tv_usec - start.tv_usec) ;
printf(" %2d\n\n", point[0]) ;
printf("%2d %2d %2d %2d\n\n", point[10], point[11],point[1],
point[2]) ;
printf(" %2d %2d\n\n", point[9], point[3])
;
printf("%2d %2d %2d %2d\n\n", point[8], point[7],point[5],
point[4]) ;
printf(" %2d\n\n", point[6])
;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
printf("=========================\n") ;
gettimeofday(&end, &tz) ;
if(end.tv_usec < start.tv_usec)
{
end.tv_usec += 1000000 ;
end.tv_sec-- ;
}
printf("Time: %3d.%06d\n", end.tv_sec - start.tv_sec,end.tv_usec
- start.tv_usec) ;
return(0) ;
}
Steve Rothman's solution
- Found all the combinations of 4 of the first 12 integers which sum to 26. Of the 495 possible (12 items taken 4 at a time), 33 sum to 26.
- For the set of 33, it then generated all the groups of 6 where each integer is used exactly twice. There are 514.
- It then searched those 514 for the cases where there is only one (or none) shared values been every pair of 6 sums. There are 20. I then randomly picked one of the 20, and in a few minutes (manually) juggled the placement on the star. The total effort was about an hour.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com