#ifdef SIZE

#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

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

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 verbose = 0;

static BD puzzle;

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

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

 if ((v < 1) | (v > SIZE)) abort();
 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);
    exit(1);
  }
 for (i=0;i<SIZE;i++)
  { puzzle.c[c->y][i].excl |= bit;
    puzzle.c[i][c->x].excl |= bit;
    puzzle.c[(int)box[i][1]][(int)box[i][0]].excl |= bit;
  }
 c->excl = ALLBITS;
}

static void load_puzzle(void)
{
 int y;
 int x;
 CELL *c;
 int ch;
 int f;

 for (y=0;y<SIZE;y++)
  { for (x=0;x<SIZE;x++)
     { c = &puzzle.c[y][x];
       c->x = x;
       c->y = y;
       c->box = boxloc[y][x][1];
       c->cwb = boxloc[y][x][0];
       c->fill = 0;
       c->excl = 0;
     }
  }
 for (y=0;y<SIZE;y++)
  { for (x=0;x<SIZE;x++)
     { c = &puzzle.c[y][x];
       while <"cell"> (1)
	{ ch = getchar();
	  if (ch == EOF)
	   { fprintf(stderr,"%s: EOF in mid-puzzle\n",__progname);
	     exit(1);
	   }
	  f = charfill(ch);
	  if (f > 0)
	   { fill(c,f);
	     break <"cell">;
	   }
	  else if (f == 0)
	   { break <"cell">;
	   }
	}
     }
  }
}

static void printpuzzle(void)
{
 int y;
 int x;
 char output[SIZE+1][((SIZE+SSIZE)*2)+1];
 char *op;

 for (y=0;y<SIZE;y++)
  { op = &output[y][0];
    *op++ = '|';
    for (x=0;x<SIZE;x++)
     { *op++ = ' ';
       *op++ = puzzle.c[y][x].fill ? fillchar(puzzle.c[y][x].fill) : '.';
       if ((x % SSIZE) == SSIZE-1)
	{ *op++ = ' ';
	  *op++ = '|';
	}
     }
  }
 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 done(void)
{
 printpuzzle();
}

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 (puzzle.c[enum_n][inx].excl & BIT(enum_v)) return((LOCVAL){.c=0,.v=0});
    return((LOCVAL){.c=&puzzle.c[enum_n][inx],.v=enum_v});
  }

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

 static LOCVAL enum_box(int inx)
  { CELL *c;
    c = &puzzle.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 (verbose)
     { for (y=0;y<SIZE;y++)
	{ printf("%*s| ",levels,"");
	  for (x=0;x<SIZE;x++)
	   { if (x) printf("%s",SEP);
	     c = &puzzle.c[y][x];
	     if (c->fill)
	      { printf(FILLEDFMT,FILLEDARG(c->fill));
	      }
	     else
	      { printf(MASKFMT,c->excl);
	      }
	   }
	  printf("\n");
	}
     }
    best = 0;
    for (y=0;y<SIZE;y++)
     { for (x=0;x<SIZE;x++)
	{ c = &puzzle.c[y][x];
	  if (c->fill) continue;
	  if (!best || (bitcount(c->excl) > bitcount(best->excl))) best = c;
	}
     }
    if (best == 0)
     { done();
       return;
     }
    if (bitcount(best->excl) > SIZE-1)
     { if (verbose) 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 (verbose) 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 = &puzzle.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 (verbose) 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 = &puzzle.c[i][j];
	     if (bits & ~c->excl)
	      { bits &= ~c->excl;
		for (i=1;i<=SIZE;i++) if (bits & BIT(i)) break;
		if (verbose) 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&~puzzle.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 = &puzzle.c[j][i];
	     if (bits & ~c->excl)
	      { bits &= ~c->excl;
		for (i=1;i<=SIZE;i++) if (bits & BIT(i)) break;
		if (verbose) 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&~puzzle.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 = &puzzle.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 (verbose) 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&~puzzle.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 (verbose) printf("%*sNo more forced\n",levels,"");
    save = puzzle;
    for (i=0;i<SIZE;i++)
     { elv = (*bestenum)(i);
       if (elv.c == 0) continue;
       if (verbose) 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);
       puzzle = save;
     }
    break;
  }
}

static void boxloc_init(void)
{
 int x;
 int y;

 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);
     }
  }
}

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;
     }
#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)
{
 handleargs(ac,av);
 bitcount_init();
 boxloc_init();
 load_puzzle();
 solve(2);
 exit(0);
}

#endif