/*============================================================================
  sumsup.c -- solve Magic Hexagon -- xptaylor October 3, 2003
==============================================================================
Artificial Intelligence Memo No. 239 February 29, 1972

HAKMEM Item 49 -- Magic hexagon

There is a unique "magic hexagon" of side 3:

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

First discovered by Clifford W. Adams, who worked on the problem from 1910.
In 1957, he found a solution. (See Aug. 1963 Sci. Am., Math. Games.)
Other length sides are impossible.
==============================================================================
W. Radcliffe from the Isle of Man, U.K. is credited with the discovery
of the magic hexagon in 1895. This was not known to Adams and others who
have credited him with the discovery, perhaps independently.
==============================================================================
See also: http://mathworld.wolfram.com/MagicHexagon.html
     and: http://www.geocities.com/~harveyh/moremsqrs.htm
============================================================================*/

char used[20];
int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s;

void display()
{
  printf( "\n"
    "    %3i %3i %3i\n"
    "  %3i %3i %3i %3i\n"
    "%3i %3i %3i %3i %3i\n"
    "  %3i %3i %3i %3i\n"
    "    %3i %3i %3i\n",

           a,  b,  c,
         d,  e,  f,  g,
       h,  i,  j,  k,  l,
         m,  n,  o,  p,
           q,  r , s);
}

/* Create macros to build iterative context. To view the
   resultant expansions on stdio with gcc use the command:

    gcc -E sumsup.c

*/

#define LOOP(N)   for (N=1; N<20; N++) if (!used[N]){used[N]++
#define SETL(N,X) if ((N=(X))>0 && N<20 && !used[N]){used[N]++
#define NEXT(N)   used[N]--;}

/* solve hexagon and display all 12 symmetrical aspects of the solution */

/* since we know that the sum of 1 thru 19 is 190 and since we have 5 rows */
/* with the same sum then the magic sum must be 38 (190 divided by 5 sums) */

main()
{
  LOOP(a);            /* for a 1-19 no exceptions */
   LOOP(b);           /* for b 1-19 except a ...  */
    SETL(c,38-a-b);   /* set c to 38-a-b and check uniqueness */
     LOOP(d);         /* for d 1-19 except a,b,c ...          */
      SETL(h,38-a-d); /* set h to 38-a-d and check uniqueness */
       LOOP(e);       /* for e 1-19 except a,b,c,d,h ...      */
        LOOP(f);
         SETL(g,38-d-e-f);
          SETL(l,38-c-g);
           LOOP(i);
            SETL(m,38-b-e-i);
             SETL(q,38-h-m);
              LOOP(j);
               SETL(k,38-h-i-j-l);
                SETL(n,38-c-f-j-q);
                 SETL(r,38-d-i-n);
                  SETL(o,38-g-k-r);
                   SETL(p,38-m-n-o);
                    SETL(s,38-l-p);
                     display();      /* display the solution */
                    NEXT(s);
                   NEXT(p);
                  NEXT(o);
                 NEXT(r);
                NEXT(n);
               NEXT(k);
              NEXT(j);
             NEXT(q);
            NEXT(m);
           NEXT(i);
          NEXT(l);
         NEXT(g);
        NEXT(f);
       NEXT(e);
      NEXT(h);
     NEXT(d);
    NEXT(c);
   NEXT(b);
  NEXT(a);
}