//  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 const 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 const 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;
   const char     *IndexP;
   i32            NewValue;
   const 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;
}