023: Magic Hexagon

/*==========================================================================
  sumsup.c -- solve Magic Hexagon -- xptaylor@hotmail.com -- October 11, 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
          http://www.geocities.com/~harveyh/moremsqrs.htm
          http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
          http://www.4c.ucc.ie/~tw/csplib/prob/prob023/links.html
  ==========================================================================*/

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 expanded C source
   with gcc use the command:

    gcc -E sumsup.c

*/

#define LOOP(N)   for (N=1; N<20; N++) if (!used[N]){used[N]++
#define LSET(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     */
main()
{ LOOP(a);                     /* for a 1-19 no exceptions                  */
   LOOP(c);                    /* for c 1-19 except a                       */
    LSET(b,38-a-c);            /* set b to 38-a-c and check uniqueness      */
     LOOP(l);                  /* for l 1-19 except a,c,b                   */
      LSET(g,38-c-l);          /* set g to 38-c-l and check uniqueness      */
       LOOP(s);                /* for s 1-19 except a,c,b,l,g               */
        LSET(p,38-l-s);        /* set p to 38-l-s and check uniqueness      */
         LOOP(q);              /* for q 1-19 except a,c,b,l,g,s,p           */
          LSET(r,38-s-q);      /* set r to 38-s-q and check uniqueness      */
           LOOP(h);            /* for h 1-19 except a,c,b,l,g,s,p,q,r       */
            LSET(m,38-q-h);    /* ... and so on until a solution is found.  */
             LSET(d,38-a-h);
              LOOP(e);
               LSET(f,38-d-e-g); 
                LSET(k,38-b-f-p);
                 LSET(o,38-g-k-r);
                  LSET(n,38-m-o-p);
                   LSET(i,38-d-n-r);
                    LSET(j,38-a-e-o-s); /* Why is this 'if' always true?    */
                     if (38==c+f+j+n+q && 38==h+i+j+k+l && 38==b+e+i+m)
                      display();        /* show each aspect of the solution */
                    NEXT(j);
                   NEXT(i);
                  NEXT(n);
                 NEXT(o);  /*  The solution has 15 simultaneous sums formed */
                NEXT(k);  /*  as follows: (1+2+3+4+5+6+7+8+9+...+19)/5 = 38 */
               NEXT(f);  /* = a+b+c = d+e+f+g = h+i+j+k+l = m+n+o+p = q+r+s */
              NEXT(e);  /*  = a+d+h = b+e+i+m = c+f+j+n+q = g+k+o+r = l+p+s */
             NEXT(d);  /*   = c+g+l = b+f+k+p = a+e+j+o+s = d+i+n+r = h+m+q */
            NEXT(m);
           NEXT(h);  /* Only 12 of the sums are generated by this program,  */
          NEXT(r);  /*  yet all 15 are correct regardless of the ordering   */
         NEXT(q);  /*   of variables being looped and set to a correct sum. */
        NEXT(p);
       NEXT(s);  /* Can anyone help explain why this always works? Why is   */
      NEXT(g);  /*  the if always true when the 12 other sums are correct?  */
     NEXT(l); 
    NEXT(b);  /* Can we prove that it is safe to leave the 'if' out of the  */
   NEXT(c);  /*  program or, should we leave it in for completeness? It is  */
  NEXT(a);  /*   only executed 12 times and doesn't slow the process.       */
}