6
\$\begingroup\$

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.

Hexagon

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

Your challenge is to solve the magic hexagon as fast as possible. You must derive the result yourself, no hard-coding.

\$\endgroup\$
6
  • \$\begingroup\$ I suppose it's also a requirement that each of the values 1-19 be used exactly once? \$\endgroup\$
    – primo
    Jun 10, 2012 at 11:16
  • \$\begingroup\$ Ya sorry I left that out by accident. \$\endgroup\$ Jun 10, 2012 at 11:19
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jun 10, 2012 at 15:50
  • 2
    \$\begingroup\$ @Peter: Some of the constraints are redundant, so there are actually 7 independent variables. \$\endgroup\$ Jun 11, 2012 at 0:25
  • \$\begingroup\$ 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? \$\endgroup\$ Jun 12, 2012 at 1:45

4 Answers 4

7
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ 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? \$\endgroup\$
    – primo
    Jun 11, 2012 at 7:10
  • \$\begingroup\$ There aren't - just replace all the 38s with a variable in my code and loop over it. \$\endgroup\$ Jun 11, 2012 at 14:19
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – breadbox
    Jun 12, 2012 at 1:31
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ Jun 12, 2012 at 8:13
  • \$\begingroup\$ @PeterTaylor Thanks, that makes perfect sense. \$\endgroup\$
    – primo
    Jun 12, 2012 at 8:19
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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);
            Console.In.Read();
    }
\$\endgroup\$
1
  • 3
    \$\begingroup\$ 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." \$\endgroup\$
    – PhiNotPi
    Jun 12, 2012 at 1:07
0
\$\begingroup\$

39 ms, 363k recurrence calls. Greetings Lukasz.

Java code:

package game_numbers;

public class Numbers {
    public static int counter=0;


public static byte get_next(byte[] numbers)
    {
    byte elem=0;
    int i=0;
    do
        {
        elem=numbers[i];
        i++;
        }
    while(elem==0 && i<19) ;
    return elem; 
    }

// main recur alg

public static boolean findNext(byte[] gameBoard, byte[] numbers)
   {
    boolean found = false;
    byte tmpNumbers[] = copyNumbers(numbers);  
    byte elem = get_next(tmpNumbers);

    do
        {
        counter++;
        tmpNumbers = removeFromNumbers(tmpNumbers, elem);
        gameBoard = putOnBoard(gameBoard,elem);
        //printBoard(gameBoard);
        if(match(gameBoard))
            {
            numbers = removeFromNumbers(numbers, elem);
            if(win(numbers)) 
                found=true;
            else
                {
                found=findNext(gameBoard, numbers);
                if( !found)
                    {
                    gameBoard = removeFromBoard(gameBoard);
                    numbers = addToNumbers(numbers, elem);
                    }
                }
            }
        else
            removeFromBoard(gameBoard);

        elem=get_next(tmpNumbers);     
        }
    while (elem!=0 && !found) ;

return found; 
}



private static byte[] addToNumbers(byte[] numbers1, byte elem) {
    numbers1[elem-1] = elem;
    return numbers1;
}

private static byte[] copyNumbers(byte[] numbers) {
byte[] newNumbers={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

for(byte i=0; i<19; i++)
    newNumbers[i] = numbers[i];

return newNumbers;
}

private static void printBoard(byte[] gameBoard) {
    System.out.println();
    for(byte temp: gameBoard)
    {
    System.out.print(temp + " ");       
    }

}

private static boolean win(byte[] numbers) {

if( get_next(numbers) == 0)
    return true;
else
    return false;
}

private static byte[] removeFromNumbers(byte[] numbers1, byte elem) {
    numbers1[elem-1] = 0;
    return numbers1;
}

private static byte[] removeFromBoard(byte[] gameBoard) {
byte i=0;
while( gameBoard[i] > 0 )
    i++;
gameBoard[i-1] = 0;
return gameBoard;
}

//evaluation function
private static boolean match(byte[] gameBoard) {

byte SUM = 38;

// mapping of permutation to board game

//spiral from outside - quick 300k
byte a=gameBoard[0];
byte b=gameBoard[1];
byte c=gameBoard[2];
byte g=gameBoard[3];
byte l=gameBoard[4];
byte p=gameBoard[5];
byte t=gameBoard[6];
byte s=gameBoard[7];
byte r=gameBoard[8];
byte m=gameBoard[9];
byte h=gameBoard[10];
byte d=gameBoard[11];
byte e=gameBoard[12];
byte f=gameBoard[13];
byte k=gameBoard[14];
byte o=gameBoard[15];
byte n=gameBoard[16];
byte i=gameBoard[17];
byte j=gameBoard[18];

/*     /a|b|c\
      /d|e|f|g\ 
     /h|i|j|k|l\
      \m|n|o|p/ 
       \r|s|t/
*/




if( checkVeriables3(a,b,c) == SUM)
    if (checkVeriables4(d,e,f,g) == SUM)
        if (checkVeriables5(h,i,j,k,l) == SUM)
            if (checkVeriables4(m,n,o,p) == SUM)
                if (checkVeriables3(r,s,t) == SUM)
                    if (checkVeriables3(a,d,h) == SUM)
                        if (checkVeriables4(b,e,i,m) == SUM)
                            if (checkVeriables5(c,f,j,n,r) == SUM)
                                if (checkVeriables4(g,k,o,s) == SUM)
                                    if (checkVeriables3(l,p,t) == SUM)
                                        if (checkVeriables3(c,g,l) == SUM)
                                            if (checkVeriables4(b,f,k,p) == SUM)
                                                if (checkVeriables5(a,e,j,o,t) == SUM)
                                                    if (checkVeriables4(d,i,n,s) == SUM)
                                                        if (checkVeriables3(h , m , r) == SUM) return true;
return false;

}

private static byte checkVeriables5(byte h, byte i, byte j, byte k, byte l) {
byte SUM=38;
if (h==0) return SUM;
if (i==0) return SUM;
if (j==0) return SUM;
if (k==0) return SUM;
if (l==0) return SUM;

SUM=(byte)(h+i+j+k+l);

return SUM;
}

private static byte checkVeriables4(byte h, byte i, byte j, byte k) {
    byte SUM=38;
    if (h==0) return SUM;
    if (i==0) return SUM;
    if (j==0) return SUM;
    if (k==0) return SUM;

    SUM=(byte)(h+i+j+k);

    return SUM;
}

private static byte checkVeriables3(byte h, byte i, byte j) {
    byte SUM=38;
    if (h==0) return SUM;
    if (i==0) return SUM;
    if (j==0) return SUM;

    SUM=(byte)(h+i+j);

    return SUM;
}

private static byte[] putOnBoard(byte[] gameBoard, byte elem) {
    byte i=0;
    while( gameBoard[i] > 0 )
        i++;
    gameBoard[i] = elem;
    return gameBoard;

}

public static void main(String[] args) 
    {

    byte[] availableNumbers={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};  
    byte[] gameBoard={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    boolean found = false;
    long time = System.currentTimeMillis();

    while (!found)
        {
        found = findNext(gameBoard,availableNumbers);           
        }       

    long time1 = System.currentTimeMillis();
    for(byte temp: gameBoard)
        System.out.print(temp + " ");       

    System.out.println();
    System.out.println("runing time:" + (time1-time));
    System.out.println("number of recurrence calls:" + counter);
    }
}
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.