/* Stan supplied this updated version 7/9/96 after reports that the
	previously posted entry was garbled ... my apologies ... =Fred */

/* POTM ENTRY : crossroads              */
/* Author : Stan Peijffers              */
/* E-mail : s.peijffers@nl.lucent.com   */

#include "stdio.h"
#include <sys/times.h>
#include "stdlib.h"

#define CLK_TCK 60     /* Note: this may be different on YOUR box, you
                           might find the value of HZ in YOUR param.h, but
                           it's gotta be 100 when you ship your entry!
                           Alternatively, use sysconf to deduce CLK_TCK -
                           this approach should work on both systems!    */

#define MAXWORDS 200
#define WRDL 20
#define HMAX 20
#define VMAX 20
#define NBLTRS 26
#define MAXPR (MAXWORDS / 32 + 1)

#define HORAL 0x20
#define VERAL 0x40
#define DIRS (HORAL+VERAL)

#define LETTER 0x1f
#define CTRS 0xe0
#define INCTR 0x20

#define XVAL 10
#define WVAL 10000

#define WINDOW 3

#define MIN(a, b) (((a) < (b))? (a) : (b))
#define MAX(a, b) (((a) > (b))? (a) : (b))
#define ABS(a, b) (((a) <= (b))? (b) - (a) : (a) - (b))

FILE *ifile;
int trace;
int nbrwrds;

typedef struct {
int wl;
int wval;
char word[WRDL];
} t_words;

t_words wrdtab[MAXWORDS];

typedef struct {
int ch1l;
int wor1[MAXWORDS];
int del1[MAXWORDS];
} t_word1;

typedef struct {
int ch2l;
int wor2[MAXWORDS];
int del2[MAXWORDS];
} t_word2;

t_word1 tr1[NBLTRS];
t_word2 tr2[32*NBLTRS];


int letct[NBLTRS];

typedef struct {
unsigned char raster[HMAX+2][VMAX+2];
unsigned char hword[HMAX+2][VMAX+2];
unsigned char vword[HMAX+2][VMAX+2];
unsigned int printed[MAXPR];
} t_state;

t_state board;
t_state sv2_board;
t_state final_board;

int finalbest;
int bestmov;
int cbest;
int next;
int hnext;
int wctoff;
int ll,llw;

t_state bestboard[3];
int bestwct[3];
int artinum[3];
int artictr[3];
int artidfn[3][MAXWORDS];
int artil[3][MAXWORDS];

int wlow[3];
int whigh[3];

typedef struct {
int tabuwrd;
int tabux;
int tabuy;
int tabudir;
} t_exc;

t_exc exc;

main(argc,argv)
int argc;
char *argv[];
{
int wct;

ifile = fopen(argv[1],"r");
trace = atoi(argv[2]);

init_tables();

if (llw>15)
{
next = ll;
hnext = 1;

do
 {
  reinit_tables();
  first_move();
    bestmov=0;
    select_move(1,HMAX,1,VMAX,0,1);
    if ((bestmov) && (bestmov<2*WVAL))
     cp_board(&sv2_board, &board);
  do 
   {
    bestmov=0;
    select_move(1,HMAX,1,VMAX,0,1);
    if ((bestmov) && (bestmov<2*WVAL))
     cp_board(&sv2_board, &board);
   } while (bestmov);
  
  wct = ct_wrds(&board);

  if (trace)
     printf(" improvment new val %d\n", wct);

  if (wct>finalbest)
  {
  if (wct == nbrwrds)
   {
    prt_sol(&board);
    exit(0);
   }
  cp_board(&board, &final_board);
  finalbest = wct;
  }

 }
  while (hnext++ <= VMAX);
}

next=0;
hnext=VMAX/2 -1;

do
 {
  reinit_tables();
  first_move();
    bestmov=0;
    select_move(1,HMAX,1,VMAX,0,1);
    if ((bestmov) && (bestmov<2*WVAL))
     cp_board(&sv2_board, &board);
  do 
   {
    bestmov=0;
    select_move(1,HMAX,1,VMAX,0,1);
    if ((bestmov) && (bestmov<2*WVAL))
     cp_board(&sv2_board, &board);
   } while (bestmov);
  
  wct = ct_wrds(&board);

  if (trace)
     printf(" improvment new val %d\n", wct);
  if (wct< bestwct[0]-3)
   continue;


  cp_board(&board, &bestboard[0]);
  if (trace)
     prt_sol(&bestboard[0]);

  if (wct>finalbest)
  {
  if (wct == nbrwrds)
   {
    prt_sol(&board);
    exit(0);
   }
  cp_board(&board, &final_board);
  finalbest = wct;
  }

  if (trace)
   printf(" start new phase %d\n", 0);

  if ((wct>=bestwct[0]-1) && (checktime()))
   {
    bestwct[0] = wct;
    improv_sol();
   }

  if (checktime())
  {
  bestwct[0] = wct;
  arti(0);

  improv_sol();
  }

 }
  while ((next++ < nbrwrds-1) && (checktime()));

  prt_sol(&final_board);
  exit(0);
}

improv_sol()

{

if (trace)
     prt_sol(&bestboard[0]);

if (bestwct[0]< bestwct[1]-3)
   return;

bestwct[1] = bestwct[0];


cp_board(&bestboard[0], &bestboard[1]);
if (trace)
   printf(" start new phase %d\n", 1);
while (arti(1));

if (trace)
     prt_sol(&bestboard[1]);

if (bestwct[1]< bestwct[2]-3)
   return;

bestwct[2] = bestwct[1];

/*
if (next==3)
 trace = 2;
*/

cp_board(&bestboard[1], &bestboard[2]);
if (trace)
   printf(" start new phase %d : dpth = %d\n", 2,
             (4-(nbrwrds-bestwct[2])/40));
while (arti(2));

}


checktime()
{
        int seconds;
        static struct tms TMS;
        times(&TMS);
        /* add the elapsed system and user times                           */
        /* calculation comes out to the nearest second - rounded down ...  */
        seconds = (TMS.tms_stime + TMS.tms_utime)/CLK_TCK ;

        return (seconds >=570)?0:1;
 
}

fill_tables()
{
int m,m1,m2;
int i,j,j1,j2,ltr,ltr1,ltr2;

for (i=0;i<nbrwrds;i++)
 {
  j = wrdtab[i].wl;

  if (j > llw)
   {
    llw=j;
    ll =i;
   }

    for (m=0;m<j;m++)
     {
     ltr = wrdtab[i].word[m] - 97;
     tr1[ltr].del1[tr1[ltr].ch1l] = m+1;
     tr1[ltr].wor1[tr1[ltr].ch1l++] = i;
     }

    for (m1=0;m1<j-1;m1++)
     {
      m2 = m1 + 1;

     ltr1 = wrdtab[i].word[m1] - 97;
     ltr2 = wrdtab[i].word[m2] - 97;
     ltr = (ltr1<<5)+ltr2;

     tr2[ltr].wor2[tr2[ltr].ch2l] = i;
     tr2[ltr].del2[tr2[ltr].ch2l++] = m2;

     }

 }

if (trace>3)
 {
  printf("nbr words %d\n", nbrwrds);

  for (j=0;j<NBLTRS;j++)
   for (i=0;i<tr1[j].ch1l;i++)
   {
     printf(" %c %d %d\n", j+97, tr1[j].wor1[i], tr1[j].del1[i]);
   }

  printf(" 2letters\n");

  for (j1=0;j1<NBLTRS;j1++)
  for (j2=0;j2<NBLTRS;j2++)
   for (i=0;i<tr2[(j1<<5)+j2].ch2l;i++)
   {
     printf(" %c %c %d %d\n", j1+97, j2+97, 
            tr2[(j1<<5)+j2].wor2[i], tr2[(j1<<5)+j2].del2[i]);
   }

  printf("letter count\n");
  for (i=0;i<NBLTRS;i++)
   printf(" letter %c : %d\n", (char)i+97, letct[i]);

 }

}

reinit_tables()
{
int i;
int k,l;

for (k=0;k<=nbrwrds/32;k++)
 board.printed[k]=0;
for (k=0;k<=HMAX+1;k++)
 for (l=0;l<=VMAX+1;l++)
  {
  board.raster[k][l]=0;
  board.hword[k][l]=0;
  board.vword[k][l]=0;
  }

/* init border of raster */

for (i=1;i<HMAX+2;i++)
 {
  board.raster[i][0] = 0x20;
  board.raster[i][VMAX+1] = 0x20;
 }
for (i=1;i<VMAX+2;i++)
 {
  board.raster[0][i] = 0x20;
  board.raster[HMAX+1][i] = 0x20;
 }
}

init_tables()
{
int i,j,k,t;
int ewl;
int val1,val2,ssgp,step;
char tmp[WRDL];
char c;


/* read in words */

i=j=0;
while ((c=getc(ifile)) != EOF)
 {
  if (c == '\n')
   {
    wrdtab[i].wl = j;
    i++;
    j=0;
   }
  else
  {
   wrdtab[i].word[j++] = c;
   letct[c-97]++;
  }
 }
nbrwrds = i;

reinit_tables();

/* calculate word values */

for (i=0;i<nbrwrds;i++)
 {
 for (j=0;j<wrdtab[i].wl;j++)
  wrdtab[i].wval += letct[wrdtab[i].word[j] - 97];

 ewl = ABS(wrdtab[i].wl,4) + 2;

 wrdtab[i].wval /= (ewl*ewl);
 wrdtab[i].wval *=2;

 }

/* now sort (dichotomic algorithm) */

ssgp=nbrwrds;
while (ssgp)
 {
  step = ssgp;
  ssgp = ssgp & (ssgp-1);
 }

ssgp=step;
while (ssgp)
 {
  for (j=0;j<nbrwrds-ssgp;j++)
   {
    k=j;
    while (k>=0)
    {
    val1 = wrdtab[k+ssgp].wval;
    val2 = wrdtab[k].wval;
    if (val2<val1)
     {
      t=wrdtab[k].wval; 
      wrdtab[k].wval=wrdtab[k+ssgp].wval;
      wrdtab[k+ssgp].wval=t; 

      for (i=0;i<wrdtab[k].wl;i++)
       tmp[i] = wrdtab[k].word[i];

      for (i=0;i<wrdtab[k+ssgp].wl;i++)
       wrdtab[k].word[i] = wrdtab[k+ssgp].word[i];

      for (i=0;i<wrdtab[k].wl;i++)
       wrdtab[k+ssgp].word[i] = tmp[i];

      t=wrdtab[k].wl; 
      wrdtab[k].wl=wrdtab[k+ssgp].wl;
      wrdtab[k+ssgp].wl=t; 
     }
     else break;
    k-=ssgp;
    }
   }
  ssgp>>=1;
 }

if (trace>8)
{
for (i=0;i<nbrwrds;i++)
 {
  for (j=0;j<wrdtab[i].wl;j++)
   printf("%c", wrdtab[i].word[j]);
  printf("\n");
 }

exit(0);
}

fill_tables();

}

first_move ()
{
int i;
int firstv;

if (trace)
 printf(" best is now %d\n", next);

firstv=HMAX/2-wrdtab[next].wl;

if (firstv>0)
 move(next, firstv, hnext, 0, HORAL, &board, &i);
 else
 move(next, 1, hnext, 0, HORAL, &board, &i);

}

arti(ap)
int ap;
{
int i,j,k,l;
int sx,sy,sdir;
int ret;

/* works non-destructively on bestboard[ap] */
/* init arti variables */

switch (ap)
{
case 0 :
wlow[0] = bestwct[0]-WINDOW;
whigh[0] = bestwct[0];
break;

case 1 :
wlow[1] = WINDOW;
whigh[1] = bestwct[1]/2;
break;

case 2 :
wlow[2] = 0;
whigh[2] = WINDOW+10;
}

artictr[ap] = 0;
artinum[ap] = 1;

for (i=0;i<nbrwrds;i++)
 artidfn[ap][i]=artil[ap][i]=0;

for (i=1;i<=HMAX;i++)
   for (j=1;j<=VMAX;j++)
    if (((bestboard[ap].raster[i][j] & LETTER) == 0) &&
         (bestboard[ap].raster[i][j] & CTRS) &&
         (((bestboard[ap].raster[i+1][j] & LETTER) && 
           (bestboard[ap].raster[i+2][j] & LETTER)) ||
          ((bestboard[ap].raster[i][j+1] & LETTER) &&
           (bestboard[ap].raster[i][j+2] & LETTER))))

{
if ((bestboard[ap].raster[i+1][j] & LETTER) && (bestboard[ap].raster[i+2][j] & LETTER))
   {
   sdir = HORAL;
   sx = i+1;
   sy = j;
   }
  else
   {
   sdir = VERAL;
   sy = j+1;
   sx = i;
   }

/* position on the first non-cross square. If all letters are cross... */
 
k=l=0; 
while (bestboard[ap].raster[sx+k][sy+l] & LETTER)
 if ((bestboard[ap].raster[sx+k][sy+l] & DIRS) != DIRS)
  break;
  else
  if (sdir==HORAL) k++; else l++;

if (bestboard[ap].raster[sx+k][sy+l] & LETTER)
 goto cc;
}

return 0;
cc:

cbest = bestwct[ap];
ret=art (ap,sx+k,sy+l,sdir);

if (ret==1)
 {
  if (trace)
   printf("new cycle new value : %d\n", bestwct[ap]);
  return 1;
 }
return 0;
}

art(ap,sx,sy,sdir)
int ap;
int sx;
int sy;
int sdir;
{
int sw, w2,i,dx,dy;
int lartictr,ret;

/* sx , sy any square */

sw = (sdir==HORAL)? bestboard[ap].hword[sx][sy]:bestboard[ap].vword[sx][sy];

artidfn[ap][sw] = artil[ap][sw] = artinum[ap]++;

if (trace>1)
 printf (" --> art : ap %d, sx %d, sy %d, sdir %d, sw %d, num %d\n",
    ap, sx,sy,sdir,sw, artinum[ap]-1);

for (i=-1; i<=1; i+=2)
 {
  dx = (sdir==HORAL)? 1:0; 
  dy = (sdir==HORAL)? 0:1; 

  while (bestboard[ap].raster[sx+i*dx][sy+i*dy] & LETTER)
   {
    if ((bestboard[ap].raster[sx+i*dx][sy+i*dy] & DIRS) == DIRS)
     {
      w2 = (sdir==HORAL)?bestboard[ap].vword[sx+i*dx][sy+i*dy]:
                         bestboard[ap].hword[sx+i*dx][sy+i*dy];

      if (artidfn[ap][w2] == 0)
       {

        lartictr = ++artictr[ap]; 
        if (ret=art(ap, sx+i*dx, sy+i*dy, sdir ^ DIRS))
         return ret;

        if (artil[ap][w2] >= artidfn[ap][sw])
         {
          if (trace>1)
           printf(" articulation point (1) : sx %d sy %d wrd %d (w2 %d) - ct %d lo %d hi %d\n",
               sx+i*dx, sy+i*dy, sw, w2, artictr[ap] - lartictr + 1, wlow[ap], whigh[ap]);

          if (arti_point(ap, sx+i*dx, sy+i*dy, 
                   sw, w2, sdir, artictr[ap]-lartictr + 1))
           return 1;

          if (artil[ap][w2] > artidfn[ap][sw])
          {
          if (trace>1)
           printf(" articulation point (2) : sx %d sy %d wrd %d (w2 %d) - ct %d lo %d hi %d\n",
               sx+i*dx, sy+i*dy, w2, sw, cbest -(artictr[ap] - lartictr + 1), wlow[ap], whigh[ap]);

          if (arti_point(ap, sx+i*dx, sy+i*dy, 
                   w2, sw, sdir ^ DIRS, cbest-artictr[ap]+lartictr - 1))
           return 1;

          }
         }
     
        artil[ap][sw] = MIN(artil[ap][sw], artil[ap][w2]);

       }
      else
       artil[ap][sw] = MIN(artil[ap][sw], artidfn[ap][w2]);
     }
      
    if (sdir==HORAL) dx++; else dy++;
   }
 } /* endfor */

return 0;
}

arti_point(ap, sx, sy, w1, w2, sdir, wct)
int ap;
int sx;
int sy;
int w1;
int w2;
int sdir;
int wct;
{
int k,l;
int ct,ret;
int lim;

          if ((wct > wlow[ap]) && (wct < whigh[ap]))
          {
          cp_board(&bestboard[ap],&board);
          
          k=l=0;
          while (board.raster[sx-k][sy-l] & LETTER)
            if (sdir==HORAL) l++; else k++;

          wremove (sx-k, sy-l, sdir ^ DIRS, w1);

          if (trace>1)
           {
           printf("trimmed raster\n");
           prt_sol (&board);
           }

          if (ap)
           {
            exc.tabuwrd = w2;
            exc.tabux = sx-k+((sdir==VERAL)?1:0);
            exc.tabuy = sy-l+((sdir==VERAL)?0:1);
            exc.tabudir = sdir ^ DIRS;
            if (trace>1)
             printf(" tabu wrd %d x %d y %d dir %d\n", 
               exc.tabuwrd, exc.tabux, exc.tabuy, exc.tabudir);
           }

           do 
            {
             bestmov=0;
             lim = 3 -(nbrwrds-bestwct[2]+wct)/40;
             lim = MAX(lim,1);
             if (lim==3) lim = 4;

             if (wlow[ap] || (wct>lim))
              {
              select_move(1,HMAX,1,VMAX,0,1);
              if ((bestmov) && (bestmov < 2*WVAL))
                cp_board(&sv2_board, &board);
              }
              else
              {
              wctoff=(wct+1)*WVAL;
              ret = select_move(1,HMAX,1,VMAX,1,0);
              if ((bestmov) && (ret==0))
                cp_board(&sv2_board, &board);
              }

            } while (bestmov);

          ct = ct_wrds(&board); 
            if (trace>1)
             {
              printf(" new raster (ct %d)\n", ct);
              prt_sol(&board);
             }
          if (ct > bestwct[ap]) 
           {
            if (trace)
             printf(" new improved raster (ct %d) %d wrds removed\n", ct, wct);
            if (ct > finalbest)
             {
             if (ct == nbrwrds)
              {
               prt_sol(&board);
               exit(0);
              }
              finalbest = ct;
              cp_board(&board, &final_board);
             }
              cp_board(&board, &bestboard[ap]);
              bestwct[ap] = ct;
              return 1;
           }
          }
return 0;
}

check_move (sx, sy, dir, brd)
int sx;
int sy;
int dir;
t_state *brd;
{
t_state nbrd;
t_state sv_board;
int i,j,k,w;
int bestval=0;
int id,jd,ln,hn,ltr,dlt,idlt,jdlt;
int nblet,mvval1,mvval2,mval;
int dirs;
int wrdval=0;
t_word2 *t2p;


if (trace > 3)
 {
 printf(" check : dir %d, sx %d, sy %d\n", dir, sx, sy);
 }

i=j=0;
id = (dir==HORAL)? 1:0;
jd = (dir==HORAL)? 0:1;

while ((ltr=brd->raster[sx+i][sy+j] & LETTER) &&
       ((((dirs=brd->raster[sx+i][sy+j] & DIRS)) == DIRS) ||
        (((brd->raster[sx+i-jd][sy+j-id] & LETTER)==0) && 
         ((brd->raster[sx+i+jd][sy+j+id] & LETTER)==0))))
 {
  i += id;
  j += jd;
  if (dirs == DIRS)
   wrdval += XVAL;
 }

if (ltr==0)
 return WVAL+wrdval;

cp_board(brd, &nbrd);

ltr = brd->raster[sx+i][sy+j] & LETTER;
ln = brd->raster[sx+i-jd][sy+j-id] & LETTER;
hn = brd->raster[sx+i+jd][sy+j+id] & LETTER;
       
if (ln)
 t2p = &tr2[(ln-1<<5)+ltr-1];
 else
 t2p = &tr2[(ltr-1<<5)+hn-1];

for (k=0;k<t2p->ch2l;k++)
 {
  dlt = t2p->del2[k] + (ln?1:0);
  w = t2p->wor2[k];

  if (((brd->printed[w >> 5] & (1<< (w & 0x1f))) == 0) &&
      ((dir==HORAL)? ((sy-dlt+1>0) && (sy-dlt+wrdtab[w].wl <= VMAX)):
                     ((sx-dlt+1>0) && (sx-dlt+wrdtab[w].wl <= HMAX))))
   {

    idlt = (dir==VERAL)?dlt-1:0;
    jdlt = (dir==VERAL)?0:dlt-1;

    nblet = move (w, sx+i, sy+j, dlt-1, dir ^ DIRS, &nbrd, &mval);
   
    if (nblet == wrdtab[w].wl+1)
     {
      mvval1 = check_move (sx+i-idlt, sy+j-jdlt, dir ^ DIRS, &nbrd);
   
      if (mvval1)
        mvval2 = check_move (sx+i+id, sy+j+jd, dir, &nbrd);

      if ((mvval1 && mvval2) && 
          (mvval1+mvval2+wrdtab[w].wval + mval > bestval))
          {
           bestval = mvval1+mvval2+wrdtab[w].wval + mval;
           if (bestval > 2*WVAL)
            {
            cp_board(&nbrd, brd);
            if (trace > 2)
             printf(" retcheck val %d %d %d %d\n", wrdval, bestval, mvval1, mvval2);
            return wrdval+bestval;
            }
           else
            cp_board(&nbrd, &sv_board);
          }

      unmove (w, sx+i-idlt, sy+j-jdlt, 
                        dir ^ DIRS, wrdtab[w].wl+1, &nbrd);

     }
    else
      unmove (w, sx+i-idlt, sy+j-jdlt, dir ^ DIRS, nblet, &nbrd);
   }
 }
      
 if (bestval)
  {
   cp_board(&sv_board, brd);
   return wrdval+bestval;
  }
 else
  return 0;
}

ct_wrds(brd)
t_state *brd;
{
int ct=0;
int i,ict,ibits;

for (i=0;i<=nbrwrds/32;i++)
 {
  ict = 0;
  ibits = brd->printed[i];

  while (ibits)
   {
    ibits &= ibits-1;
    ict++;
   }
  ct += ict;
 }
return ct;
}

cp_board(frbrd,tobrd)
unsigned int *frbrd;
unsigned int *tobrd;
{
unsigned int *ep = &frbrd[363+nbrwrds/32];

while (frbrd<=ep)
 *tobrd++ = *frbrd++;

}

select_move (sx,ex,sy,ey,selval,dpth)
int sx;
int ex;
int sy;
int ey;
int selval;
int dpth;
{
t_word1 *t1p;
int i,j,k;
int w;
int nblet,mvval,mval,totval;
int ltr,dir,dlt,idlt,jdlt;

/* return 1 means : stop : multimove;
   return 0 means : continue */

if (trace>2)
 {
 printf("--> select_move : sx %d ex %d sy %d ey %d selval %d\n",
         sx,ex,sy,ey,selval);
 prt_sol(&board);
 }

 for (i=sx;i<=ex;i++)
  for (j=sy;j<=ey;j++)
   {
   ltr = board.raster[i][j] & LETTER;
   dir = board.raster[i][j] & DIRS;

   if (ltr && (dir != DIRS))
    {

     if (trace > 3)
      printf(" square check i %d j %d (%c)\n", i,j, (char) (ltr+96));

     dir ^= DIRS;

     t1p = &tr1[ltr-1];

     for (k=0;k<t1p->ch1l;k++)
      {
      w = t1p->wor1[k];
      dlt = t1p->del1[k];
      if (((board.printed[w >> 5] & (1<< (w & 0x1f))) == 0) &&
         ((dir==HORAL)? ((i-dlt+1>0) && (i-dlt+wrdtab[w].wl <= HMAX)):
                        ((j-dlt+1>0) && (j-dlt+wrdtab[w].wl <= VMAX))))
      {

       idlt = (dir==HORAL)?dlt-1:0;
       jdlt = (dir==HORAL)?0:dlt-1;

       if ((exc.tabuwrd == w) && 
           (exc.tabux == i-idlt) &&
           (exc.tabuy == j-jdlt) &&
           (exc.tabudir == dir))
        continue;

       nblet = move (w, i, j, dlt-1, dir, &board, &mval);

       if (nblet == wrdtab[w].wl+1)
        {
         mvval = check_move (i-idlt, j-jdlt, dir, &board);

         if (mvval)
         {
          if (selval)
           {
            if (select_move(1,HMAX,1,VMAX,
                     selval+mvval+wrdtab[w].wval+mval,0))
             return 1;
            totval = selval+mvval+wrdtab[w].wval+mval;
            }
          else
          if ((dpth) && (mvval<2*WVAL))
           {
            if (dir == VERAL)
            {
            if (select_move(i,i,j-1,j+1,0,dpth-1))
             return 1;
            }
            else
            {
            if (select_move(i-1,i+1,j,j,0,dpth-1))
             return 1;
            }
            totval = mvval+wrdtab[w].wval+mval;
            }
          else
           totval = mvval+wrdtab[w].wval+mval;

          if (mvval > 2*WVAL)
           {
           bestmov = totval;
           return 1;
           }

          if (totval > bestmov)
          {
           if (trace>2)
           printf(" best <-- : word %d dir %d at %d %d mvv %d wv %d mv %d \n", 
             w, dir, i-idlt, j-jdlt, 
              mvval,wrdtab[w].wval,mval);
           bestmov = totval;
           cp_board(&board, &sv2_board);
           if (selval && (totval> wctoff) && (bestwct[0]*5 < nbrwrds*2))
            return 1;
          }
         }

         unmove (w, i-idlt, j-jdlt, dir, wrdtab[w].wl+1, &board);

        }
        else
         unmove (w, i-idlt, j-jdlt, dir, nblet, &board);
      }
     }
    }

   if (bestmov && dpth && (bestwct[0]*5 < nbrwrds*2))
    return 0;

  } /* endfor i/j */

return 0;
}

move (wrd, xx, xy, dlt, dir, brd, val)
int wrd;
int xx;
int xy;
int dlt;
int dir;
t_state *brd;
int *val;
{
int i,j;
int dx,dy,sx,sy;
int wordl, ltr,ltr1,ltrl,ltrh;

if (trace>3)
 {
 printf(" move : word %d, dir %d, xx %d, xy %d dlt %d best %d\n", wrd, dir, xx, xy, dlt, bestmov);
 }

dx= (dir==HORAL);
dy= !dx;

sx= xx -dx*dlt;
sy= xy -dy*dlt;

if (brd->raster[sx-dx][sy-dy] & LETTER)
   return -1;
 else
   *val = brd->raster[sx-dx][sy-dy] += INCTR;

wordl = wrdtab[wrd].wl;

for (i=j=0;i+j<wordl;(dir==HORAL)?i++:j++)
  {

   ltr = brd->raster[sx+i][sy+j];

   if (ltr & LETTER)
    {
     if (((ltr & LETTER) != wrdtab[wrd].word[i+j] -96) ||
          (ltr & dir) || ((i+j<dlt) && (brd == &board)))
     /* last condition : don't evaluate move if a connector is seen 
        which is at the left of the current connector
        (only when a full scan of the board is made (ie. on &board)!) */

      return i+j;
     else
      {
      brd->raster[sx+i][sy+j] |= dir;
      if (dir==HORAL)
        brd->hword[sx+i][sy+j] = wrd;
       else
        brd->vword[sx+i][sy+j] = wrd;
      }
    }
    else
    {
     if (ltr) /* unplayable */
      return i+j;
     else
      {
      ltr1 = wrdtab[wrd].word[i+j] -96;
      ltrl = brd->raster[sx+i-dy][sy+j-dx] & LETTER;
      ltrh = brd->raster[sx+i+dy][sy+j+dx] & LETTER;

      if (ltrl && (tr2[(ltrl-1<<5) + ltr1-1].ch2l == 0))
       return i+j;

      if (ltrh && (tr2[(ltr1-1<<5) + ltrh-1].ch2l == 0))
       return i+j;
      
      brd->raster[sx+i][sy+j] = ltr1;
      brd->raster[sx+i][sy+j] |= dir;
      if (dir==HORAL)
        brd->hword[sx+i][sy+j] = wrd;
       else
        brd->vword[sx+i][sy+j] = wrd;
      }
    }
} /* endfor */
       
if (brd->raster[sx+dx*wordl][sy+dy*wordl] & LETTER)
   return wordl;
 else
   *val += brd->raster[sx+dx*wordl][sy+dy*wordl] += INCTR;

brd->printed[wrd >> 5] |= 1 << (wrd  & 0x1f);

return wordl+1;
}

unmove (wrd, sx, sy, dir, lgth, brd)
int wrd;
int sx;
int sy;
int dir;
int lgth;
t_state *brd;
{
int i = 0;
int j = 0;

/* sx and sy always >0 and <= V(H)MAX */

if (trace > 3)
 {
 printf(" unmove : word %d, dir %d, lgth %d, sx %d, sy %d\n", 
         wrd, dir, lgth, sx, sy);
 }

brd->printed[wrd >> 5] &= ~(1 << (wrd  & 0x1f));

if (dir==HORAL)
 i=-1;
 else
 j=-1;

for (;i+j<lgth;(dir==HORAL)?i++:j++)
  if (brd->raster[sx+i][sy+j] & LETTER)
    {
     brd->raster[sx+i][sy+j] &= ~dir;
     if ((brd->raster[sx+i][sy+j] & DIRS) == 0)
      brd->raster[sx+i][sy+j] = 0;
    }
    else
     brd->raster[sx+i][sy+j] -= INCTR;

}
    
wremove (sx, sy, dir, skip)
int sx;
int sy;
int dir;
int skip;
{
int i = 0;
int j = 0;
int wrd,lgth,k,l;

/* sx and sy always >=0 and <= V(H)MAX */
/* coordinates of STOP character */

if (trace > 3)
 {
 printf(" wremove : dir %d, skip %d, sx %d, sy %d\n", 
         dir, skip, sx, sy);
 }

wrd = (dir==HORAL)? board.hword[sx+1][sy]:board.vword[sx][sy+1];

if (wrd == skip)
 return 0;

board.printed[wrd >> 5] &= ~(1 << (wrd  & 0x1f));
board.raster[sx][sy] -= INCTR;

if (dir==HORAL) i=1; else j=1;
while (board.raster[sx+i][sy+j] & LETTER)
 {
     board.raster[sx+i][sy+j] &= ~dir;
     if ((board.raster[sx+i][sy+j] & DIRS) == 0)
      board.raster[sx+i][sy+j] = 0;
     if (dir==HORAL) i++; else j++;
 }

board.raster[sx+i][sy+j] -= INCTR;

lgth = i+j;

if (dir==HORAL) i=1; else j=1;
for (;i+j<lgth;(dir==HORAL)?i++:j++)
 if (board.raster[sx+i][sy+j])
  {
   k=l=0;
   while (board.raster[sx+i-k][sy+j-l] & LETTER)
    if (dir==HORAL) l++; else k++;

   wremove (sx+i-k,sy+j-l,dir ^ DIRS, skip);
  }
return 0;

}

prt_sol(brd)
t_state *brd;
{
int i,j;

if (trace)
printf(" solution : \n");

for (i=1;i<=VMAX;i++)
 {
 for (j=1;j<=HMAX;j++)
  if (brd->raster[j][i] & LETTER)
   printf("%c", (brd->raster[j][i] & LETTER) + 96);
   /* check print status */

  else
   printf("-");
 printf("\n");
 }

if (trace)
 printf(" print status : (%d) \n", ct_wrds(brd));

if (trace>2)
{
printf(" states : \n");
for (i=1;i<=VMAX;i++)
 {
 for (j=1;j<=HMAX;j++)
   printf("%2x ", brd->raster[j][i]);
 printf("\n");
 }
printf(" print status : (%d) \n", ct_wrds(brd));
}
}