# Code Solution for the Magic Hexagon

A magic hexagon is a hexagon where every row and every diagonal add up to the same value. In this case the value is 38. Each number from 1 to 19 must be used exactly once.

This image shows a solution but I want a program that derives this result.

What's the most effecient way of computing theses values? The length of code doesn't matter but I suppose the shorter the better.

-
I suppose it's also a requirement that each of the values 1-19 be used exactly once? – primo Jun 10 '12 at 11:16
Ya sorry I left that out by accident. – PriestVallon Jun 10 '12 at 11:19
There are 19 variables and 15 linear constraints, so the most efficient way of computing them is likely to be to convert the system of equations into reduced row echelon form, identify 4 independent variables which you can use for a basis, and enumerate the 93024 combinations checking for ones which use 1-19 once each. – Peter Taylor Jun 10 '12 at 15:50
@Peter: Some of the constraints are redundant, so there are actually 7 independent variables. – Keith Randall Jun 11 '12 at 0:25
How might the length of code not matter, and meanwhile the shorter the better? What is meant with `most efficient`? Lowest network traffic, size on HDD, size in RAM or highest speed? If highest speed: Shall we assume a multi core system, or a single CPU? – user unknown Jun 12 '12 at 1:45

## C++

Uses some macros to enumerate the possible values. (A-S, assigned lexicographically in the problem image.) `m` is a bitmask of values that have been used so far.

``````#include <stdio.h>
#define LOOP(V) for(int V=1;V<20;V++){if(m&1<<V){m&=~(1<<V);
#define ENDLOOP(V) m|=1<<V;}}
#define SET(V,e) int V=e;if(m&1<<V){m&=~(1<<V);
#define UNSET(V) m|=1<<V;}
int main() {
int m=1048574;
LOOP(A);
LOOP(B);
SET(C,38-A-B);
LOOP(D);
SET(H,38-A-D);
LOOP(G);
SET(L,38-C-G);
LOOP(E);
SET(F,38-D-E-G);
LOOP(I);
SET(M,38-B-E-I);
SET(Q,38-H-M);
LOOP(J);
SET(N,38-C-F-J-Q);
SET(R,38-D-I-N);
SET(S,38-Q-R);
SET(P,38-L-S);
SET(K,38-B-F-P);
SET(O,38-M-N-P);
printf("%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d\n",A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S);
UNSET(O);
UNSET(K);
UNSET(P);
UNSET(S);
UNSET(R);
UNSET(N);
ENDLOOP(J);
UNSET(Q);
UNSET(M);
ENDLOOP(I);
UNSET(F);
ENDLOOP(E);
UNSET(L);
ENDLOOP(G);
UNSET(H);
ENDLOOP(D);
UNSET(C);
ENDLOOP(B);
ENDLOOP(A);
}
``````

Runs in 30msec and generates the following:

``````3 17 18 19 7 1 11 16 2 5 6 9 12 4 8 14 10 13 15
3 19 16 17 7 2 12 18 1 5 4 10 11 6 8 13 9 14 15
9 11 18 14 6 1 17 15 8 5 7 3 13 4 2 19 10 12 16
9 14 15 11 6 8 13 18 1 5 4 10 17 7 2 12 3 19 16
10 12 16 13 4 2 19 15 8 5 7 3 14 6 1 17 9 11 18
10 13 15 12 4 8 14 16 2 5 6 9 19 7 1 11 3 17 18
15 13 10 14 8 4 12 9 6 5 2 16 11 1 7 19 18 17 3
15 14 9 13 8 6 11 10 4 5 1 18 12 2 7 17 16 19 3
16 12 10 19 2 4 13 3 7 5 8 15 17 1 6 14 18 11 9
16 19 3 12 2 7 17 10 4 5 1 18 13 8 6 11 15 14 9
18 11 9 17 1 6 14 3 7 5 8 15 19 2 4 13 16 12 10
18 17 3 11 1 7 19 9 6 5 2 16 14 8 4 12 15 13 10
``````

The 4th line is the example solution.

-
It's interesting that all of the solutions are mirrors and rotations of each other. I suppose that implies that there is only one unique solution where the values add to 38. The question I have, is if there are any solutions with a sum value other than 38? – primo Jun 11 '12 at 7:10
There aren't - just replace all the 38s with a variable in my code and loop over it. – Keith Randall Jun 11 '12 at 14:19
@primo It's not possible for a magic square/hexagon/whatever to have multiple solutions with different sums. Given the shape and the set of numbers, the required sum is fixed. – breadbox Jun 12 '12 at 1:31
@primo, to expand on breadbox's comment, each cell participates in three lines: one East-West, one NorthEast-SouthWest, and one NorthWest-SouthEast. Therefore the total of the 15 lines is `sum[1..19]*3`, so each line sums to `(19*20/2)*(3/15) = 38`. – Peter Taylor Jun 12 '12 at 8:13
@PeterTaylor Thanks, that makes perfect sense. – primo Jun 12 '12 at 8:19
show 2 more comments

So this somewhat ugly code crashes spectacularly in the REPL (its own words!), but compiles and executes fine.

Uppercase letters indicate values, I pick from the set to iterate over them. Lowercase letters are generated. z = 38 - X - Y for example, and e = 38 - X - A. With e and J we get n and so on.

``````/**
X Y z
A B c d
e f g h i
J k l m
n o p
*/
object MagicHexagon extends App {

val set =(1 to 19)toSet

// row 1
for (x <- set;
y <-(set - x);
z = 38 - y - x;
dummy <- ((set - x - y) -- (set - x - y - z));
rest1=(set - x - y - z);
a <- rest1;
e = 38 - x - a;
dummy2 <- ((rest1 - a) -- (rest1 - a - e));
j <- rest1 - a - e;
n = 38 - e - j;
dummy3 <- ((rest1 - a - e - j) -- (rest1 - a - e - j - n));
b <- rest1 - a - e - n;
rest2=(rest1 - a - e - j - n - b);
f = 38 - y - b - j;
dummy4 <- ((rest2) -- (rest2 - f));
c <- rest2 - f;
d = 38 - a - b - c;
dummy5 <- ((rest2 - f - c) -- (rest2 - f - c - d));
i = 38 - z - d;
dummy6 <- ((rest2 - f - c - d) -- (rest2 - f - c - d - i));
rest3 = rest2 - f - c - d - i;
g <- rest3;
h = 38 - e - f - g - i;
dummy7 <- ((rest3 - g) -- (rest3 - g - h));
k = 38 - z - c - g - n;
dummy8 <- ((rest3 - g - h) -- (rest3 - g - h - k));
o = 38 - a - f - k;
rest4 = (rest3 - g - h - k - o);
dummy9 <- ((rest3 - g - h - k) -- rest4);
m = 38 - y - c - h;
dummyA <- (rest4 -- (rest4 - m));
p = 38 - i - m;
dummyB <- (rest4 - m) -- (rest4 - m - p);
l = 38 - j - k - m;
dummyC <- (rest4 - m - p) -- (rest4 - m - p - l);
buf = List( List("  ",x,y,z), List(" ",a,b,c,d), List("",e,f,g,h,i), List(" ",j,k,l,m), List("  ",n,o,p))) {
println (buf.map (_.mkString ("", ", ", "")).mkString ("\n"))
println ()
}
}
``````

The dummy-variables are a kind of hack to allow the loop to terminate prematurely if a generated value doesn't match one of the left values from the set, especially 0 or negative values must be avoided.

Result:

``````scala MagicHexagon
, 10, 12, 16
, 13, 4, 2, 19
, 15, 8, 5, 7, 3
, 14, 6, 1, 17
, 9, 11, 18

, 10, 13, 15
, 12, 4, 8, 14
, 16, 2, 5, 6, 9
, 19, 7, 1, 11
, 3, 17, 18

, 9, 11, 18
, 14, 6, 1, 17
, 15, 8, 5, 7, 3
, 13, 4, 2, 19
, 10, 12, 16

, 9, 14, 15
, 11, 6, 8, 13
, 18, 1, 5, 4, 10
, 17, 7, 2, 12
, 3, 19, 16

, 3, 19, 16
, 17, 7, 2, 12
, 18, 1, 5, 4, 10
, 11, 6, 8, 13
, 9, 14, 15

, 3, 17, 18
, 19, 7, 1, 11
, 16, 2, 5, 6, 9
, 12, 4, 8, 14
, 10, 13, 15

, 18, 11, 9
, 17, 1, 6, 14
, 3, 7, 5, 8, 15
, 19, 2, 4, 13
, 16, 12, 10

, 18, 17, 3
, 11, 1, 7, 19
, 9, 6, 5, 2, 16
, 14, 8, 4, 12
, 15, 13, 10

, 16, 19, 3
, 12, 2, 7, 17
, 10, 4, 5, 1, 18
, 13, 8, 6, 11
, 15, 14, 9

, 16, 12, 10
, 19, 2, 4, 13
, 3, 7, 5, 8, 15
, 17, 1, 6, 14
, 18, 11, 9

, 15, 13, 10
, 14, 8, 4, 12
, 9, 6, 5, 2, 16
, 11, 1, 7, 19
, 18, 17, 3

, 15, 14, 9
, 13, 8, 6, 11
, 10, 4, 5, 1, 18
, 12, 2, 7, 17
, 16, 19, 3
``````

Runs in 17s on 7y'o' Laptop.

-

It takes 121 seconds to run and is incredibly inefficient.

Any tips to improve efficiency would be appreciated instead of down votes.

## C#

``````static void Main(string[] args)
{
DateTime time = DateTime.Now;
int n1 = 0, n2 = 0, n3 = 0, n4 = 0, n5 = 0, n6 = 0, n7 = 0, n8 = 0, n9 = 0, n10 = 0, n11 = 0, n12 = 0, n13 = 0, n14 = 0, n15 = 0, n16 = 0, n17 = 0, n18 = 0, n19 = 0;

List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
List<int> c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19;

c1 = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };

for (int x1 = 0; x1 < c1.Count; x1++ )
{
n1 = c1[x1];
c2 = c1.Select(i => i).ToList();
c2.Remove(n1);
for (int x2 = 0; x2 < c2.Count; x2++)
{
n2 = c2[x2];
c3 = c2;
c3 = c2.Select(i => i).ToList();
c3.Remove(n2);
for (int x3 = 0; x3 < c3.Count; x3++)
{
n3 = c3[x3];

if (n1 + n2 + n3 == 38)
{
c4 = c3.Select(i => i).ToList();
c4.Remove(n3);
for (int x4 = 0; x4 < c4.Count; x4++)
{
n4 = c4[x4];
c5 = c4.Select(i => i).ToList();
c5.Remove(n4);
for (int x5 = 0; x5 < c5.Count; x5++)
{
n5 = c5[x5];
c6 = c5.Select(i => i).ToList();
c6.Remove(n5);
for (int x6 = 0; x6 < c6.Count; x6++)
{
n6 = c6[x6];
c7 = c6.Select(i => i).ToList();
c7.Remove(n6);
for (int x7 = 0; x7 < c7.Count; x7++)
{
n7 = c7[x7];

if(n4 + n5 + n6 + n7 == 38)
{
c8 = c7.Select(i => i).ToList();
c8.Remove(n7);
for (int x8 = 0; x8 < c8.Count; x8++)
{
n8 = c8[x8];

if(n1 + n4 + n8 == 38)
{
c9 = c8.Select(i => i).ToList();
c9.Remove(n8);
for (int x9 = 0; x9 < c9.Count; x9++)
{
n9 = c9[x9];
c10 = c9.Select(i => i).ToList();
c10.Remove(n9);

for (int x10 = 0; x10 < c10.Count; x10++)
{
n10 = c10[x10];
c11 = c10.Select(i => i).ToList();
c11.Remove(n10);
for (int x11 = 0; x11 < c11.Count; x11++)
{
n11 = c11[x11];
c12 = c11.Select(i => i).ToList();
c12.Remove(n11);

for (int x12 = 0; x12 < c12.Count; x12++)
{
n12 = c12[x12];

if(n8 + n9 + n10 + n11 + n12 == 38)
{
if(n3 + n7 + n12 == 38)
{
c13 = c12.Select(i => i).ToList();
c13.Remove(n12);
for (int x13 = 0; x13 < c13.Count; x13++)
{
n13 = c13[x13];

if (n2 + n5 + n9 + n13 == 38)
{
c14 = c13.Select(i => i).ToList();
c14.Remove(n13);
for (int x14 = 0; x14 < c14.Count; x14++)
{
n14 = c14[x14];
c15 = c14.Select(i => i).ToList();
c15.Remove(n14);
for (int x15 = 0; x15 < c15.Count; x15++)
{
n15 = c15[x15];
c16 = c15.Select(i => i).ToList();
c16.Remove(n15);

for (int x16 = 0; x16 < c16.Count; x16++)
{
n16 = c16[x16];

if (n13 + n14 + n15 + n16 == 38)
{
if (n2 + n6 + n11 + n16 == 38)
{
c17 = c16.Select(i => i).ToList();
c17.Remove(n16);
for (int x17 = 0; x17 < c17.Count; x17++)
{
n17 = c17[x17];

if (n3 + n6 + n10 + n14 + n17 == 38)
{
c18 = c17.Select(i => i).ToList();
c18.Remove(n17);
for (int x18 = 0; x18 < c18.Count; x18++)
{
n18 = c18[x18];

if (n4 + n9 + n14 + n18 == 38)
{
if (n7 + n11 + n15 + n18 == 38)
{
c19 = c18.Select(i => i).ToList();
c19.Remove(n18);
n19 = c19[0];
if(n17 + n18 + n19 == 38)
{
if(n1 + n5 + n10 + n15 + n19 == 38)
{
if(n12 + n16 + n19 == 38)
{
Console.Out.WriteLine("Success");
Console.Out.WriteLine(n1);
Console.Out.WriteLine(n2);
Console.Out.WriteLine(n3);
Console.Out.WriteLine(n4);
Console.Out.WriteLine(n5);
Console.Out.WriteLine(n6);
Console.Out.WriteLine(n7);
Console.Out.WriteLine(n8);
Console.Out.WriteLine(n9);
Console.Out.WriteLine(n10);
Console.Out.WriteLine(n11);
Console.Out.WriteLine(n12);
Console.Out.WriteLine(n13);
Console.Out.WriteLine(n14);
Console.Out.WriteLine(n15);
Console.Out.WriteLine(n16);
Console.Out.WriteLine(n17);
Console.Out.WriteLine(n18);
Console.Out.WriteLine(n19);
}

}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}

}
}
}
}
Console.Out.WriteLine(DateTime.Now - time);
}
``````
-
It seems to me that you are simply brute-forcing every possible solution. In actuality, once you have a few (at best, seven) of the numbers solved, the rest of the hexagon can be solved directly, without looping through different possibilities. You then only have to loop through the different possibilities for those seven "squares." – PhiNotPi Jun 12 '12 at 1:07