Magic hexagon Explained

 

The numbers in any row of the hexagon above sum to 38, e.g.   9+14+15,   11+1+7+19,   3+7+5+8+15, making this a magic hexagon (by analogy to magic squares). If you already know why this size is the only possible size (outside of the trivial single digit "hexagon"), but aren't content to just take someone's word that no other arrangement (not counting rotations and/or reflections) of integers 1 through 19 is magic--then the C++ program below is for you. Tom Ace return to Tom's home page

//  magic hexagon   T. Ace   18 November 2002

#include <stdio.h>

typedef int           i32;

/*   octal indices to the Vals[] and DeriveRules[] arrays:

         variable              contingent                all

        --  --  --             13  14  10             13  14  10
      --  01  02  03         12  --  --  --         12  01  02  03
    --  04  05  06  07     11  --  --  --  --     11  04  05  06  07
      --  --  --  --         15  22  23  16         15  22  23  16
        --  --  --             17  21  20             17  21  20

(I'm not fond of octal; it's just convenient in C/C++ char strings.)  */

static const i32   VAR_COUNT = 7;

// vary the values in positions numbered 1 through VAR_COUNT; all other 
// values are contingent on those, derived in sequence by these rules:

static char   *DeriveRules[20] = {
   (char *) NULL,     // 00 isn't used
   (char *) NULL,     // 01 is not derived
   (char *) NULL,     // 02 is not derived
   (char *) NULL,     // 03 is not derived
   (char *) NULL,     // 04 is not derived
   (char *) NULL,     // 05 is not derived
   (char *) NULL,     // 06 is not derived
   (char *) NULL,     // 07 is not derived
   "\03\07",          // 10   Vals[010] = 38 - Vals[003] - Vals[007]
   "\04\05\06\07",    // 11   ... 
   "\01\02\03",       // 12  
   "\11\12",          // 13
   "\10\13",          // 14
   "\14\01\04",       // 15
   "\14\02\06",       // 16
   "\11\15",          // 17
   "\07\16",          // 20
   "\17\20",          // 21
   "\12\04\21",       // 22
   "\03\06\21"        // 23
};

// CheckRows[] describes the rows whose sums were not already 
// guaranteed by the formulas encoded in DeriveRules[]

static char  *CheckRows[] =
{
   "\15\22\23\16",    // Vals[015] + Vals[022] + Vals[023] + Vals[016] == 38 
   "\13\01\05\23\20", // ...
   "\10\02\05\22\17",
   (char *) NULL      // end marker
};

class Bits32 {
   i32      Data;

public:
   void     Clear()        { Data = 0; }
   void     Set  (i32 N)   { Data |= 1 << N; }
   void     Reset(i32 N)   { Data &= ~(1 << N); }
   bool     Test (i32 N)   { return (Data >> N) & 1; }
};

static i32     Vals[20];
static Bits32  ValsTaken;

static void PrintConfig()
{
   printf("\n"
          "      %3d   %3d   %3d\n"
          "   %3d   %3d   %3d   %3d\n"
          "%3d   %3d   %3d   %3d   %3d\n"
          "   %3d   %3d   %3d   %3d\n"
          "      %3d   %3d   %3d\n\n\n",
          Vals[013], Vals[014], Vals[010],
          Vals[012], Vals[001], Vals[002], Vals[003],
          Vals[011], Vals[004], Vals[005], Vals[006], Vals[007],
          Vals[015], Vals[022], Vals[023], Vals[016],
          Vals[017], Vals[021], Vals[020]);
}

static void InitNVals(i32 N)
{
   // set up the initial configuration of the first N values

   ValsTaken.Clear();
   do {
      Vals[N] = N;
      ValsTaken.Set(N);
   } while (--N > 0);
}

static bool NextNVals(i32 N)
{
   // generate the next configuration of the first N values;
   // return 0 if there are no more

   i32  V = Vals[N];
   ValsTaken.Reset(V);
   do {
      if (V < 19) {
         V++;
      }
      else {
         if (N == 1 || !NextNVals(N - 1)) return 0;
         V = 1;
      }
   } while (ValsTaken.Test(V));
   ValsTaken.Set(V);
   Vals[N] = V;
   return 1;
}

int main(int argc,char **argv)
{
   i32            Count;
   i32            I;
   i32            Index;
   char           *IndexP;
   i32            NewValue;
   char           **Row;
   i32            Sum;
   Bits32         Taken;

   InitNVals(VAR_COUNT);
   Count = 0;

   do {
      Taken = ValsTaken;

      // derive the (19 - VAR_COUNT) contingent values, if possible

      for (I = VAR_COUNT; ++I <= 19; ) {
         NewValue = 38;
         for (IndexP = DeriveRules[I]; (Index = *IndexP) != '\0'; IndexP++) {
            NewValue -= Vals[Index];
         }
         if (NewValue < 1 || NewValue > 19) goto NextConfig;
         if (Taken.Test(NewValue)) goto NextConfig;
         Taken.Set(NewValue);
         Vals[I] = NewValue;
      }

      // DeriveRules guarantees the correct sum in most of the rows; 
      // we now verify the sums in the rows that weren't used in derivations

      for (Row = CheckRows; (IndexP = *Row) != NULL; Row++) {
         Sum = 0;
         for ( ; (Index = *IndexP) != '\0'; IndexP++) {
            Sum += Vals[Index];
         }
         if (Sum != 38) goto NextConfig;
      }

      // magic config found

      PrintConfig();
      Count++;

      NextConfig:;
   } while (NextNVals(VAR_COUNT));

   printf("\n %d magic configurations found   "
          "(expected:  12 rotations/reflections)\n",
          Count);

   return 0;
}

 LINK:
magic hexagon

 http://www.minortriad.com/magichex.html