#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef enum status { BOARD_INCOMP, BOARD_BAD, BOARD_GOOD } status;

#define HEIGHT 5 // Odd number
#define STARTW 3 // Width of first line < HEIGHT

#define WIDTH  ((2*HEIGHT)-1)
#define PIECES (HEIGHT*HEIGHT-STARTW*(STARTW-1))
#define SEEKED ((PIECES*(PIECES+1))/(2*HEIGHT))

//#define EXITON1SOL exit(0);

#ifdef EXITON1SOL
#define FINALEXITCODE 1
#else
#define FINALEXITCODE 0
#define EXITON1SOL  
#endif

status CheckLine(int i, int board[HEIGHT][WIDTH])
{
   int j, sum=0, val, *b;	
   status stat = BOARD_GOOD;

   b=&board[i][0];

   for(j=0;j<WIDTH;++j)
   {
      if((val = b[j]) < 0) stat=BOARD_INCOMP; 
      else { sum += val; }
   }
   if(sum != SEEKED && stat != BOARD_INCOMP) return BOARD_BAD;
   else if(sum > SEEKED) return BOARD_BAD;
   else if(sum == SEEKED && stat != BOARD_INCOMP) return BOARD_GOOD;
   return stat;
}

status CheckDiags(int ci, int cj, int board[HEIGHT][WIDTH])
{
   int i, j, sum, val, s;
   status lstat, stat = BOARD_GOOD;
   
   for (s=-1; s<=1; s+=2)
   {
      j = cj + s*ci;
      sum = 0; lstat = BOARD_GOOD;

      for(i=0;i<HEIGHT;++i)
      {
         if(i<0||i>=HEIGHT||j<0||j>=WIDTH) ;
         else if((val = board[i][j]) < 0) stat=lstat=BOARD_INCOMP;
         else sum += val; 
	 j-=s;
      }
      if(sum != SEEKED && lstat != BOARD_INCOMP) return BOARD_BAD;
      else if(sum > SEEKED) return BOARD_BAD;
      else if(sum == SEEKED && lstat != BOARD_INCOMP) stat = BOARD_GOOD;
   }
   return stat;
}

status CheckSums(int i, int j, int board[HEIGHT][WIDTH])
{
   if(CheckLine(i, board) == BOARD_BAD) return BOARD_BAD;
   return CheckDiags(i, j, board);
}

void FindNextFree(int *i, int *j, int board[HEIGHT][WIDTH])
{
   int dj=1+(*j>0);

   for(;*i<HEIGHT;++*i)
   {
      for(;*j<WIDTH;*j+=dj)
         if(board[*i][*j] < 0) return;
      *j=0; dj=1;
   }
   *i = -1; *j = -1;

   return;
}

void ShowBoard(int board[HEIGHT][WIDTH])
{
   int i, j, val;

   printf("\n+"); for(i=0;i<HEIGHT*3-1;++i) printf("--");
   printf("+\n");

   for(i=0;i<HEIGHT; ++i)
   {
      printf ("|");
      for(j=0;j<WIDTH; ++j)
      {
         if((val=board[i][j]) == 0) printf("   ");
	 else printf(" %2d", val);
      }
      printf(" |\n");
   }
   printf("+"); for(i=0;i<HEIGHT*3-1;++i) printf("--");
   printf("+\n");
}

void Recurse(int p, int x, int y, int board[HEIGHT][WIDTH], int pieces[PIECES])
{
   int val, v, lp;
   status s;

   FindNextFree(&x, &y, board);

   lp = pieces[PIECES-p];

   for(v=0;v<=PIECES-p;++v)
   {
      board[x][y]=val=pieces[v];
      pieces[v] = lp;
      s = CheckSums(x, y, board);
      if(s != BOARD_BAD && p < PIECES) { Recurse(p+1, x, y+2, board, pieces); }
      else if( p == PIECES && s == BOARD_GOOD) {ShowBoard(board); EXITON1SOL}
      pieces[v] = val;
   }
   board[x][y] = -1;
}

void InitPieces(int pieces[PIECES])
{
   int i;
   for(i=0;i<PIECES;++i)
      pieces[i]=i+1;
}

void InitBoard(int board[HEIGHT][WIDTH])
{
   int x, y, w, inc, ex;

   for(y=0; y<HEIGHT; ++y)
      for(x=0; x<WIDTH; ++x)
         board[y][x] = 0;

   w = STARTW; inc = 1;
   for(y=0; y<HEIGHT; ++y)
   {
      x = (WIDTH-w-w+1)/2;
      ex = WIDTH-x;

      for(; x < ex; x+=2) board[y][x] = -1;

      if (w==HEIGHT) { inc = -1; w=HEIGHT-1; } else { w += inc; }
   }
}

void CheckProblem()
{
   int maxv, v, i;

   maxv=0;
   v=PIECES;

   for(i=0; i<STARTW; ++i) {maxv += v--; }

   if (SEEKED > maxv)
   {
      printf ("No solution (max value on first line is %d (seeked %d) !\n",
                maxv, SEEKED);
      exit(1);
   }

   printf("Seekeing solutions for %d pos. board (%d to %d), sum=%d\n",
                PIECES, STARTW, HEIGHT, SEEKED);
}

int main()
{
   int board[HEIGHT][WIDTH];
   int pieces[PIECES];

   CheckProblem();

   InitPieces(pieces);
   InitBoard(board);

   Recurse(1, 0, 0, board, pieces);
   exit(FINALEXITCODE);
}