/*  POTM-MASTER ADDENDUM:  Giorgio kindly added some commenting
	to this version ... thus it is not the PRECISE version
	that participated in the contest, but he assures me
	that it is algorithmicly the same.	=Fred		     */

/*********************************************************************/
/*       POTM 1st quarter 1997: "PEGGED"                             */
/*                                                                   */
/*       Program name:  PickQuick                                    */
/*       Author      :  Giorgio Di Falco                             */
/*       Version     :  2.2                                          */
/*       E-mail      :  G.difalco@agora.stm.it                       */
/*********************************************************************/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/* Some define's for avoiding investigating on compiler's .h files */
#undef BOOL
#undef TRUE
#undef FALSE
#undef min
#undef max
#define BOOL  int
#define TRUE  1
#define FALSE 0
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)<(y)?(y):(x))
 
/*-------------------------------------------------------------------*/
/*       Common declarations                                         */
/*-------------------------------------------------------------------*/
#define WIDTH  51                       /* # matrix columns          */
#define HEIGHT 27                       /* # matrix rows             */
#define NO     '_'                      /* means position forbidden  */
#define HOLE   'O'
#define PEG    'X'                      /*                           */
#define MARK   'Z'                      /* a marked peg              */
#define MAXPATHS  15                    /* # sequences in array      */
#define MAXMOVES   9                    /* max length of a sequence  */
#define STARTSEQ   3                    /* initial sequence length   */
 
typedef struct {                        /* defines a move            */
short from;
short to;
} MOVE;
 
typedef struct {    /* this structure define a sequence and its */
short nMoves;       /* estimated value                          */
MOVE  m[MAXMOVES];
short nPegs;
short nMax;
char  maxDist;
long  gravity;
short valSqua;
} EVAL;
 
static char  W[HEIGHT*WIDTH+1];         /* working board             */
static char  Y[HEIGHT*WIDTH+1];         /* subset of the board       */
static char  dist[HEIGHT*WIDTH+1];      /* matrix of distances       */
static signed char from[HEIGHT*WIDTH+1];/* matrix of back pointers   */
static short row[HEIGHT*WIDTH+1];       /* row numbers               */
static short col[HEIGHT*WIDTH+1];       /* col numbers               */
static short iWidth, iW;                /* actual board width +2     */
static short iHeight, iH;               /* actual board height+2     */
static short nPegs;                     /* current number of pegs    */
 
static short top,bottom,left,right;     /* area bounds               */
static short center;                    /* center of the board       */
 
static short delta[4];    /* distance of nort/west/east/south cell   */
static short delta8[8];   /* distance of all 8 neighboroughs         */
static short nPaths[2] = {1,1};         /* # elements in paths[2][]  */
static EVAL  paths[2][MAXPATHS];        /* array of sequences        */
static short nWalks;                    /* current # walks allowed   */
static short nMarked;                   /* current # of marked pegs  */
 
short iLen;                             /* total board length        */
 
/*-------------------------------------------------------------------*/
/*       Function prototypes                                         */
/*-------------------------------------------------------------------*/
static char  computeDist(void);
static EVAL  *processZone(short);
static short markZone(short,short);
static short markPaths(short,short);
static void  eval(EVAL *,char);
static BOOL  nextPath(short, EVAL *);
static void  appendPath(short, EVAL *);
static MOVE  nextMove(MOVE *,MOVE *,BOOL);
static short numWalks(MOVE *,short);
static void  doMove(MOVE *);
static void  undoMove(MOVE *);
static BOOL  isBetter(EVAL *,EVAL *,BOOL);
static short square(short);
static short pathInArray(short, EVAL *,BOOL);
static void  findRectangle(void);
/*-------------------------------------------------------------------*/
/*       Macros                                                      */
/*-------------------------------------------------------------------*/
#define DISTANCE(x,y)  (abs(row[x]-row[y])+abs(col[x]-col[y]))
#define isWALK(x)      (abs(x.from-x.to)==1 ||  \
                        abs(x.from-x.to)==iWidth)
#define WRITEPOS(x)    row[x]+'A'-1,col[x]
/* the areNear macro return TRUE if the 1st move is connected
   to the previous move */
#define areNear(m,prev)             \
  ( (  m.from==prev->to               \
  || prev->from==m.to               \
  || m.to==(prev->from+prev->to)/2  \
  || DISTANCE(m.to,prev->to)==1     \
  || DISTANCE(prev->to,(m.from+m.to)/2)<2  ) \
  && (m.from!=prev->to || m.to!=prev->from))
 
/*********************************************************************
*    MAIN PROGRAM                                                   *
*********************************************************************/
main(int argc, char **argv)
{
/*-------------------------------------------------------------------*/
/*       Local declarations                                          */
/*-------------------------------------------------------------------*/
FILE  *f;
char  *p;
short  i,j,n,nApplied,
maxDist,
d,tobeDone;
EVAL   *v,path;
BOOL   good,nogood,some;
MOVE   m;
 
/*-------------------------------------------------------------------*/
/*       Inizialize the matrix                                       */
/*-------------------------------------------------------------------*/
memset(W,NO,WIDTH*HEIGHT);
 
/*-------------------------------------------------------------------*/
/*       Read file                                                   */
/*       The input is put into matrix M, with an additional          */
/*       1-byte wide frame made of '_'                               */
/*-------------------------------------------------------------------*/
f = fopen(argv[1],"r");                 /* open input file           */
fscanf(f,"%s",W);                       /* read first record         */
iWidth = strlen(W)+2;                   /* line length+frame         */
memmove(W+iWidth+1,W,iWidth-2);         /* leave one row ahead       */
memset (W,NO,iWidth+1);                 /* reinitialize row zero     */
 
iHeight=3;
for (p=W+iWidth*2+1;                    /* fill from 2nd row on      */
1==fscanf(f,"%s",p);
p+=iWidth, iHeight++)              /* read everything           */
p[iWidth-2] = NO;                     /* replace the terminator    */
 
fclose(f);                              /* close input file          */
iLen    = p-W+iWidth-1;                 /* total board length        */
W[iLen] = 0;                            /* final terminator          */
center  = iLen/2;
 
/* for better performance, build two matrices with the row and
   column numbers */
for (i=0;i<iLen;i++)
{
row[i] = (char)(i/iWidth);
col[i] = (char)(i%iWidth);
}
 
for (nPegs=0, p=W;
     0!=(p=strchr(p,PEG));
     p++,nPegs++);                      /* count number of pegs      */
/* some further initializations */
delta[0] = -iWidth;
delta[1] =  iWidth;
delta[2] = -1;
delta[3] =  1;
delta8[0] = -iWidth-1;
delta8[1] = -iWidth;
delta8[2] = -iWidth+1;
delta8[3] = -1;
delta8[4] = 1;
delta8[5] =  iWidth-1;
delta8[6] =  iWidth;
delta8[7] =  iWidth+1;
 
/*-------------------------------------------------------------------*/
/*       Main loop                                                   */
/*       Progressively reduce the maximum distance from the          */
/*       center by processing the farthest areas first.              */
/*-------------------------------------------------------------------*/
maxDist = computeDist();                /* build the distance matrix */
tobeDone = 0;                           /* remember failure distance */
n = 0;                                  /* number of moves (4 debug) */
/*-----------------------------------------------------------------*/
/*    1st level loop: process decreasing distances                 */
/*-----------------------------------------------------------------*/
for (d=maxDist; d && nPegs>1; d--)      /* getting closer            */
{
  some = FALSE;                         /* no move done yet          */
  /*-----------------------------------------------------------------*/
  /*    2nd level loops: process all pegs at distance d              */
  /*-----------------------------------------------------------------*/
  do                                    /* do all d-far pegs         */
  {
    for (good=nogood=i=0, p=dist; 0!=(p=memchr(p,d,iLen-i)); p++,i++)
    {                                   /* search for all d-far pegs */
      i = p-dist;                       /* position in the board     */
      if (W[i]==PEG)                    /* a peg is there?           */
      {
        v = processZone(i);             /* mark zone and process it  */
        if (v)                          /* good sequence found       */
        {
          path = *v;                    /* move sequence to work fld */
          some = good = TRUE;           /* one is found              */
          /* do apply only a subset of the sequence, if not short    */
          /* (because it is better to reexamine the situation then)  */
          if (nMarked==nPegs && path.nPegs<2)
            nApplied = path.nMoves;
          else
            nApplied = max(1,path.nMoves-2);
 
          for (j=0; j<nApplied; j++)    /* apply the moves found     */
          {
            m = path.m[j];
            printf("%c%d %c%d\n",WRITEPOS(m.from),WRITEPOS(m.to));
            doMove(path.m+j);
            n++;
          }
          if (nPegs<2) break;           /* ok done                   */
        }
        else
          nogood = TRUE;                /* no sequence found         */
      }
    }                                   /* end for d-distance pegs   */
    if (nPegs<2) break;
  } while(good);  /* if something done, try again with the same dist.*/
  if (nPegs<2) break;
  if (nogood)                           /* distance not exhausted    */
  {
    if (!tobeDone) tobeDone = d;        /* remember to try later     */
    if (!some)     d-=3;                /* failed: try much nearer   */
  }
  else if (d==tobeDone)                 /* all ok                    */
  tobeDone = 0;                         /* this is done, proceed     */
  if (tobeDone>d && some)               /* may retry back level      */
    d = tobeDone+1;
}
return 0;                               /* end of program            */
}
/*-------------------------------------------------------------------*/
/*  Prepare the distance matrix                                      */
/*  (distance is measured in actual walks from the center; the       */
/*   format chosen works with distances up to 254 walks)             */
/*-------------------------------------------------------------------*/
static char computeDist(void)
{
  BOOL  bAny;
  short i,j,k;
  unsigned char  *p;
 
  memset(dist,255,iLen);                /* initialize                */
  memset(from,0,iLen);
  dist[center] = 0;                     /* center has distance=0     */
  for (i=0, bAny=TRUE; bAny; i++)       /* loop until some cell left */
  {                               /* reapeat for increasing distance */
    bAny=FALSE;
    for (j=0, p=dist; 0!=(p=memchr(p,i,(size_t)(iLen-j))); p++,j++)
    {                              /* search 4 cell with distance=i  */
     j = p-dist;                        /* position in board         */
     for (k=0; k<4; k++)                /* process neighboroughs     */
       if (W[j+delta[k]]!=NO && p[delta[k]]==255)
       {
         bAny=TRUE;
         p[delta[k]]=(char)(i+1);       /* set distance              */
         from[j+delta[k]]=(signed char)-delta[k]; /* set pointer back*/
       }
    }
  }
  return (char)(i-1);
}
 
/*-------------------------------------------------------------------*/
/*  Process the zone around a given peg                              */
/*-------------------------------------------------------------------*/
static EVAL *processZone(short pos)
{
short  range, i, j, k,nMoves, flip, maxWalks=2;
char   *p;
EVAL   val,startVal;
static EVAL bestVal;
BOOL   bSome, bGood, bWalk;
MOVE   m;
 
/*-------------------------------------------------------------------*/
/*     Mark pegs to be processed                                     */
/*-------------------------------------------------------------------*/
nMarked=0;
if (nPegs<8)        /* a few are left */
{
  for (p=W; 0!=(p=strchr(p,PEG)); p++,nMarked++) *p=MARK;
  findRectangle();
}
else                /* some morepegs left */
{
  for (range=min(4,dist[pos]); nMarked<8 && range<=dist[pos];
       range++)     /* increase radius until sufficient */
  {
    nMarked += markZone(pos,range);     /* do the actual marking       */
    findRectangle();                    /* delimite a rectangular zone */
    if (nMarked==nPegs ||               /* sufficient                  */
       (bottom-top-1)*(right-left-1) < 3*nMarked) break;
  }
}
 
/*-------------------------------------------------------------------*/
/*     Main evaluation process over the marke zone                   */
/*-------------------------------------------------------------------*/
eval(&startVal,dist[pos]);              /* evaluate current status   */
bGood  = 0;                             /* some initialization       */
nPaths[0]  = 0;
for (nWalks=0; nWalks<=maxWalks; nWalks++)
{              /* loop allowing an increasing number of walks        */
  nPaths[1] = 0;
  val.nMoves = 0;
  nMoves = STARTSEQ;    /* process all STARTSEQ-long sequences       */
  while (nextPath(nMoves,&val))         /* generate the next sequence*/
  {
    eval(&val,dist[pos]);               /* evaluate arrival status   */
                                        /* insert in best-seq array  */
    pathInArray(1,&val,(nMoves<min(MAXMOVES,nMarked-1)));
  }
  if (nPaths[1]==0)                     /* no sequence found at all  */
  {
    if (nWalks>0)                       /* walks already attempted   */
    {
      for (p=W; 0!=(p=strchr(p,MARK)); p++)
        *p = PEG;                       /* reset all marks           */
      return 0;                         /* signal failure            */
    }
    else continue;                      /* try with walks            */
  }
  /*-----------------------------------------------------------------*/
  /*   Starting with the best MAXPATHS sequences, continue moving    */
  /*   to improve evaluation                                         */
  /*-----------------------------------------------------------------*/
  for (nMoves++,j=0; nMoves<=min(MAXMOVES,nMarked-1); nMoves++,j++)
  {
    flip = j%2;             /* index in the flip-flop sequence array */
    nPaths[flip] = 0;
    bSome = FALSE;
    /*---------------------------------------------------------------*/
    /*    Analyze continuations of each best sequences               */
    /*---------------------------------------------------------------*/
    for (k=0; k<nPaths[!flip]; k++)     /* loop on best paths        */
    {
      val = paths[!flip][k];            /* initialize for nextPath   */
      if (val.nMoves<nMoves-1 && j)     /* blocked (uncontinuable)   */
      {
        pathInArray(flip,&val,FALSE);   /* insert in current array   */
        continue;
      }
      for (i=0; i<val.nMoves; i++)      /* apply moves to board      */
        doMove(val.m+i);
      bWalk = nWalks>numWalks(val.m,val.nMoves);  /* walk allowed?   */
      m = nextMove(0,val.m+val.nMoves-1,bWalk);   /* generate move   */
 
      if (m.from==0)                    /* no addition possible      */
        pathInArray(flip,&val,FALSE);   /* put sequence in array asis*/
      else                              /* ok move found             */
      {
        val.nMoves++;
        do                              /* evaluate and iterate      */
        {
          doMove(&m);                   /* apply move to board       */
          val.m[i] = m;                 /* append to sequence        */
          eval(&val,dist[pos]);         /* evaluate situtation       */
          if (pathInArray(flip,&val,FALSE)<MAXPATHS)
            bSome = TRUE;               /* insert in best-seq array  */
          undoMove(&m);                 /* unapply move, try next    */
          bWalk = nWalks>numWalks(val.m,val.nMoves-1);
          m = nextMove(&m,0,bWalk);
        } while (m.from);               /* try all continuations     */
      }
      while(--i>=0) undoMove(val.m+i);  /* reset board               */
    }                                   /* iterate on next sequence  */
    if (!bSome) break;                  /* no additional moves found */
  }                                     /* iterate: more moves       */
  if (j==0) flip=1;                    /* no additional moves at all */
  bestVal = paths[flip][0];             /* this is the best sequence */
  if (nPaths[flip] && bestVal.nMoves)   /* some sequence really found*/
  {
    if (startVal.maxDist>bestVal.maxDist /* was it a distance gain?  */
    ||  startVal.maxDist==bestVal.maxDist
    &&  startVal.nMax>bestVal.nMax
    ||  bestVal.nPegs<2)                /* or the game is over?      */
    {
      bGood = TRUE;
      break;                            /* ok take it                */
    }
  }                                     /* otherwise, try more walks
}                                                                    */
for (p=W; 0!=(p=strchr(p,MARK)); p++)
  *p = PEG;                             /* reset marks */
 
if (bGood || nMarked==nPegs)
  return &bestVal;                      /* worthwile */
else
  return 0;                             /* failure                   */
}
 
/**********************************************************************/
/*  Evaluate the position of currently marked pegs                    */
/**********************************************************************/
static void eval(EVAL *v,char currDist)
{
register    i,j;
char        *p;
 
v->nPegs = v->nMax = v->maxDist = 0;
v->gravity = 0;
 
for (i=top,j=0; i<=bottom; i++, j+=iW)  /* duplicate to a smaller    */
  memcpy(Y+j,W+i*iWidth+left,iW);       /* work area                 */
 
v->valSqua = 0;
for (p=Y; 0!=(p=strchr(p,MARK)); p++)   /* analyze the marked pegs   */
{
  i = p-Y;
  i = (i/iW+top)*iWidth+(i%iW+left);    /* position on actual board */
  if (dist[i]>v->maxDist) v->maxDist=dist[i]; /* max distance in set */
  v->nPegs++;                           /* number pegs in set        */
  v->gravity += dist[i]*dist[i];        /* gravity                   */
  v->valSqua += square(i);              /* evaluation of 3by3 squares*/
}
 
for (p=Y; 0!=(p=strchr(p,MARK)); p++)   /* again, for some computation*/
{
  i = p-Y;
  i = (i/iW+top)*iWidth+(i%iW+left);
  if (dist[i]>=currDist
  ||  dist[i]==v->maxDist)  v->nMax++;   /* num pegs at max distance  */
}
}
 
/*********************************************************************/
/*  Build a sequence of 'nMoves' moves                               */
/*********************************************************************/
static BOOL nextPath(short nMoves, EVAL *v)
{
MOVE m, *prev, *last;
BOOL bWalk;                             /* true if a walk is allowed */
 
do
{
  if (v->nMoves)                        /* move to be replaced       */
  {
    last = v->m+v->nMoves-1;            /* last move in the curr.path*/
    undoMove(last);                     /* move back                 */
    bWalk = nWalks>numWalks(v->m,v->nMoves-1);
  }
  else                                  /* no replacement: 1st move  */
  {
    bWalk = nWalks>0;
    last = 0;
    v->nMoves=1;
  }
  prev = v->nMoves>1 ? v->m+v->nMoves-2:0; /* preceding move         */
  m = nextMove(last,prev,bWalk);        /* get next move             */
  if (m.from) break;
} while (--v->nMoves);
if (m.from)                             /* a move found              */
{
  v->m[v->nMoves-1] = m;                /* put in array              */
  doMove(&m);                           /* apply to board            */
  if (v->nMoves<nMoves)                 /* request not completed     */
    appendPath(nMoves,v);               /* compose subsequence       */
}
return (v->nMoves>0);
}
 
/*-------------------------------------------------------------------*/
/*  Append a subsequence to the given sequence                       */
/*-------------------------------------------------------------------*/
static void appendPath(short nMoves, EVAL *v)
{
MOVE m;
BOOL bWalk;
 
bWalk = numWalks(v->m,v->nMoves);
for (;v->nMoves<nMoves; v->nMoves++)
{
  bWalk = nWalks>numWalks(v->m,v->nMoves);
  m = nextMove(0,v->m+v->nMoves-1,bWalk);
  if (m.from)                         /* a move found            */
  {
    v->m[v->nMoves] = m;              /* put in array            */
    doMove(&m);                       /* actually move           */
  }
  else break;                         /* no further move found   */
}
}
/*   ----------------------------------------------------------------
*   Next move: 1st parm is the preceding attempted move
*              2nd parm is the preceding move from where vicinity
*                       must be considered
*   ---------------------------------------------------------------- */
static MOVE nextMove(MOVE *last,MOVE *prev, BOOL bWalk)
{
static MOVE m;
register k;
char     *p;
BOOL     bWalked;
 
/* search position of last attempt in the 4 directions */
if (last) {
  p = W+last->from;
  if (isWALK(last[0]))
  {
    bWalked = TRUE;
    for (k=0; k<4 && (last->to-last->from!=delta[k]); k++);
  }
  else
  {
    bWalked = FALSE;
    for (k=0; k<4 && (last->to-last->from!=delta[k]*2); k++);
  }
}
else
{
  k = -1, p=W+iWidth+1;
  bWalked = FALSE;
}
 
/* generate a jump */
if (!bWalked)                           /* not trying walks          */
{
  for (; 0!=(p=strchr(p,MARK)); p++)    /* search for next peg       */
  {
    for (k++; k<4; k++)                 /* try next direction        */
    {
      if (p[delta[k]]==MARK && p[delta[k]*2]==HOLE)
      {                                 /* jump is legal             */
        m.from = p-W;                   /* start position            */
        m.to   = m.from+2*delta[k];     /* end position              */
        if (row[m.to]>=top && row[m.to]<=bottom
        &&  col[m.to]>=left && col[m.to]<=right
        && (!prev
        ||  areNear(m,prev)))           /* it is an interesting move?*/
          return m;                     /* return it                 */
      }
    }
    k = -1;                             /* start direction for next peg*/
  }
  p = W+iWidth+1;
}
 
if (bWalk)                              /* a walk is allowed         */
  for (; 0!=(p=strchr(p,MARK)); p++)    /* same process as above     */
  {
    for (k++; k<4; k++)
    {
      if (p[delta[k]]==HOLE)
      {
        m.from = p-W;
        m.to   = m.from+delta[k];
        if (row[m.to]>=top && row[m.to]<=bottom
        &&  col[m.to]>=left && col[m.to]<=right
        && (!prev
        ||  areNear(m,prev)))           /* it is an interesting move?*/
          return m;                     /* return it                 */
      }
    }
    k = -1;
  }
m.from = 0;
return m;
}
/*********************************************************************/
/*   Determine the best of two sequences                             */
/*********************************************************************/
static BOOL isBetter(EVAL *v1, EVAL *v2, BOOL bSpecial)
{
  /* 1st comparison: less distance wins */
  if (v1->maxDist < v2->maxDist)
    return TRUE;
  else if (v1->maxDist > v2->maxDist)
    return FALSE;
 
  /* 2nd and 3rd comparisons are made in a different order
     when evaluating the initial sequences and when evaluating
     the sequence continuations */
  if (!bSpecial)
  {
    /* less gravity wins */
    if (v1->gravity/v1->nPegs < v2->gravity/v2->nPegs)
      return TRUE;
    else if (v1->gravity/v1->nPegs > v2->gravity/v2->nPegs)
      return FALSE;
  }
 
  /* best 3by3 square evaluation wins */
  if ((v1->valSqua*5)/v1->nPegs > (v2->valSqua*5)/v2->nPegs)
    return TRUE;
  else if ((v1->valSqua*5)/v1->nPegs < (v2->valSqua*5)/v2->nPegs)
    return FALSE;
 
  if (bSpecial)
  {
    if (v1->gravity/v1->nPegs < v2->gravity/v2->nPegs)
      return TRUE;
    else if (v1->gravity/v1->nPegs > v2->gravity/v2->nPegs)
      return FALSE;
  }
 
  /* all comparison are even: the longest sequence wins */
  if (v1->nMoves>v2->nMoves) return TRUE;
  return FALSE;
}
 
/*********************************************************************
*    Apply a move to the board                                      *
*********************************************************************/
static void doMove(MOVE *m)
{
W[m->to]   = W[m->from];
W[m->from] = HOLE;
if (abs(dist[m->to]-dist[m->from])!=1)
{
  W[(m->from+m->to)/2] = HOLE;
  nPegs--;
}
}
 
/********************************************************************
*    Un-apply a move to the board                                   *
*********************************************************************/
static void undoMove(MOVE *m)
{
W[m->from] = W[m->to];
if (abs(dist[m->to]-dist[m->from])!=1)
{
  W[(m->from+m->to)/2] = W[m->to];
  nPegs++;
}
W[m->to]   = HOLE;
}
 
/********************************************************************
 *    Give a value to the marked zone, by evaluating                *
 *    each 3 by 3 square according to a predefined value table      *
 ********************************************************************/
static short square(short p)
{
static signed char points[] = {
-6,-2, 0,-2,-2,-2,-2,-3, 0,-2,  -2, 0, 0,-1,-2, 0, 0, 0,-2,-2,  /*  0*/
-2,-1, 0, 0,-3, 0,-3, 0, 0,-2,   0,-2,-2,-2, 0,-1,-2,-3,-2,-1,  /* 20*/
-2,-3,-2, 0,-2,-1,-3,-2, 0,-2,   0, 0,-2,-1,-2, 0, 0, 0,-2,-2,  /* 40*/
-1,-2, 0, 0, 0, 0,-3, 0, 0,-2,   0, 0,-2,-2,-3, 0, 0, 0,-2,-2,  /* 60*/
-2, 0,-4,-2,-2, 0, 0,-2,-4,-2,  -5,-3,-2,-4,-3, 0,-2,-1, 0,-2,  /* 80*/
-1,-3,-1,-3, 0, 0, 0,-2,-2, 0,   0, 0,-2, 0,-2,-3,-3,-2, 0,-2,  /*100*/
0,-2,-2, 0, 0,-2,-2, 0,-2,-2,   0,-2,-2,-3,-1,-1, 0,-2, 0,-2,  /*120*/
-2,-3, 0, 0,-2,-2,-2,-3,-3,-1,   0,-2, 0,-1,-2, 0, 0,-1,-2, 0,  /*140*/
-2,-3,-2,-3,-3,-2,-3,-3,-1,-1,   0, 0,-3,-3,-2,-2,-1,-3, 0,-2,  /*160*/
-1,-3, 0,-2,-2,-3,-4,-2,-3,-3,  -2, 0,-2,-2, 0,-1,-1,-3,-2,-3,  /*180*/
-2,-3,-2, 0, 0,-3,-4,-2, 0,-2,   0, 0, 0, 0,-2, 0, 0, 0,-2,-2,  /*200*/
-2,-2, 0, 0,-3,-1, 0,-3,-1,-3,  -3,-3, 0,-2,-2, 0, 0,-2,-2, 0,  /*220*/
0, 0,-2,-2,-2,-2, 0, 0,-2, 0,   0, 0, 0, 0, 0,-2               /*240*/
};
short i,t,x,j;
for (i=t=x=0; i<8;i++)
{
  j = p+delta8[i];
  t += t + (W[j]==PEG || W[j]==MARK);
  if (W[j]==NO) x--;
}
return (points[t]+x);
}
 
/********************************************************************
 *    Insert a sequence in the best-sequences array                 *
 ********************************************************************/
static short pathInArray(short flip,EVAL *val,BOOL bSpecial)
{
register i,j,k;
 
for (i=0; i<nPaths[flip]; i++)
{
  for (j=val->nMoves-1; j>=0; j--)
  {
    for (k=paths[flip][i].nMoves-1; k>=0; k--)
      if (!memcmp(val->m+j,paths[flip][i].m+k,sizeof(MOVE))) break;
    if (k<0) break;
  }
  if (j<0) /* all matched */
  return MAXPATHS;
}
 
for (i=0; i<nPaths[flip]; i++)   /* find position according to value */
  if (isBetter(val,paths[flip]+i,bSpecial)) break;
if (i<MAXPATHS-1)                /* a part to be shifted right     */
  memmove(paths[flip]+i+1,paths[flip]+i,
          sizeof(EVAL)*(MAXPATHS-i-1));
if (i<MAXPATHS)                       /* place found               */
{
  paths[flip][i] = *val;
  if (nPaths[flip]<MAXPATHS) nPaths[flip]++;
}
return i;
}
/********************************************************************
 *    Mark the pegs to be processed, by first marking a path        *
 *    (with a given length) towards the center, then marking        *
 *    all pegs in a given radius from the marked pegs.              *
 ********************************************************************/
static short markZone(short pos,short range)
{
register i,j;
short nMarks = 0;
 
for (i=0, j=pos; i<=min(range,dist[pos]); i++)
{                                     /*follow path towards center */
  nMarks += markPaths(j,4);             /* mark neighboroughs too  */
  j      += from[j];
}
return nMarks;
}
/********************************************************************
 *    Mark the pegs within a given disance from a given position    *
 ********************************************************************/
static short markPaths(short pos,short len)
{
short nMarks = 0;
register i;
 
if (W[pos]==PEG)
  W[pos]=MARK, nMarks++;
else if (W[pos]==NO)
  return 0;
if (len>1)
{
  for (i=0; i<4; i++)
    nMarks += markPaths(pos+delta[i],len-1);
}
return nMarks;
}
/********************************************************************
 *    Delimite the rectangular zone containing all marked pegs      *
 ********************************************************************/
static void findRectangle(void)
{
register i;
char    *p1,*p2,c;
 
top = (strchr(W,MARK)-W) / iWidth;     /* find first valid row      */
bottom = (strrchr(W,MARK)-W) / iWidth; /* find last valid row       */
left   = iWidth;                       /* initialize left margin    */
right  = 0;                            /* initialize right margin   */
for (i=top,p1=W+i*iWidth;
     i<=bottom; i++, p1+=iWidth)       /* analyze all rows   */
{
  p2 = memchr(p1,MARK,iWidth);
  if (p2 && p2-p1<left) left = p2-p1;  /* change left margin        */
  c = p1[iWidth];
  p1[iWidth]=0;                        /* temporary string delimiter*/
  p2 = strrchr(p1,MARK);
  if (p2 && p2-p1>right) right=p2-p1;  /* set right margin          */
  p1[iWidth]=c;                        /* restore string delimiter  */
}
top--;
bottom++;
right++;
left--;
iW = right-left+1;
iH = bottom-top+1;
Y[iW*iH]=0;
}
/*
*  Count walks in an array of moves
*/
static short numWalks(MOVE *m,short nM)
{
short n = 0;
 
while (nM--)
n += isWALK(m[nM]);
return n;
}