/*
  $Id: msq5.c,v 1.9 1999/12/30 00:32:48 issei Exp $
  */

/*
  Count up 5x5 magic square which central number is NUM
  You need to define NUM when compile

  ex)

  % cc -DNUM=12 -O3 msq5.c -o msq5

  */

#include <stdio.h>

#define SQ_SIZE	5
#define SUM	(SQ_SIZE*(SQ_SIZE*SQ_SIZE-1)/2)
#define	NUM0	(1UL << 24)
#define MASK	((1UL << (SQ_SIZE*SQ_SIZE)) - 1)

#ifndef NUM
#if __GNUC__
#warning "you need to define NUM when comple for answer"
#endif
#define	NUM	0
#endif

#define TARGET_BIT	(NUM0 >> NUM)
#define TARGET_NUM	NUM

typedef unsigned int BITS;

int	sq[SQ_SIZE][SQ_SIZE];
int	N;

BITS	C[SQ_SIZE];
BITS	L[SQ_SIZE];
BITS	D[2];

BITS 	TBL_SIZE;
BITS	sq_tab[1400];

int perm_tab[3][5] = {
    {1,2,0,3,4,},
    {1,2,0,4,3,},
    {1,3,0,4,2,},
};

void
debug(BITS n)
{
    int i;

    for(i=0 ; i<SQ_SIZE*SQ_SIZE ; ++i){
	if(n & (NUM0>>i)){
	    printf("%d ", i);
	}
    }
    printf("\n");
}

void
debug5(BITS n1, BITS n2, BITS n3, BITS n4, BITS n5)
{
    debug(n1);
    debug(n2);
    debug(n3);
    debug(n4);
    debug(n5);
}

void
print_sq()
{
    int i, j;

    for(i=0 ; i<SQ_SIZE ; ++i){
	for(j=0 ; j<SQ_SIZE ; ++j){
	    printf("%2d ", sq[i][j]);
	}
	printf("\n");
    }
    fflush(stdout);
}

/*
  return TRUE if n1 and n2 has only 1 common bit
 */
inline int
is_cross(BITS n1, BITS n2)
{
    register int n;
    register BITS bb;
    register BITS b;

    b = n1 & n2;

    n = 0;
    bb = NUM0;

    while(n < SQ_SIZE * SQ_SIZE){
	if(bb == b)
	    return 1;
	++n;
	bb >>= 1;
    }

    return 0;
}

int
bit2num(BITS b)
{
    register int n;
    register BITS bb;

    bb = NUM0;
    n = 0;

    while(n < SQ_SIZE * SQ_SIZE){
	if(bb & b)
	    return n;
	bb >>= 1;
	++n;
    }
    return -1;
}


void
sq_test(BITS *CC, BITS *LL, BITS *DD)
{
    int d[SQ_SIZE];
    int n;
    int i, j;
    int p;
    BITS b;

    n = 0;

    d[0] = TARGET_NUM;
    for(i=1 ; i<SQ_SIZE ; ){
	if(n != TARGET_NUM){
	    if(DD[0] & (NUM0 >> n)){
		d[i] = n;
		++i;
	    }
	}
	++n;
    }

    for(p = 0 ; p<3 ; ++p){
	sq[0][0] = d[perm_tab[p][0]];
	sq[1][1] = d[perm_tab[p][1]];
	sq[2][2] = d[perm_tab[p][2]];
	sq[3][3] = d[perm_tab[p][3]];
	sq[4][4] = d[perm_tab[p][4]];
    
	for(n=0 ; n < SQ_SIZE ; ++n){
	    b = NUM0 >> sq[n][n];
	    for(i=0 ; i<SQ_SIZE ; ++i)
		if(b & CC[i])
		    C[n] = CC[i];

	    for(i=0 ; i<SQ_SIZE ; ++i)
		if(b & LL[i])
		    L[n] = LL[i];
	}

	b = (L[0] & C[4]) | (L[1] & C[3]) | (L[2] & C[2]) | (L[3] & C[1]) | (L[4] & C[0]);
	if(b > DD[0])
	    continue;

	sq[0][4] = bit2num(L[0] & C[4]);
	sq[1][3] = bit2num(L[1] & C[3]);
	sq[2][2] = bit2num(L[2] & C[2]);
	sq[3][1] = bit2num(L[3] & C[1]);
	sq[4][0] = bit2num(L[4] & C[0]);

	if(sq[0][4] + sq[1][3] + sq[2][2] + sq[3][1] + sq[4][0] == SUM){
	    ++N;
	    if(N % 100 == 0){
		for(i=0 ; i<SQ_SIZE ; ++i)
		    for(j=0 ; j<SQ_SIZE ; ++j)
			sq[i][j] = bit2num(L[i] & C[j]);
	  
		printf("%d\n", N);
		print_sq();
		printf("\n");
	    }
	}
    }
}

int i0;

void
diagonal(BITS *CC,  BITS *LL)
{
    register int k0;
    BITS DD[2];

    for(k0 = 0 ; k0 < TBL_SIZE ; ++k0){
	DD[0] = sq_tab[k0];
	if(!(DD[0] & TARGET_BIT))
	    continue;

	if(!is_cross(DD[0], CC[0]) || !is_cross(DD[0], CC[1]) || !is_cross(DD[0], CC[2]) || !is_cross(DD[0], CC[3]) || !is_cross(DD[0], CC[4]))
	    continue;
	if(!is_cross(DD[0], LL[0]) || !is_cross(DD[0], LL[1]) || !is_cross(DD[0], LL[2]) || !is_cross(DD[0], LL[3]) || !is_cross(DD[0], LL[4]))
	    continue;
	sq_test(CC, LL, DD);
    }
}

void
line(BITS *CC)
{
    register int j0, j1, j2, j3;
    BITS LL[SQ_SIZE];
    BITS L01, L012, L0123;

    for(j0 = i0+1 ; j0 < TBL_SIZE ; ++j0){
	LL[0] = sq_tab[j0];
	if(!(LL[0] & TARGET_BIT))
	    continue;

	if(!is_cross(LL[0], CC[0]) || !is_cross(LL[0], CC[1]) || !is_cross(LL[0], CC[2]) || !is_cross(LL[0], CC[3]) || !is_cross(LL[0], CC[4]))
	    continue;

	for(j1 = 0 ; j1 < TBL_SIZE ; ++j1){
	    LL[1] = sq_tab[j1];

	    if(LL[0] & LL[1])
		continue;
	    if(!is_cross(LL[1], CC[0]) || !is_cross(LL[1], CC[1]) || !is_cross(LL[1], CC[2]) || !is_cross(LL[1], CC[3]) || !is_cross(LL[1], CC[4]))
		continue;
	    L01 = LL[0] | LL[1];

	    for(j2 = j1 + 1 ; j2 < TBL_SIZE ; ++j2){
		LL[2] = sq_tab[j2];

		if(L01 & LL[2])
		    continue;
		if(!is_cross(LL[2], CC[0]) || !is_cross(LL[2], CC[1]) || !is_cross(LL[2], CC[2]) || !is_cross(LL[2], CC[3]) || !is_cross(LL[2], CC[4]))
		    continue;

		L012 = L01 | LL[2];
		for(j3 = j2 + 1 ; j3 < TBL_SIZE ; ++j3){
		    LL[3] = sq_tab[j3];

		    if(L012 & LL[3])
			continue;
		    if(!is_cross(LL[3], CC[0]) || !is_cross(LL[3], CC[1]) || !is_cross(LL[3], CC[2]) || !is_cross(LL[3], CC[3]) || !is_cross(LL[3], CC[4]))
			continue;

		    L0123 = L012 | LL[3];
		    LL[4] = ~L0123 & MASK;
		    if(LL[4] < LL[3])
			continue;

		    if(!is_cross(LL[4], CC[0]) || !is_cross(LL[4], CC[1]) || !is_cross(LL[4], CC[2]) || !is_cross(LL[4], CC[3]) || !is_cross(LL[4], CC[4]))
			continue;
		    
		    diagonal(CC, LL);
		}
	    }
	}
    }
}

void
column()
{
    register int /*i0,*/ i1, i2, i3;
    BITS CC[SQ_SIZE];
    BITS C01, C012, C0123;

    for(i0 = 0 ; i0 < TBL_SIZE ; ++i0){
	CC[0] = sq_tab[i0];
	if(!(CC[0] & TARGET_BIT))
	    continue;

	for(i1 = 0 ; i1 < TBL_SIZE ; ++i1){
	    CC[1] = sq_tab[i1];

	    if(CC[0] & CC[1])
		continue;

	    C01 = CC[0] | CC[1];
	    for(i2 = i1 + 1 ; i2 < TBL_SIZE ; ++i2){
		CC[2] = sq_tab[i2];

		if(C01 & CC[2])
		    continue;

		C012 = C01 | CC[2];
		for(i3 = i2 + 1 ; i3 < TBL_SIZE ; ++i3){
		    CC[3] = sq_tab[i3];

		    if(C012 & CC[3])
			continue;

		    C0123 = C012 | CC[3];

		    CC[4] = ~C0123 & MASK;
		    if(CC[4] < CC[3])
			continue;

		    line(CC);
		}
	    }
	}
    }
}


int	sq_tmp[SQ_SIZE];

static void
mk_sqtab_sub(int size, int lvl, int idx, int sum)
{
    int i;
    int n;

    if(lvl == size){
	if(sum == SUM){
	    for(n=0 ; n < size ; ++n){
		sq_tab[TBL_SIZE] |= (NUM0 >> sq_tmp[n]);
	    }
	    ++TBL_SIZE;
	}
	return;
    }

    for(i=idx ; i < size * size - size + lvl + 1 ; ++i){
	sq_tmp[lvl] = i;
	mk_sqtab_sub(size, lvl+1, i+1, sum + i);
    }
}

void
mk_sqtab(int size)
{
    TBL_SIZE = 0;
    
    mk_sqtab_sub(size, 0, 0, 0);
}

int
main()
{
    int i;

    mk_sqtab(SQ_SIZE);
    for(i=0 ; i<TBL_SIZE ; ++i){
	printf("%d\t%08X\t", i, sq_tab[i]);
	debug(sq_tab[i]);
    }
    printf("table size=%d\n", TBL_SIZE);
    column();
    printf("found %d magic squares\n", N);

    return 0;
}