#ifdef SIZE

#define STYLE_FORK    1
#define STYLE_NOFORK  2
#define STYLE_PRUNE   4
#define STYLE_NOPRUNE 8

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <strings.h>

#if (SSIZE*SSIZE) != SIZE
#error SSIZE wrong, must be sqrt(SIZE)
#endif
#if (1<<SIZEBITS) < SIZE
#error SIZEBITS wrong, must be >= lg(SIZE)
#endif
#if (1<<SIZE1BITS) < (SIZE+1)
#error SIZE1BITS wrong, must be >= lg(SIZE+1)
#endif

extern const char *__progname;

typedef struct cell CELL;
typedef struct bd BD;
typedef struct locval LOCVAL;

struct cell {
  unsigned int x : SIZEBITS;
  unsigned int y : SIZEBITS;
  unsigned int box : SIZEBITS;
  unsigned int cwb : SIZEBITS;
  unsigned int fill : SIZE1BITS;
  unsigned int excl : SIZE;
#define BIT(x) (1U << ((x)-1))
#define ALLBITS (~((~0U)<<SIZE))
  } ;

struct bd {
  CELL c[SIZE][SIZE];
  } ;

struct locval {
  CELL *c;
  int v;
  } ;

static int style = (DEFSTYLE);
static int verbose = 0;
static int vsolve = 0;

static BD tosolve;
static int solved;
static int forked;
static void (*multsoln)(void);

static char boxlocw[SIZE][SIZE][2];
#define boxloc (*(const char (*)[SIZE][SIZE][2])&boxlocw)

static void setcell(BD *b, CELL *c, int v)
{
 int i;
 unsigned int bit;
 const char (*box)[2];

 bit = BIT(v);
 c->fill = v;
 box = &boxloc[c->box][0];
 if (c->excl & bit)
  { printf("Inconsistency, row %d col %d\n",c->y+1,c->x+1);
    abort();
  }
 for (i=0;i<SIZE;i++)
  { b->c[c->y][i].excl |= bit;
    b->c[i][c->x].excl |= bit;
    b->c[(int)box[i][1]][(int)box[i][0]].excl |= bit;
  }
 c->excl = ALLBITS;
}

static void fill(CELL *c, int v)
{
 setcell(&tosolve,c,v);
}

static void printpuzzle(BD *b, char blank, ...)
{
 int y;
 int x;
 va_list ap;
 CELL *c;
 char output[SIZE+1][((SIZE+SSIZE)*2)+1];
 char *op;
 char *oat[SIZE][SIZE];

 for (y=0;y<SIZE;y++)
  { op = &output[y][0];
    *op++ = '|';
    for (x=0;x<SIZE;x++)
     { *op++ = ' ';
       oat[y][x] = op;
       *op++ = b->c[y][x].fill ? fillchar(b->c[y][x].fill) : blank;
       if ((x % SSIZE) == SSIZE-1)
	{ *op++ = ' ';
	  *op++ = '|';
	}
     }
  }
 va_start(ap,blank);
 while (1)
  { c = va_arg(ap,CELL *);
    if (c == 0) break;
    op = oat[c->y][c->x];
    switch (op[-1])
     { case ' ': op[-1] = '('; break;
       case '(':               break;
       case ')': op[-1] = 'X'; break;
       default: abort();
     }
    switch (op[1])
     { case ' ': op[1] = ')'; break;
       case '(': op[1] = 'X'; break;
       case ')':              break;
       default: abort();
     }
  }
 va_end(ap);
 op = &output[SIZE][0];
 *op++ = '+';
 for (x=SSIZE-1;x>=0;x--)
  { int i;
    for (i=SSIZE-1;i>=0;i--)
     { *op++ = '-';
       *op++ = '-';
     }
    *op++ = '-';
    *op++ = '+';
  }
 printf("%.*s\n",(int)sizeof(output[0]),&output[SIZE][0]);
 for (y=0;y<SIZE;y++)
  { printf("%.*s\n",(int)sizeof(output[0]),&output[y][0]);
    if ((y % SSIZE) == SSIZE-1) printf("%.*s\n",(int)sizeof(output[0]),&output[SIZE][0]);
  }
}

static void solve(int levels)
{
 int y;
 int x;
 CELL *c;
 int i;
 int j;
 int v;
 CELL *best;
 int bestn;
 LOCVAL (*bestenum)(int);
 LOCVAL elv;
 int enum_n;
 int enum_v;
 BD save;
 VECTYPE row;
 VECTYPE col;
 VECTYPE box;
 unsigned int bits;

 static LOCVAL enum_cell(int inx)
  { if (best->excl & BIT(inx+1)) return((LOCVAL){.c=0,.v=0});
    return((LOCVAL){.c=best,.v=inx+1});
  }

 static LOCVAL enum_row(int inx)
  { if (tosolve.c[enum_n][inx].excl & BIT(enum_v)) return((LOCVAL){.c=0,.v=0});
    return((LOCVAL){.c=&tosolve.c[enum_n][inx],.v=enum_v});
  }

 static LOCVAL enum_col(int inx)
  { if (tosolve.c[inx][enum_n].excl & BIT(enum_v)) return((LOCVAL){.c=0,.v=0});
    return((LOCVAL){.c=&tosolve.c[inx][enum_n],.v=enum_v});
  }

 static LOCVAL enum_box(int inx)
  { CELL *c;
    c = &tosolve.c[(int)boxloc[enum_n][inx][1]][(int)boxloc[enum_n][inx][0]];
    if (c->excl & BIT(enum_v)) return((LOCVAL){.c=0,.v=0});
    return((LOCVAL){.c=c,.v=enum_v});
  }

 while <"force"> (1)
  { if (vsolve)
     { for (y=0;y<SIZE;y++)
	{ printf("%*s| ",levels,"");
	  for (x=0;x<SIZE;x++)
	   { if (x) printf("%s",SEP);
	     c = &tosolve.c[y][x];
	     if (c->fill)
	      { printf(FILLEDFMT,c->fill);
	      }
	     else
	      { printf(MASKFMT,c->excl);
	      }
	   }
	  printf("\n");
	}
     }
    best = 0;
    for (y=0;y<SIZE;y++)
     { for (x=0;x<SIZE;x++)
	{ c = &tosolve.c[y][x];
	  if (c->fill) continue;
	  if (!best || (bitcount(c->excl) > bitcount(best->excl))) best = c;
	}
     }
    if (best == 0)
     { if (verbose)
	{ printf("Found solution:\n");
	  printpuzzle(&tosolve,'·',(CELL *)0);
	}
       if (solved) (*multsoln)();
       solved = 1;
       return;
     }
    if (bitcount(best->excl) > SIZE-1)
     { if (vsolve) printf("%*sDead end (r=%d c=%d)\n",levels,"",best->y,best->x);
       return;
     }
    if (bitcount(best->excl) == SIZE-1)
     { for (i=SIZE;best->excl&BIT(i);i--) ;
       if (vsolve) printf("%*sPlacing %d at row %d col %d (cell)\n",levels,"",i,best->y,best->x);
       fill(best,i);
       continue <"force">;
     }
    bestn = SIZE - bitcount(best->excl);
    bestenum = &enum_cell;
    for (i=0;i<SIZE;i++)
     { row = 0;
       col = 0;
       box = 0;
       for (j=0;j<SIZE;j++)
#define MERGE(VAR,R,C) do { CELL *l; l = &tosolve.c[R][C];		\
		VAR |= ((VAR & ALLBITS & ~(typeof(VAR))l->excl) << SIZE) |\
			(ALLBITS & ~(typeof(VAR))l->excl);		\
		if (l->fill) VAR |= ((typeof(VAR))BIT(l->fill)) << (SIZE*2);\
			} while (0)
	{ MERGE(row,i,j);
	  MERGE(col,j,i);
	  MERGE(box,(int)boxloc[i][j][1],(int)boxloc[i][j][0]);
	}
#undef MERGE
#define CHECK(V) do { if (((V | (V >> (SIZE*2))) & ALLBITS) != ALLBITS)	\
	{ if (vsolve) printf("%*sDead end (%s %d)\n",levels,"",#V,i); return; } } while(0)
       CHECK(row);
       CHECK(col);
       CHECK(box);
#undef CHECK
       bits = row & ~(row >> SIZE) & ALLBITS;
       if (bits)
	{ for (j=0;j<SIZE;j++)
	   { c = &tosolve.c[i][j];
	     if (bits & ~c->excl)
	      { bits &= ~c->excl;
		for (i=1;i<=SIZE;i++) if (bits & BIT(i)) break;
		if (vsolve) printf("%*sPlacing %d at r=%d c=%d (row)\n",levels,"",i,c->y,c->x);
		fill(c,i);
		continue <"force">;
	      }
	   }
	}
       if (row & ALLBITS)
	{ SUMDECL;
	  SUMINIT;
	  for (j=0;j<SIZE;j++) SUMADD(ALLBITS&~tosolve.c[i][j].excl);
	  for (v=0;v<SIZE;v++)
	   { j = SUMGET(v);
	     if (j == 0) continue;
	     if (j == 1) abort();
	     if ((j < bestn) || ((j == bestn) && (bestenum == &enum_box)))
	      { bestn = j;
		bestenum = &enum_row;
		enum_n = i;
		enum_v = v + 1;
	      }
	   }
	}
       bits = col & ~(col >> SIZE) & ALLBITS;
       if (bits)
	{ for (j=0;j<SIZE;j++)
	   { c = &tosolve.c[j][i];
	     if (bits & ~c->excl)
	      { bits &= ~c->excl;
		for (i=1;i<=SIZE;i++) if (bits & BIT(i)) break;
		if (vsolve) printf("%*sPlacing %d at r=%d c=%d (col)\n",levels,"",i,c->y,c->x);
		fill(c,i);
		continue <"force">;
	      }
	   }
	}
       if (col & ALLBITS)
	{ SUMDECL;
	  SUMINIT;
	  for (j=0;j<SIZE;j++) SUMADD(ALLBITS&~tosolve.c[j][i].excl);
	  for (v=0;v<SIZE;v++)
	   { j = SUMGET(v);
	     if (j == 0) continue;
	     if (j == 1) abort();
	     if ((j < bestn) || ((j == bestn) && (bestenum == &enum_box)))
	      { bestn = j;
		bestenum = &enum_col;
		enum_n = i;
		enum_v = v + 1;
	      }
	   }
	}
       bits = box & ~(box >> SIZE) & ALLBITS;
       if (bits)
	{ for (j=0;j<SIZE;j++)
	   { c = &tosolve.c[(int)boxloc[i][j][1]][(int)boxloc[i][j][0]];
	     if (bits & ~c->excl)
	      { bits &= ~c->excl;
		for (i=1;i<=SIZE;i++) if (bits & BIT(i)) break;
		if (vsolve) printf("%*sPlacing %d at r=%d c=%d (box)\n",levels,"",i,c->y,c->x);
		fill(c,i);
		continue <"force">;
	      }
	   }
	}
       if (box & ALLBITS)
	{ SUMDECL;
	  SUMINIT;
	  for (j=0;j<SIZE;j++) SUMADD(ALLBITS&~tosolve.c[(int)boxloc[i][j][1]][(int)boxloc[i][j][0]].excl);
	  for (v=0;v<SIZE;v++)
	   { j = SUMGET(v);
	     if (j == 0) continue;
	     if (j == 1) abort();
	     if (j < bestn)
	      { bestn = j;
		bestenum = &enum_box;
		enum_n = i;
		enum_v = v + 1;
	      }
	   }
	}
     }
    if (vsolve) printf("%*sNo more forced\n",levels,"");
    save = tosolve;
    forked = 1;
    for (i=0;i<SIZE;i++)
     { elv = (*bestenum)(i);
       if (elv.c == 0) continue;
       if (vsolve) printf("%*sTrying %d at r=%d c=%d\n",levels,"",elv.v,elv.c->y,elv.c->x);
       fill(elv.c,elv.v);
       solve(levels+2);
       tosolve = save;
     }
    break;
  }
}

static int random_allowed(unsigned int mask)
{
 int v;
 int i;
 int j;

 v = random() % (SIZE - bitcount(mask));
 for (i=mask,j=1;;i>>=1,j++)
  { if (i & 1) continue;
    if (v == 0) break;
    v --;
  }
 return(j);
}

static int solns(void)
{
 __label__ mult;

 static void multiple_solutions(void)
  { goto mult;
  }

 multsoln = &multiple_solutions;
 solved = 0;
 forked = 0;
 solve(2);
 return(solved);
mult:;
 return(2);
}

static void recompute_excl(BD *b)
{
 int y;
 int x;
 CELL *c;

 for (y=0;y<SIZE;y++)
  { for (x=0;x<SIZE;x++)
     { b->c[y][x].excl = 0;
     }
  }
 for (y=0;y<SIZE;y++)
  { for (x=0;x<SIZE;x++)
     { c = &b->c[y][x];
       if (c->fill) setcell(b,c,c->fill);
     }
  }
}

static void handleargs(int ac, char **av)
{
 int skip;
 int errs;

 skip = 0;
 errs = 0;
 for (ac--,av++;ac;ac--,av++)
  { if (skip > 0)
     { skip --;
       continue;
     }
    if (**av != '-')
     { fprintf(stderr,"%s: extra argument `%s'\n",__progname,*av);
       errs ++;
       continue;
     }
#if 0
    if (0)
     {
needarg:;
       fprintf(stderr,"%s: %s needs a following argument\n",__progname,*av);
       errs ++;
       continue;
     }
#endif
#define WANTARG() do { if (++skip >= ac) goto needarg; } while (0)
    if (!strcmp(*av,"-v"))
     { verbose = 1;
       continue;
     }
    if (!strcmp(*av,"-V"))
     { verbose = 1;
       vsolve = 1;
       continue;
     }
    if (!strcmp(*av,"-fork"))
     { style = (style & ~STYLE_NOFORK) | STYLE_FORK;
       continue;
     }
    if (!strcmp(*av,"-nofork"))
     { style = (style & ~STYLE_FORK) | STYLE_NOFORK;
       continue;
     }
    if (!strcmp(*av,"-prune"))
     { style = (style & ~STYLE_NOPRUNE) | STYLE_PRUNE;
       continue;
     }
    if (!strcmp(*av,"-noprune"))
     { style = (style & ~STYLE_PRUNE) | STYLE_NOPRUNE;
       continue;
     }
#undef WANTARG
    fprintf(stderr,"%s: unrecognized option `%s'\n",__progname,*av);
    errs ++;
  }
 if (errs) exit(1);
}

int main(int, char **);
int main(int ac, char **av)
{
 BD save;
 BD work;
 int x;
 int y;
 CELL *c1;
 CELL *c2;
 CELL *list[((SIZE*SIZE)+1)/2];
 int nlist;

 handleargs(ac,av);
 srandom(time(0));
 bitcount_init();
 for (y=0;y<SIZE;y++)
  { for (x=0;x<SIZE;x++)
     { boxlocw[y][x][0] = (x%SSIZE) + ((y%SSIZE)*SSIZE);
       boxlocw[y][x][1] = (x/SSIZE) + ((y/SSIZE)*SSIZE);
     }
  }
 for (y=0;y<SIZE;y++)
  { for (x=0;x<SIZE;x++)
     { c1 = &work.c[y][x];
       c1->x = x;
       c1->y = y;
       c1->box = boxloc[y][x][1];
       c1->cwb = boxloc[y][x][0];
       c1->fill = 0;
       c1->excl = 0;
     }
  }
 while <"place"> (1)
  { x = random() % SIZE;
    y = random() % SIZE;
    c1 = &work.c[y][x];
    if (c1->fill) continue;
    c2 = &work.c[SIZE-1-y][SIZE-1-x];
    if (c2->fill) abort();
    save = work;
    if (c1 == c2)
     { setcell(&work,c1,random_allowed(c1->excl));
     }
    else if ((c1->box == c2->box) || (c1->x == c2->x) || (c1->y == c2->y))
     { setcell(&work,c1,random_allowed(c1->excl));
       if (c2->excl == ALLBITS)
	{ work = save;
	  continue <"place">;
	}
       setcell(&work,c2,random_allowed(c2->excl));
     }
    else
     { setcell(&work,c1,random_allowed(c1->excl));
       setcell(&work,c2,random_allowed(c2->excl));
     }
    tosolve = work;
    if (verbose)
     { printf("Trying:\n");
       printpuzzle(&work,'·',c1,c2,(CELL *)0);
     }
    switch (solns())
     { case 0:
	  if (verbose) printf("No solutions\n");
	  work = save;
	  continue <"place">;
	  break;
       case 1:
	  switch (style & (STYLE_FORK|STYLE_NOFORK))
	   { case STYLE_NOFORK:
		if (! forked)
		 {
	     case STYLE_FORK:
		   if (verbose) printf("One solution\n");
		   break <"place">;
		 }
		else
		 { if (verbose) printf("One solution, but search forked\n");
		 }
		continue <"place">;
		break;
	   }
	  abort();
	  break;
       default:
	  if (verbose) printf("Multiple solutions\n");
	  break;
     }
  }
 switch (style & (STYLE_PRUNE|STYLE_NOPRUNE))
  { default:
       abort();
       break;
    case STYLE_NOPRUNE:
       break;
    case STYLE_PRUNE:
       nlist = 0;
       for <"find"> (y=0;;y++)
	{
#if ! (SIZE & 1)
	  if (y >= (SIZE/2)) break;
#endif
	  for (x=0;x<SIZE;x++)
	   { c1 = &work.c[y][x];
	     if (c1->fill) list[nlist++] = c1;
#if SIZE & 1
	     if ((x == (SIZE/2)) && (y == (SIZE/2))) break <"find">;
#endif
	   }
	}
       while (nlist > 0)
	{ x = random() % nlist;
	  c1 = list[x];
	  nlist --;
	  if (x < nlist) list[x] = list[nlist];
	  c2 = &work.c[SIZE-1-c1->y][SIZE-1-c1->x];
	  tosolve = work;
	  tosolve.c[c1->y][c1->x].fill = 0;
	  tosolve.c[c2->y][c2->x].fill = 0;
	  recompute_excl(&tosolve);
	  if (verbose)
	   { printf("Trying:\n");
	     printpuzzle(&tosolve,'·',&tosolve.c[c1->y][c1->x],&tosolve.c[c2->y][c2->x],(CELL *)0);
	   }
	  switch (solns())
	   { case 0:
		if (verbose) printf("No solutions\n");
		abort();
		break;
	     case 1:
		switch (style & (STYLE_FORK|STYLE_NOFORK))
		 { case STYLE_NOFORK:
		      if (! forked)
		       {
		   case STYLE_FORK:
			 if (verbose) printf("One solution\n");
			 c1->fill = 0;
			 c2->fill = 0;
			 recompute_excl(&work);
		       }
		      else
		       { if (verbose) printf("One solution, but search forked\n");
		       }
		      break;
		   default:
		      abort();
		      break;
		 }
		break;
	     default:
		if (verbose) printf("Multiple solutions\n");
		break;
	   }
	}
       break;
  }
 if (verbose) printf("Final\n");
 printpuzzle(&work,'.',(CELL *)0);
 exit(0);
}

#endif