/*====================================+====================================*/
/*                                                                         */ 
/*                    A General Puzzle Solution Program                    */ 
/*                              by Udo Sprute                              */ 
/*                        Version 1.2.5, 1995.11.02                        */ 
/*                         (hybrid language C/C++)                         */ 
/*                                                                         */ 
/*====================================+====================================*/


# include <stdio.h> 
# include <stdlib.h> 
# include <unistd.h> 
# include <stdarg.h> 
# include <string.h> 
# include <fcntl.h> 

# undef NULL 
# define NULL 0 

# undef FALSE 
# undef TRUE 
typedef enum { FALSE, TRUE } boolean; 
boolean testing = FALSE; 
boolean surrounding = FALSE; 
boolean norotate = FALSE; 
boolean distributed = FALSE; 
boolean blind = FALSE; 
const char * squeezing = NULL; 

unsigned messages = 0; 
unsigned part = 0; 
unsigned pn = 0; 

unsigned nnn; 
# define NNN * 


typedef struct struct_permutation { 
   unsigned NNN indices; 
   struct struct_permutation * next; 
} permutation; 


typedef struct struct_element { 
   char * name; 
   boolean used; 
   struct struct_element * NNN neigh; 
   unsigned NNN conn; 
   char * NNN value; 
} element; 

typedef struct struct_appearence { 
   element * elementvar; 
   struct struct_appearence * next; 
} appearence; 

typedef struct struct_shape { 
   unsigned unused; 
   appearence * appearencevar; 
   struct struct_shape * next; 
} shape; 


typedef struct struct_place { 
   char * name; 
   struct struct_place * NNN neigh; 
   unsigned NNN conn; 
   element * occ; 
   struct struct_place * next; 
   element * solutionocc; 
   char * NNN solutionvalue; 
} place; 

/*------------------------------------+------------------------------------*/


void fatal (char * fmt, ...) 
{ 
   va_list args; 
   va_start (args, fmt); 
   fprintf (stderr, "Error: "); 
   vfprintf (stderr, fmt, args); 
   fprintf (stderr, "\n"); 
   va_end (args); 
   exit (1); 
} 

void * alloc (unsigned n_bytes) 
{ 
   void * result = malloc (n_bytes); 
   if (! result) 
      fatal ("Malloc doesn't give memory any more."); 
   return result; 
} 

void fieldprint (place * f) 
{ 
   if (f) { 
      unsigned n; 
      char * nothing = (char *) alloc ((n=strlen(f->name)) + 1); 
      nothing[n] = '\0'; 
      while (n--) 
         nothing[n] = '-'; 
      do { 
         printf ("%s:  ", f->name); 
         for (n=0; n<nnn; n++) 
            printf ("%s %d  ", (f->neigh[n]) ? f->neigh[n]->name : nothing, 
                                f->conn[n] ); 
         printf ("\n"); 
         f = f->next; 
      } while (f); 
      free (nothing); 
   } 
   return; 
} 

void elementprint (element * f) 
{ 
   unsigned n; 
   char * nothing; 

   nothing = (char *) alloc ((n=strlen(f->name)) + 1); 
   nothing[n] = '\0'; 
   while (n--) 
      nothing[n] = '-'; 

   printf ("%s:  ", f->name); 
   for (n=0; n<nnn; n++) 
      printf ("%s %s %d  ", f->value[n], 
                            f->neigh[n] ? f->neigh[n]->name : nothing, 
                            f->conn[n]); 
   printf ("\n"); 
   f->used = TRUE; 
   for (n=0; n<nnn; n++) 
      if (f->neigh[n] && ! f->neigh[n]->used) 
         elementprint (f->neigh[n]); 

   free (nothing); 
   return; 
} 

void elementunuse (element * el) 
{ 
   unsigned n; 

   el->used = FALSE; 
   for (n=0; n<nnn; n++) 
      if (el->neigh[n] && el->neigh[n]->used) 
         elementunuse (el->neigh[n]); 
   return; 
} 

void inputtest (permutation * p, place * field, shape * fig) 
{ 
   unsigned n; 

   printf ("Rotations:\n"); 
   for (n=0; n<nnn; n++) 
      printf ("%d ", n); 
   printf ("\n"); 
   while (p) { 
      for (n=0; n<nnn; n++) 
         printf ("%d ", p->indices[n]); 
      printf ("\n"); 
      p = p->next; 
   } 
   printf ("\n"); 
   printf ("Field:\n"); 
   fieldprint (field); 
   printf ("\n"); 
   printf ("Pieces:\n"); 
   while (fig) { 
      appearence * app = fig->appearencevar; 
      printf ("%u\n", fig->unused); 
      while (app) { 
         elementprint (app->elementvar); 
         elementunuse (app->elementvar); 
         printf ("\n"); 
         app = app->next; 
      } 
      fig = fig->next; 
   } 
   fflush (stdout); 
   return; 
} 

/*------------------------------------+------------------------------------*/


# define NAMESIZE 20 


struct connectionlist { 
   char * name; 
   unsigned number; 
   struct connectionlist * left, * right; 
}; 

unsigned connectionnumber (const char * name) 
{ 
   static struct connectionlist * list = NULL; 
   struct connectionlist ** lp = & list; 

   while (*lp) { 
      int cmp = strcmp (name, (*lp)->name); 
      if (cmp < 0) 
         lp = & (*lp)->left; 
      else if (cmp > 0) 
         lp = & (*lp)->right; 
      else 
         return (*lp)->number; 
   } 
   *lp = (struct connectionlist *) alloc (sizeof (struct connectionlist)); 
   (*lp)->name = (char *) alloc (strlen(name)+1); 
   strcpy ((*lp)->name, name); 
   (*lp)->left = (*lp)->right = NULL; 
   return (*lp)->number = nnn++; 
} 

permutation * read_rotations (void) 
{ 
   permutation * rotations = NULL, ** rot = & rotations; 
   char name[NAMESIZE]; 
   int c; 

   if ((c=getchar()) == EOF) 
      fatal ("Empty inputfile."); 
   ungetc (c, stdin); 
   while ((c=getchar()) != '\n') { 
      ungetc (c, stdin); 
      scanf ("%s", name); 
      connectionnumber (name); 
   } 

   while ((c=getchar()) != '\n') { 
      unsigned n; 
      ungetc (c, stdin); 
      *rot = (permutation *) alloc (sizeof (permutation)); 
      (*rot)->indices = (unsigned *) alloc (nnn * sizeof(unsigned)); 
      (*rot)->next = NULL; 
      for (n=0; n<nnn; n++) { 
         scanf ("%s", name); 
         (*rot)->indices[n] = connectionnumber (name); 
      } 
      if (getchar() != '\n') 
         fatal ("Garbage in Rotationlist."); 
      rot = & (*rot)->next; 
   } 
   return rotations; 
} 


struct placelist { 
   char * name; 
   place * address; 
   struct placelist * left, * right; 
}; 

place * placeaddress (const char * name, place ** fieldp) 
{ 
   static struct placelist * list = NULL; 
   struct placelist ** lp = & list; 
   unsigned n; 

   while (*lp) { 
      int cmp = strcmp (name, (*lp)->name); 
      if (cmp < 0) 
         lp = & (*lp)->left; 
      else if (cmp > 0) 
         lp = & (*lp)->right; 
      else 
         return (*lp)->address; 
   } 
   *lp = (struct placelist *) alloc (sizeof (struct placelist)); 
   (*lp)->name = (char *) alloc (strlen(name)+1); 
   strcpy ((*lp)->name, name); 
   (*lp)->left = (*lp)->right = NULL; 
   (*lp)->address = (place *) alloc (sizeof (place)); 
   (*lp)->address->name = (*lp)->name; 
   (*lp)->address->neigh = (place   **) alloc (nnn * sizeof(place  *)); 
   (*lp)->address->conn  = (unsigned *) alloc (nnn * sizeof(unsigned)); 
   for (n=0; n<nnn; n++) { 
      (*lp)->address->neigh[n] = NULL; 
      (*lp)->address->conn [n] = 0; 
   } 
   (*lp)->address->occ = NULL; 
   (*lp)->address->next = *fieldp; 

   (*lp)->address->solutionocc   = NULL; 
   (*lp)->address->solutionvalue = (char **) alloc (nnn * sizeof(char *)); 
   for (n=0; n<nnn; n++) 
      (*lp)->address->solutionvalue[n] = NULL; 
   return *fieldp = (*lp)->address; 
} 

place * read_field (void) 
{ 
   place * field = NULL; 
   int c; 

   while ((c=getchar()) != '\n') { 
      char name1[NAMESIZE], name2[NAMESIZE]; 
      char conn1[NAMESIZE], conn2[NAMESIZE]; 
      place * field1, * field2; 
      unsigned port1, port2; 

      ungetc (c, stdin); 
      scanf ("%s %s %s %s", name1, conn1, name2, conn2); 
      if (getchar() != '\n') 
         fatal ("Garbage in Field."); 
      field1 = placeaddress (name1, &field); 
      field2 = placeaddress (name2, &field); 
      port1 = connectionnumber (conn1); 
      port2 = connectionnumber (conn2); 
      field1->neigh[port1] = field2; 
      field1->conn [port1] =  port2; 
      field2->neigh[port2] = field1; 
      field2->conn [port2] =  port1; 
   } 
   return field; 
} 


struct elementlist { 
   char * name; 
   element * address; 
   struct elementlist * left, * right; 
}; 

element * elementaddress (const char * name) 
{ 
   static struct elementlist * list = NULL; 
   struct elementlist ** lp = & list; 
   unsigned n; 

   if (! name) { 
      list = NULL; 
      return NULL; 
   } 
   while (*lp) { 
      int cmp = strcmp (name, (*lp)->name); 
      if (cmp < 0) 
         lp = & (*lp)->left; 
      else if (cmp > 0) 
         lp = & (*lp)->right; 
      else 
         return (*lp)->address; 
   } 
   *lp = (struct elementlist *) alloc (sizeof (struct elementlist)); 
   (*lp)->name = (char *) alloc (strlen(name)+1); 
   strcpy ((*lp)->name, name); 
   (*lp)->left = (*lp)->right = NULL; 
   (*lp)->address = (element *) alloc (sizeof (element)); 
   (*lp)->address->name = (*lp)->name; 
   (*lp)->address->used = FALSE; 
   (*lp)->address->neigh = (element **) alloc (nnn * sizeof(element *)); 
   (*lp)->address->conn  = (unsigned *) alloc (nnn * sizeof(unsigned )); 
   (*lp)->address->value = (char    **) alloc (nnn * sizeof(char    *)); 
   for (n=0; n<nnn; n++) { 
      (*lp)->address->neigh[n] = NULL; 
      (*lp)->address->conn [n] = 0; 
      (*lp)->address->value[n] = NULL; 
   } 
   return (*lp)->address; 
} 

struct valuelist { 
   char * name; 
   struct valuelist * left, * right; 
}; 

char * valueaddress (const char * name) 
{ 
   static struct valuelist * list = NULL; 
   struct valuelist ** lp = & list; 

   while (*lp) { 
      int cmp = strcmp (name, (*lp)->name); 
      if (cmp < 0) 
         lp = & (*lp)->left; 
      else if (cmp > 0) 
         lp = & (*lp)->right; 
      else 
         return (*lp)->name; 
   } 
   *lp = (struct valuelist *) alloc (sizeof (struct valuelist)); 
   (*lp)->name = (char *) alloc (strlen(name)+1); 
   strcpy ((*lp)->name, name); 
   (*lp)->left = (*lp)->right = NULL; 
   return (*lp)->name; 
} 

shape * read_figures (void) 
{ 
   shape * figures = NULL, ** fp = & figures; 
   int c; 

   while ((c=getchar()) != EOF) { 
      *fp = (shape *) alloc (sizeof (shape)); 
      (*fp)->unused = 1; 
      (*fp)->appearencevar = (appearence *) alloc (sizeof (appearence)); 
      (*fp)->next = NULL; 
      while (c != '\n') { 
         char name[NAMESIZE]; 
         unsigned n; 
         ungetc (c, stdin); 
         scanf ("%s", name); 
         (*fp)->appearencevar->elementvar = elementaddress (name); 
         (*fp)->appearencevar->next = NULL; 
         for (n=0; n<nnn; n++) { 
            scanf ("%s", name); 
            (*fp)->appearencevar->elementvar->value[n] = valueaddress (name); 
         } 
         if (getchar() != '\n') 
            fatal ("Garbage in Elementlist."); 
         c = getchar (); 
      } 
      while ((c=getchar()) != '\n') { 
         char name1[NAMESIZE], name2[NAMESIZE]; 
         char conn1[NAMESIZE], conn2[NAMESIZE]; 
         element * field1, * field2; 
         unsigned port1, port2; 

         if (c == '>') { 
            if (getchar() != ' ') 
               fatal ("Missing space in shift."); 
            scanf ("%s %s", name1, name2); 
            if (getchar() != '\n') 
               fatal ("Garbage in shift."); 
            elementaddress(name1)->name = elementaddress(name2)->name; 
         } else if (c == '#') { 
            c = getchar (); 
            while (c==' ' || c=='\t') 
               c = getchar (); 
            ungetc (c, stdin); 
            scanf ("%d", & (*fp)->unused); 
            if (getchar() != '\n') 
               fatal ("Garbage in count."); 
         } else { 
            ungetc (c, stdin); 
            scanf ("%s %s %s %s", name1, conn1, name2, conn2); 
            if (getchar() != '\n') 
               fatal ("Garbage in Figure.  Last name:  %s", name2); 
            field1 = elementaddress (name1); 
            field2 = elementaddress (name2); 
            port1 = connectionnumber (conn1); 
            port2 = connectionnumber (conn2); 
            field1->neigh[port1] = field2; 
            field1->conn [port1] =  port2; 
            field2->neigh[port2] = field1; 
            field2->conn [port2] =  port1; 
         } 
      } 
      fp = & (*fp)->next; 
      elementaddress (NULL); 
   } 
   return figures; 
} 

/*------------------------------------+------------------------------------*/


boolean path (element * el0, element * el1) 
{ 
   unsigned n; 
   for (n=0; n<nnn; n++) 
      if (el0->neigh[n]) 
         if (el0->neigh[n] == el1) 
            return TRUE; 
         else { 
            el0->used = TRUE; 
            if (! el0->neigh[n]->used && path (el0->neigh[n], el1)) { 
               el0->used = FALSE; 
               return TRUE; 
            } 
            el0->used = FALSE; 
         } 
   return FALSE; 
} 

void nettel (element * el0) 
{ 
   unsigned n; 
   for (n=0; n<nnn; n++) 
      if (el0->neigh[n]) { 
         element * el1 = el0->neigh[n]; 
         el0->neigh[n] = NULL; 
         el1->neigh[el0->conn[n]] = NULL; 
         if (path (el0, el1)) { 
            el1->conn [el0->conn[n]] = 0; 
            el0->conn [n] = 0; 
         } else { 
            nettel (el1); 
            el0->neigh[n] = el1; 
            el1->neigh[el0->conn[n]] = el0; 
         } 
      } 
   return; 
} 

void netto (shape * figures) 
{ 
   shape * i; 
   appearence * j; 
   for (i=figures; i; i=i->next) 
      for (j=i->appearencevar; j; j=j->next) 
         nettel (j->elementvar); 
   return; 
} 



struct table { 
   void * org; 
   void * res; 
   struct table * next; 
}; 

element * rotel (element * el, unsigned ind[]) 
{ 
   static unsigned depth = 0; 
   static struct table * tab = NULL, ** tp; 
   element * result = (element *) alloc (sizeof (element)); 
   unsigned n; 

   if (! depth) { 
      while (tab) { 
         struct table * help = tab; 
         tab = tab->next; 
         free (help); 
      } 
      tp = & tab; 
   } 
   *tp = (struct table *) alloc (sizeof (struct table)); 
   (*tp)->org = el; 
   (*tp)->res = result; 
   (*tp)->next = NULL; 
   tp = & (*tp)->next; 
   result->name = el->name; 
   result->used = FALSE; 
   result->neigh = (element **) alloc (nnn * sizeof(element *)); 
   result->conn  = (unsigned *) alloc (nnn * sizeof(unsigned )); 
   result->value = (char    **) alloc (nnn * sizeof(char    *)); 
   depth++; 
   for (n=0; n<nnn; n++) { 
      result->neigh[ind[n]] = NULL; 
      result->conn [ind[n]] = 0; 
      result->value[ind[n]] = el->value[n]; 
      if (el->neigh[n]) { 
         struct table * t; 
         for (t=tab; t; t=t->next) 
            if (t->org == el->neigh[n]) 
               result->neigh[ind[n]] = (element *) t->res; 
         if (! result->neigh[ind[n]]) 
            result->neigh[ind[n]] = rotel (el->neigh[n], ind); 
         result->conn[ind[n]] = ind[el->conn[n]]; 
      } 
   } 
   depth--; 
   return result; 
} 

void rotate (shape * figures, permutation * rotations) 
{ 
   while (figures) { 
      appearence * app = figures->appearencevar; 
      permutation * rot = rotations; 
      while (rot) { 
         app->next = (appearence *) alloc (sizeof (appearence)); 
         app = app->next; 
         app->elementvar = rotel (figures->appearencevar->elementvar, 
            rot->indices); 
         rot = rot->next; 
      } 
      app->next = NULL; 
      figures = figures->next; 
   } 
   return; 
} 


boolean equal (element * el0, element * el1) 
{ 
   unsigned n; 

   for (n=0; n<nnn; n++) 
      if (! el0->neigh[n] != ! el1->neigh[n] || 
            el0->conn [n] !=   el1->conn [n] || 
            el0->value[n] !=   el1->value[n]  ) 
         return FALSE; 
   el1->used = TRUE; 
   for (n=0; n<nnn; n++) 
      if (el1->neigh[n] && ! el1->neigh[n]->used) 
         if (! equal (el0->neigh[n], el1->neigh[n])) 
            return FALSE; 
   return TRUE; 
} 

boolean equalall (element * el0, element * el1) 
{ 
   boolean result = equal (el0, el1); 
   elementunuse (el1); 
   return result; 
} 

boolean matching (element * org, element * el) 
{ 
   if (equalall (org, el)) 
      return TRUE; 
   else { 
      unsigned n; 
      org->used = TRUE; 
      for (n=0; n<nnn; n++) 
         if (org->neigh[n] && ! org->neigh[n]->used) 
            if (matching (org->neigh[n], el)) 
               return TRUE; 
      return FALSE; 
   } 
} 

boolean matchingall (element * org, element * el) 
{ 
   boolean result = matching (org, el); 
   elementunuse (org); 
   return result; 
} 

void shorten (shape * figures) 
{ 
   appearence * first, * second; 

   while (figures) { 
      for (first=figures->appearencevar; first; first=first->next) 
         for (second=first; second->next; ) 
            if (matchingall (first->elementvar, second->next->elementvar)) 
               second->next = second->next->next; 
            else 
               second = second->next; 
      figures = figures->next; 
   } 
   return; 
} 


appearence * shiftel (element * el) 
{ 
   appearence * result = NULL, ** np = & result; 
   unsigned n; 

   el->used = TRUE; 
   for (n=0; n<nnn; n++) 
      if (el->neigh[n] && ! el->neigh[n]->used) { 
         *np = (appearence *) alloc (sizeof (appearence)); 
         (*np)->elementvar = el->neigh[n]; 
         (*np)->next = shiftel (el->neigh[n]); 
         do 
            np = & (*np)->next; 
         while (*np); 
      } 
   return result; 
} 

void shift (shape * figure) 
{ 
   while (figure) { 
      appearence * app = figure->appearencevar; 
      while (app) { 
         appearence * help = app->next; 
         app->next = shiftel (app->elementvar); 
         elementunuse (app->elementvar); 
         while (app->next) 
            app = app->next; 
         app->next = help; 
         app = app->next; 
      } 
      figure = figure->next; 
   } 
   return; 
} 

/*------------------------------------+------------------------------------*/


void surround (place * field) 
{ 
   unsigned n; 

   place * border = (place *) alloc (sizeof (place)); 
   border->name = NULL; 
   border->neigh = (place   **) alloc (nnn * sizeof(place  *)); 
   border->conn  = (unsigned *) alloc (nnn * sizeof(unsigned)); 
   for (n=0; n<nnn; n++) { 
      border->neigh[n] = NULL; 
      border->conn [n] = 0; 
   } 
   border->occ = (element *) alloc (sizeof (element)); 
   border->next = NULL; 

   border->occ->name = NULL; 
   border->occ->used = FALSE; 
   border->occ->neigh = (element **) alloc (nnn * sizeof(element *)); 
   border->occ->conn  = (unsigned *) alloc (nnn * sizeof(unsigned )); 
   border->occ->value = (char    **) alloc (nnn * sizeof(char    *)); 
   for (n=0; n<nnn; n++) { 
      border->occ->neigh[n] = NULL; 
      border->occ->conn [n] = 0; 
      border->occ->value[n] = valueaddress ("0"); 
   } 

   while (field) { 
      for (n=0; n<nnn; n++) 
         if (! field->neigh[n]) { 
            field->neigh[n] = border; 
            field->conn [n] = n; 
         } 
      field = field->next; 
   } 
   return; 
} 


place * trans (place * f, place * s) 
{ 
   static struct table * list = NULL; 
   struct table ** lp = & list; 

   if (f) { 
      while (*lp && (*lp)->org != f) 
         lp = & (*lp)->next; 
      if (s && ! *lp) { 
         *lp = (struct table *) alloc (sizeof (struct table)); 
         (*lp)->org = f; 
         (*lp)->res = s; 
         (*lp)->next = NULL; 
      } 
      return (*lp) ? (place *)(*lp)->res : (f->name) ? NULL : f; 
   } else { 
      while (list) { 
         struct table * help = list; 
         list = list->next; 
         free (help); 
      } 
      return NULL; 
   } 
} 

boolean same (place * s, place * f, unsigned ind[]) 
{ 
   unsigned n; 

   trans (f, s); 
   if (f->occ->name != s->occ->name) 
      return FALSE; 
   for (n=0; n<nnn; n++) 
      if (f->occ->value[ind[n]] != s->occ->value[n]) 
         return FALSE; 
   for (n=0; n<nnn; n++) 
      if (! f->neigh[ind[n]] == ! s->neigh[n]) 
         if (s->neigh[n]) 
            if (f->conn[ind[n]] == ind[s->conn[n]]) 
               if (trans (f->neigh[ind[n]], NULL)) 
                  if (trans (f->neigh[ind[n]], NULL) == s->neigh[n]) 
                     continue; 
                  else 
                     return FALSE; 
               else 
                  if (same (s->neigh[n], f->neigh[ind[n]], ind)) 
                     continue; 
                  else 
                     return FALSE; 
            else 
               return FALSE; 
         else 
            continue; 
      else 
         return FALSE; 
   return TRUE; 
} 

struct sol { 
   place * entry; 
   struct sol * next; 
}; 

place * fieldcopy (place * field) 
{ 
   place * f; 
   place * result = NULL; 
   place ** rp = & result; 
   unsigned n; 

   trans (NULL, NULL); 
   for (f=field; f; f=f->next) { 
      *rp = (place *) alloc (sizeof (place)); 
      trans (f, *rp); 
      (*rp)->name = f->name; 
      (*rp)->neigh = (place   **) alloc (nnn * sizeof(place  *)); 
      (*rp)->conn  = (unsigned *) alloc (nnn * sizeof(unsigned)); 
      (*rp)->occ = f->occ; 
      rp = & (*rp)->next; 
   } 
   *rp = NULL; 
   for (f=field, rp= &result; f; f=f->next, rp= &(*rp)->next) 
      for (n=0; n<nnn; n++) { 
         (*rp)->neigh[n] = (f->neigh[n]) ? trans (f->neigh[n], NULL) : NULL; 
         (*rp)->conn [n] = f->conn[n]; 
      } 
   return result; 
} 

boolean known (place * field, permutation * rotations) 
{ 
   static struct sol * solist = NULL; 
   struct sol ** s; 
   place * f; 
   permutation * r; 

   permutation rotation0; 
   unsigned n; 
   rotation0.indices = (unsigned *) alloc (nnn * sizeof (unsigned)); 
   for (n=0; n<nnn; n++) 
      rotation0.indices[n] = n; 
   rotation0.next = rotations; 

   for (s= &solist; *s; s= &(*s)->next) 
      for (f=field; f; f=f->next) 
         if (f->occ->name == (*s)->entry->occ->name) 
            for (r= &rotation0; r; r=r->next) { 
               trans (NULL, NULL); 
               if (same ((*s)->entry, f, r->indices)) { 
                  free (rotation0.indices); 
                  return TRUE; 
               } 
            } 
   *s = (struct sol *) alloc (sizeof (struct sol)); 
   (*s)->entry = fieldcopy (field); 
   (*s)->next = NULL; 
   free (rotation0.indices); 
   return FALSE; 
} 

void new_solution (place * field) 
{ 
   static unsigned count = 0; 
   if (distributed) 
      printf ("%d\n", part); 
   else { 
      printf ("%d", count++); 
      fflush (stdout); 
      fprintf (stderr, "\a"); 
      printf ("\n"); 
   } 
   while (field) { 
      unsigned n; 
      printf ("%s\t%s\t", field->name, field->occ->name); 
      for (n=0; n<nnn; n++) 
         printf ("%s ", field->occ->value[n]); 
      printf ("\n"); 
      field = field->next; 
   } 
   printf ("\n"); 
   fflush (stdout); 
   return; 
} 

void notice (place * total_field, permutation * rotations) 
{ 
   static place       * field = NULL; 
   static permutation * rotat = NULL; 

   if (total_field) { 
      field = total_field; 
      rotat = rotations; 
   } else 
      if (distributed || ! known (field, rotat)) 
         new_solution (field); 
   return; 
} 

/*------------------------------------+------------------------------------*/


# define FIT(a,b) 1 /*((a) != (b))*/ 

# ifdef SIMPLE 

boolean fitting (place * field, element * el) 
{ 
   unsigned n; 

   if (squeezing) { 
      if (field->solutionocc && strcmp (el->name, field->solutionocc->name)) 
         return FALSE; 
      for (n=0; n<nnn; n++) 
         if (field->solutionvalue[n] && el->value[n] != field->solutionvalue[n]) 
            return FALSE; 
   } 
   for (n=0; n<nnn; n++) 
      if (field->neigh[n] && field->neigh[n]->occ) 
         if (! FIT (el->value[n], field->neigh[n]->occ->value[field->conn[n]])) 
            return FALSE; 
   return TRUE; 
} 

# define insert(field,el)  ((field)->occ=(el)) 
# define deleet(field,el)  ((field)->occ=NULL) 

# else 

boolean fitting (place * field, element * el) 
{ 
   unsigned n; 

   if (squeezing) { 
      if (field->solutionocc && strcmp (el->name, field->solutionocc->name)) 
         return FALSE; 
      for (n=0; n<nnn; n++) 
         if (field->solutionvalue[n] && el->value[n] != field->solutionvalue[n]) 
            return FALSE; 
   } 
   for (n=0; n<nnn; n++) 
      if (field->neigh[n] && field->neigh[n]->occ) 
         if (! FIT (el->value[n], field->neigh[n]->occ->value[field->conn[n]])) 
            return FALSE; 
   el->used = TRUE; 
   for (n=0; n<nnn; n++) 
      if (el->neigh[n] && ! el->neigh[n]->used) 
         if (! field->neigh[n] || field->neigh[n]->occ || 
             ! fitting (field->neigh[n], el->neigh[n])  ) 
            return el->used = FALSE; 
   el->used = FALSE; 
   return TRUE; 
} 

void insert (place * field, element * el) 
{ 
   unsigned n; 

   field->occ = el; 
   el->used = TRUE; 
   for (n=0; n<nnn; n++) 
      if (el->neigh[n] && ! el->neigh[n]->used) 
         insert (field->neigh[n], el->neigh[n]); 
   el->used = FALSE; 
   return; 
} 

void deleet (place * field, element * el) 
{ 
   unsigned n; 

   field->occ = NULL; 
   el->used = TRUE; 
   for (n=0; n<nnn; n++) 
      if (el->neigh[n] && ! el->neigh[n]->used) 
         deleet (field->neigh[n], el->neigh[n]); 
   el->used = FALSE; 
   return; 
} 

# endif 

void fill (place * field, shape * figures) 
{ 
   static unsigned depth = 0; 
   shape * i; 
   appearence * j; 

   if (field) 
      for (i=figures; i; i=i->next) 
         if (i->unused) 
            for (j=i->appearencevar; j; j=j->next) 
               if (fitting (field, j->elementvar)) { 
                  i->unused--; 
                  insert (field, j->elementvar); 
                  if (depth < messages && ! distributed && ! blind) { 
                     unsigned n = depth; 
                     while (n--) 
                        fprintf (stderr, "\t"); 
                     fprintf (stderr, "%s\n", field->occ->name); 
                  } 
                  if ((! distributed && ! blind) || 
                     (distributed && pn==part) || 
                     depth < messages 
                  ) { 
                     place * f = field; 
                     shape * g = figures; 
                     do 
                        f = f->next; 
                     while (f && f->occ); 
                     while (g && g->unused==0) 
                        g = g->next; 
                     depth++, fill (f, g), depth--; 
                  } 
                  deleet (field, j->elementvar); 
                  i->unused++; 
                  if (depth==messages && (distributed || blind)) 
                     if (pn==part && distributed) 
                        exit (0); 
                     else 
                        pn++; 
               } else 
                  continue; 
         else 
            continue; 
   else 
      notice (NULL, NULL); 
   return; 
} 

/*------------------------------------+------------------------------------*/


const char * ANYTHING = "*"; 

void squeeze (place ** field, shape * figures) 
{ 
   int c; 
   unsigned n; 
   char buffer[NAMESIZE]; 
   place * plad; 

   FILE * fp = fopen (squeezing, "r"); 
   if (fp == NULL) { 
      fprintf (stderr, "Cannot open %s.\n", squeezing); 
      exit (1); 
   } 
   while ((c=getc (fp)) != EOF) { 
      ungetc (c, fp); 
      fscanf (fp, "%d", &n); 
      if (getc (fp) != '\n') 
         fprintf (stderr, "Squeeze input misformatted.\n"); 
      while ((c=getc (fp)) != '\n') { 
         ungetc (c, fp); 
         fscanf (fp, "%s", buffer); 
         c = getc (fp); 
         while (c==' ' || c=='\t') 
            c = getc (fp); 
         ungetc (c, fp); 
         plad = placeaddress (buffer, field); 
         fscanf (fp, "%s", buffer); 
         c = getc (fp); 
         while (c==' ' || c=='\t') 
            c = getc (fp); 
         ungetc (c, fp); 
         if (strcmp (buffer, ANYTHING)) 
            plad->solutionocc = elementaddress (buffer); 
         for (n=0; n<nnn; n++) { 
            fscanf (fp, "%s", buffer); 
            c = getc (fp); 
            while (c==' ' || c=='\t') 
               c = getc (fp); 
            ungetc (c, fp); 
            if (strcmp (buffer, ANYTHING)) 
               plad->solutionvalue[n] = valueaddress (buffer); 
         } 
         if (getc (fp) != '\n') 
            fprintf (stderr, "Squeeze input misformatted.\n"); 
      } 
      fill (*field, figures); 
      for (plad= *field; plad; plad=plad->next) { 
         plad->solutionocc = NULL; 
         for (n=0; n<nnn; n++) 
            plad->solutionvalue[n] = NULL; 
      } 
   } 
   elementaddress (NULL); 
   fclose (fp); 
} 

/*------------------------------------+------------------------------------*/


int main (unsigned argc, char ** argv) 
{ 
   permutation * rotations; 
   place * field; 
   shape * figures; 

   int in, out; 
   char usage[] = "Usage:  %s [-t] [-n] [-s] [-m#] [-x#] [-z file] [ infile [ outfile ] ]"; 

   unsigned n; 
   for (n=1; n<argc && argv[n][0]=='-'; n++) 
      switch (argv[n][1]) { 
      case 'm': 
         messages = atoi (argv[n]+2); 
         break; 
      case 'n': 
         norotate = TRUE; 
         break; 
      case 's': 
         surrounding = TRUE; 
         break; 
      case 't': 
         testing = TRUE; 
         break; 
      case 'x': 
         if (argv[n][2]) { 
            distributed = TRUE; 
            part = atoi (argv[n]+2); 
         } else 
            blind = TRUE; 
         break; 
      case 'z': 
         squeezing = argv[++n]; 
         break; 
      case 'h': 
      case '?': 
         fprintf (stderr, usage, argv[0]); 
         fprintf (stderr, "\n"); 
         return 0; 
      default: 
         fatal ("Unknown option."); 
      } 

   switch (argc-n) { 
   case 2: 
      if ((out = creat (argv[n+1], 0644)) == -1) 
         fatal ("Outfile %s cannot be opened !", argv[n+1]); 
      if (out != 1) { 
         dup2 (out, 1); 
         close (out); 
      } 
   case 1: 
      if ((in = open (argv[n], 0)) == -1) 
         fatal ("Infile %s cannot be opened !", argv[n]); 
      if (in != 0) { 
         dup2 (in, 0); 
         close (in); 
      } 
   case 0: 
      break; 
   default: 
      fatal (usage, argv[0]); 
   } 

   rotations = read_rotations (); 
   field = read_field (); 
   figures = read_figures (); 
   if (! distributed && ! blind) 
      fprintf (stderr, "\a"); 

   if (testing) 
      inputtest (rotations, field, figures); 
   else { 
      rotate (norotate ? figures->next : figures, rotations); 
      shorten (figures); 
      netto (figures); 
      shift (figures); 
      if (! distributed && ! blind) 
         fprintf (stderr, "\a"); 

      if (surrounding) 
         surround (field); 
      notice (field, rotations); 
      if (squeezing) 
         squeeze (& field, figures); 
      else 
         fill (field, figures); 
      if (! distributed && ! blind) 
         fprintf (stderr, "\a"); 

      if (blind) 
         printf ("%d\n", pn); 
   } 
   return 0; 
} 

/*====================================+====================================*/