/*  POTM ENTRY:  PegTheSnail    			*/
/*  My Name:   Gerhard Lutz				*/
/*  My email:  glutz@hydra.informatik.uni-ulm.de	*/

/*  To: enter@potm.ffast.att.com
 */

/* Contest : First 1997 POTM
 * Problem : Pegged
 * Author: Gerhard Lutz
 * Date : Mar 31, 1997
 * Last renewal: check exactly sys+user time
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>   /* for check of time limit */

#define CHOP(s) if (*s) s[strlen(s)-1]=0
                         /* cut last character of string */
#define ABS(x) ((x)<0?(-(x)):(x))
#define DBG(x)           /* print debug messages with
                          * #define DBG(x) x */
#define DBG_MNR(x)       /* print move number */
#define DBG_RESULT(x)    /* print result */
#define oo 1000000000    /* infinity */

#define CLK_TCK 100      /* clock time of 100 Hz */

/* the next two values are needed for the valuation 
 * of the position
 */
#define ISOLATION_POINTS 100000
#define WALK_POINTS 200000

#define MAX_DEPTH 6      /* maximum depth for tree search */

#define WHITE 0          /* colors of nodes in */
#define GRAY 1           /* breadth first search */
#define BLACK 2

#define MAX_SECONDS 570  /* time limit */

int offset[8][2]=        /* four jump directios and */
{                        /* four walk directions */
{2,0},
{0,2},
{-2,0},
{0,-2},
{1,0},
{0,1},
{-1,0},
{0,-1}
};


long dist_val[1230];      /* values of a function for 0<=x<1230 */


FILE *input;              /* input file descriptor */
char org_board[100][100]; /* the original board is used */
                          /* several times */
char board[100][100];     /* board positions */
int isolated[100][100];   /* flag for each board position */
                          /* if there is an isolated peg */
int org_isolated[100][100]; /* the same for original board */
int rows,cols;            /* total rows and columns */
int centerrow,centercol;  /* center position in board */
int pegs,org_pegs;        /* actual and total number of pegs */

int dist[100][100];       /* distance of board position to 
			   * center board position, 
			   * calculated by breadth first search
			   */
int color[100][100];      /* the following variables are */
int iqueue[10000];        /* used for breadth first search */
int jqueue[10000];
int head, tail;

int m_dist[100][100];
int m_color[100][100];
int m_iqueue[10000];
int m_jqueue[10000];
int m_head, m_tail;

int maxdepth;             /* the maximum depth of tree */
                          /* search depends on last move */
int moves_to_check, best_mtoc;
                          /* number of moves to check is
			   * limited because of the local
			   * search for the best move
			   */
long actvalue, org_actvalue; /* value of the actual position */
long positions;           /* number of positions checked at
			   * last move
			   */
long move_time;           /* for calculation of maxdepth */

int move_count;           /* counts number of moves */

char solution[8000][8];   /* for saving all moves of the */
char best_solution[8000][8]; /* actual and best solution */
int highest_score;        /* number of moves of best solution */

int prev_si=0,prev_sj=0,prev_ei=0,prev_ej=0;
                          /* previous move is saved for not
			   * taking it back at the next move
			   */


void swap(int *a, int *b) {int tmp=*a;*a=*b;*b=tmp;}


int checktime()
/* This function is taken from one of the last e-mails
 * from the POTM-Master to check if the time limit 
 * is reached
 */
{
  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 ;  
  if (seconds >= MAX_SECONDS) return 0;
  
  return 1;
}


void print_solution()
/* If the time limit is reached the best solution
 * is printed
 */
{
  int i;
  for (i=0;i<highest_score;i++)
    printf("%s\n",best_solution[i]);
  DBG_RESULT(printf("Pegs: %d  Moves: %d  m_to_c: %d\n",
		 org_pegs,highest_score, best_mtoc));
  exit(0);
}


void print_board()
/* For printing the board after each move
 * (So it's easier to debug)
 */
{
  int i,j;

  printf("\n   123456789012345678901234567890\n");
  for (i=0;i<rows;i++)
    {
      printf("%c: ",i+'A');
      for (j=0;j<cols;j++)
	{
	  switch (board[i][j])
	    {
	    case '_': printf(" ");break;
	    case 'O': printf(".");break;
	    case 'X': printf("*");break;
	    }
	}
      printf("\n");
    }
  printf("\n");
  return;
}


int is_isolated(int i,int j)
/* Checks if the peg at position (i,j) is isolated;
 * it is isolated if it hasn't got adjacent pegs
 */
{
  if (board[i][j]!='X') return 0;
  if (i>0 && board[i-1][j]=='X') return 0;
  if (i<rows-1 && board[i+1][j]=='X') return 0;
  if (j>0 && board[i][j-1]=='X') return 0;
  if (j<cols-1 && board[i][j+1]=='X') return 0;
  
  return 1;
}


/* The next four procedures enqueue, dequeue, visit and
 * set_distance is a breadth first search to calculate
 * the distance of a position to the center all over the
 * board
 */
void enqueue (int i, int j)
{
  iqueue[tail] = i;
  jqueue[tail] = j;
  tail++;
}

void dequeue (int *i,int *j)
{
  *i = iqueue[head];
  *j = jqueue[head];
  head++;
}

void visit (int i, int j, int distance)
{
  if (i<0 || i>=rows || j<0 || j>=cols || 
      board[i][j]=='_' || color[i][j] != WHITE) return;
  color[i][j] = GRAY;
  dist[i][j] = distance;
  enqueue(i,j);
}


void set_distance()
{
  int i,j;

  DBG(printf("Set_distance\n"));

  for (i=0;i<rows;i++)
    for (j=0;j<cols;j++)
      {
	color[i][j] = WHITE;      
	dist[i][j] = oo;
      }
  head = tail = 0;
  visit(centerrow,centercol,1);
  while (head != tail)
    {
      dequeue(&i,&j);
      visit(i+1,j,dist[i][j]+1);
      visit(i-1,j,dist[i][j]+1);
      visit(i,j+1,dist[i][j]+1);
      visit(i,j-1,dist[i][j]+1);
      color[i][j] = BLACK;
    }
}


int test_distance()
/* Checks if the most centered board position with a peg
 * has got a distance value less than infinity
 */
{
  int d,l,side;
  int si,sj;
  
  DBG(printf("Test_distance\n"));

  /* Search the nearest peg to the center from the center
   * to the border, like a snail house
   * (that's not the reason why I named the program
   * PegTheSnail; it's because of my first tries which were
   * slow as a snail)
   */
  for (d=0;d<50;d++)
    for (l=-d;l<=d;l++)
      {
	if (l==d && d>0) break;
	for (side=0;side<=3;side++)
	  {
	    si=centerrow;sj=centercol;
	    switch (side)
	      {
	      case 0: si+=-d;sj+=l;  break;
	      case 1: si+=d ;sj+=-l; break;
	      case 2: si+=-l;sj+=-d; break;
	      case 3: si+=l ;sj+=d;  break;
	      }
	    
	    if (si>=0 && si<rows &&
		sj>=0 && sj<cols && board[si][sj]=='X')
	      {
		DBG(printf("Test_distance (%d,%d)=%d\n",
			   si,sj,dist[si][sj]));
		if (dist[si][sj]<oo)
		  {
		    /* Center is reachable */
		    return 0;
		  }
		else
		  {
		    /* Center is unreachable
		     * New center is the actual peg 
		     */
		    centerrow=si;
		    centercol=sj;
		    return 1;
		  }	
	      }
	  }
      }
  return 0;
}


void set_dist_val()
/* Calculates the values of a function for the field values;
 * The value of a field on the board is 
 *
 *   dist_val [ distance to the center ]
 */
{
  int i;

  dist_val[0]=1;
  for (i=1;i<1229;i++)
      dist_val[i]=dist_val[i-1]+i;
}


int read_case()
/* reads the input file
 */
{
  int i,j;

  DBG(printf("Read_case\n"));

  rows=0;
  while (1)
    {
      fscanf(input,"%s",board[rows++]);
      if (feof(input))
	{
	  rows--;
	  break;
	}
    }
  cols=strlen(board[0]);

  /* Center peg 
   */
  centerrow=rows/2;
  centercol=cols/2;

  /* initialise fied values and distance from the center peg
   */
  set_dist_val();
  set_distance();
  if (test_distance()) set_distance();

  /* Count pegs, find isolated pegs and calculate 
   * the starting board value
   */
  pegs=0;
  actvalue=0;
  for (i=0;i<rows;i++)
    for (j=0;j<cols;j++)
      {
	isolated[i][j]=0;

	if (board[i][j]=='X')
	  {
	    pegs++;
	    if (dist[i][j]==oo)
	      {
		printf("ERROR: Board is unsolvable\n");
		printf("ERROR: Look at position %c%d\n",
		       i+'A',j+1);
		return 0;
	      }
	    actvalue+=dist_val[dist[i][j]];
	    if (is_isolated(i,j))
	      {
		isolated[i][j]=1;
		actvalue+=ISOLATION_POINTS;
	      }
	}
      }

  DBG(
      printf("Pegs : %d\n",pegs);
      printf("Rows:%d Cols:%d\nCenter:%c%d Actvalue:%ld\n",
	      rows,cols,centerrow+'A',centercol+1,actvalue);
       );

  DBG(print_board());

  return 1;
}


/* The next four functions m_enqueue, m_dequeue, m_visit
 * and m_set_distance are to find the local environment of 
 * the farest peg with breadth first search;
 * These fields will be checked
 */
void m_enqueue (int i, int j)
{
  m_iqueue[m_tail] = i;
  m_jqueue[m_tail] = j;
  m_tail++;
}

void m_dequeue (int *i,int *j)
{
  *i = m_iqueue[m_head];
  *j = m_jqueue[m_head];
  m_head++;
}

void m_visit (int i, int j, int distance)
{
  if (distance>maxdepth+1 || i<0 || i>=rows || j<0 || j>=cols
      || m_color[i][j] != WHITE || board[i][j]=='_') return;
  m_color[i][j] = GRAY;
  m_dist[i][j] = distance;
  m_enqueue(i,j);
}


void m_set_distance(int farest_i, int farest_j)
{
  int i,j;

  for (i=0;i<rows;i++)
    for (j=0;j<cols;j++)
      {
	m_color[i][j] = WHITE;      
	m_dist[i][j] = oo;
      }
  m_head = m_tail = 0;
  m_visit(farest_i,farest_j,0);
  while (m_head != m_tail)
    {
      m_dequeue(&i,&j);
      m_visit(i+1,j,m_dist[i][j]+1);
      m_visit(i-1,j,m_dist[i][j]+1);
      m_visit(i,j+1,m_dist[i][j]+1);
      m_visit(i,j-1,m_dist[i][j]+1);
      m_color[i][j] = BLACK;
    }
}


int valid(int si,int sj,int ei,int ej)
/* Checks if the move is a valid move
 */
{
  /* Are both positions on the board?
   */
  if (si<0 || ei<0 || sj<0 || ej<0 ||
      si>=rows || ei>=rows || sj>=cols || ej>=cols) return 0;

  if (board[si][sj]!='X') return 0;
  if (board[ei][ej]!='O') return 0;

  if (ABS(si-ei)+ABS(sj-ej)==2) 
    /* then it's a jump and the field in the middle must
     * be a peg
     */
    if (board[(si+ei)/2][(sj+ej)/2]!='X') return 0;

  return 1;
}


long set_move(int si,int sj,int ei,int ej,long val)
/* This function is doing the move and calculates the
 * new value of the position
 */
{
  int i,j;

  board[si][sj]='O';
  val -= dist_val[dist[si][sj]];

  board[ei][ej]='X';
  val += dist_val[dist[ei][ej]];

  if (ABS(si-ei)+ABS(sj-ej)==2) /* then it's a jump */
    {
      board[(si+ei)/2][(sj+ej)/2]='O';
      val -= dist_val[dist[(si+ei)/2][(sj+ej)/2]];
      pegs--;
    }
  else                          /* it's a walk */
    { 
      val += WALK_POINTS;
    }

  /* Now the new isolated pegs must be searched and
   * the new value of the position must be updated
   */
  if (si>ei) swap(&si,&ei);
  if (sj>ej) swap(&sj,&ej);
  
  for (i=si-1;i<=ei+1;i++)
    for (j=sj-1;j<=ej+1;j++)
      {
	if (i<0 || i>=rows || j<0 || j>= cols) continue; 
	if (is_isolated(i,j) && isolated[i][j]==0)
	  {
	    isolated[i][j]=1;
	    val+=ISOLATION_POINTS;
	    continue;
	  }
	if (is_isolated(i,j)==0 && isolated[i][j])
	  {
	    isolated[i][j]=0;
	    val-=ISOLATION_POINTS;
	  }
      }

  return val;
}


void unset_move(int si,int sj,int ei,int ej)
/* Takes the move back;
 * The old value needn't to be calculated because it
 * was saved
 */
{
  int i,j;

  board[si][sj]='X';
  board[ei][ej]='O';
  if (ABS(si-ei)+ABS(sj-ej)==2) 
    {
      board[(si+ei)/2][(sj+ej)/2]='X';
      pegs++;
    }

  if (si>ei) swap(&si,&ei);
  if (sj>ej) swap(&sj,&ej);
  
  /* But the isolated pegs must be found again
   */
  for (i=si-1;i<=ei+1;i++)
    for (j=sj-1;j<=ej+1;j++)
      {
	if (i<0 || i>=rows || j<0 || j>= cols) continue; 
	isolated[i][j]=is_isolated(i,j);
      }
}


long find_move(long value, int depth)
/* This recursive function checks all moves in a local
 * environment till the maximum depth is reached
 * and takes the best move
 */
{
  long best=oo;
  long val;
  int moves=0;
  int d,k,kk,kkk;
  int si_b,sj_b,ei_b,ej_b;
  int si,sj;
  int ju_wa;
  int count_pegs=0;

  if (depth==maxdepth || pegs==1) 
    /* breaking condition for the recursion:
     * maximum depth is reached or there is
     * only one peg left on the board;
     * The positions at the leefs of the tree are
     * counted
     */
    {
      positions++;
      return value;
    }

  best=oo;

  /* First check the jumps, then the walks
   */
  for (ju_wa=0;ju_wa<2;ju_wa++)
  /* ju_wa=0 => Jumps
   * ju_wa=1 => Moves
   */
    for (d=0;d<m_tail;d++)
      /* The nearest fields are saved in the queue of
       * the breadth first search
       */
      if (board[m_iqueue[d]][m_jqueue[d]]=='X')
	{
	  si=m_iqueue[d];
	  sj=m_jqueue[d];
	  count_pegs++;

	  if (ju_wa==0 && moves==0 && m_dist[si][sj]>3)
	    /* then a walk for that peg is necessary
	     */
	    {
	      d=m_tail;count_pegs=0;
	      break;
	    }
	  
	  /* check randomly the four directions
	   */
	  kkk=rand()%4;
	  
	  for (kk=kkk;kk<kkk+4;kk++)
	    {
	      k=ju_wa*4+kk%4;

	      /* if the move in this direction is valid
	       */
	      if (valid(si,sj,si+offset[k][0],
			sj+offset[k][1]))
		{
		  /* Take the move
		   */
		  val=set_move(si,sj,si+offset[k][0],
			       sj+offset[k][1],value);

		  /* If it's the backward move of the
		   * last one, it gets a bad value
		   */
		  if (depth==0 &&
		      prev_si==si+offset[k][0] &&
		      prev_sj==sj+offset[k][1] &&
		      prev_ei==si && prev_ej==sj)
		    val=oo-1;
		  else
		    /* Recursive function cal
		     */
		    val=find_move(val,depth+1);
		  
		  DBG(
		      if (depth==0)
		      printf("Testing move %c%d %c%d... Value %ld\n",
			     si+'A',sj+1,
			     si+offset[k][0]+'A',
			     sj+offset[k][1]+1,val);
		      );
		  
		  if (val<best)
		    /* new best move is found
		     */
		    {
		      si_b=si;  sj_b=sj;
		      ei_b=si+offset[k][0];
		      ej_b=sj+offset[k][1];
		      best=val;
		    }

		  /* take the move back and check the
		   * next one
		   */
		  unset_move(si,sj,si+offset[k][0],
			     sj+offset[k][1]);
		  moves++;
		  if (moves>=moves_to_check) goto all_moves;
		}
	    }

	  if (count_pegs>=pegs)
	    /* then all pegs on the board were checked
	     */
	    {
	      /* if a jump was found then I needn't search
	       * for walks
	       */
	      if (ju_wa==0 && moves>0) goto all_moves;

	      /* no jumps were found
	       */
	      d=m_tail;count_pegs=0;
	    }
	}
  
all_moves:
  
  if (depth==0)
    {
      /* Take the best move and save it as 'prev'
       */
      best=set_move(si_b,sj_b,ei_b,ej_b,value);
      prev_si=si_b;prev_sj=sj_b;
      prev_ei=ei_b;prev_ej=ej_b;
      DBG_MNR(printf("%c%d %c%d\n",
		 si_b+'A',sj_b+1,ei_b+'A',ej_b+1);
	  );

      /* Save this solution move
       */
      sprintf(solution[move_count++],"%c%d %c%d",
	     si_b+'A',sj_b+1,ei_b+'A',ej_b+1);
    }

  return best;
}


int solve_case()
{
  int farest;
  int farest_i, farest_j;
  int prev_farest[3]={0,0,0};  /* for saving the previous 
				* farest pegs because they
				* have to change
				*/
  int help_pegs;

  DBG(printf("Solve_case\n"));

  maxdepth=3;
  move_count=0;  /* Number of actual move */

  /* The farest fields on the board are the first fields
   * in the queue of breadth first search;
   * now find the farest peg
   */
  for (farest=tail-1;farest>=0;farest--)
    if (board[iqueue[farest]][jqueue[farest]]=='X' ) break;

  /* In this part I myself don't know anymore what I've
   * done; I think that there have been problems with
   * big boards with few pegs
   */
  help_pegs=2*pegs/3+(farest-pegs)/3;
  if (help_pegs!=0) 
    {
      move_time=18*10000/help_pegs;
      DBG(printf("Move_time %ld\n",move_time));
    }

  while (pegs!=1) 
    {
      if (move_count+pegs>highest_score || move_count>5000)
	/* better solution is impossible or this try
	 * won't find any solution
	 */
	return 0;

      if (!checktime()) /* Is time limit reached? */
	print_solution();

      positions=0;  /* Count number of checked positions
		     * to calculate next maxdepth
		     */

      /* find farest peg of the board that can make a move
       */
      for (farest=tail-1;farest>=0;farest--)
	{
	  if (board[iqueue[farest]][jqueue[farest]]!='X' ) 
	    continue;
	  if (pegs>2)
	    /* if the farest peg is too often at the same
	     * position then it must change
	     */
	    if (farest==prev_farest[rand()%3])
	      continue;
	  if (valid(iqueue[farest],jqueue[farest],
		    iqueue[farest]+2,jqueue[farest])) break;
	  if (valid(iqueue[farest],jqueue[farest],
		    iqueue[farest]-2,jqueue[farest])) break;
	  if (valid(iqueue[farest],jqueue[farest],
		    iqueue[farest],jqueue[farest]+2)) break;
	  if (valid(iqueue[farest],jqueue[farest],
		    iqueue[farest],jqueue[farest]-2)) break;
	  if (valid(iqueue[farest],jqueue[farest],
		    iqueue[farest]+1,jqueue[farest])) break;
	  if (valid(iqueue[farest],jqueue[farest],
		    iqueue[farest]-1,jqueue[farest])) break;
	  if (valid(iqueue[farest],jqueue[farest],
		    iqueue[farest],jqueue[farest]+1)) break;
	  if (valid(iqueue[farest],jqueue[farest],
		    iqueue[farest],jqueue[farest]-1)) break;
	}

      /* save this position with a random influence
       * if the farest peg is too often at the same position
       * then it must change
       */
      prev_farest[rand()%3]=farest;

      farest_i=iqueue[farest];
      farest_j=jqueue[farest];

      DBG(printf("*********** New move ***************\n"));
      DBG(printf("Farest position is peg %c%d value %d\n",
		 farest_i+'A',farest_j+1,dist[farest_i][farest_j]));

      /* save the fields in the environment of the 
       * farest peg
       */
      m_set_distance(farest_i, farest_j);

      /* calculate best move
       */
      actvalue=find_move(actvalue,0);

      /* set new maxdepth
       */
      if (positions<move_time/4) maxdepth++;
      if (positions>2*move_time && maxdepth>3) maxdepth--;
      if (maxdepth>MAX_DEPTH) maxdepth=MAX_DEPTH;

      DBG_MNR(
	  printf("===== This was move number %d\n",move_count);
	  );
      DBG(
	  print_board();
          printf("Value : %ld\n",actvalue);
	  printf("Pegs : %d\n",pegs)
	  );
      DBG(printf("Positions : %ld  Maxdepth : %d\n",
		 positions,maxdepth));
    }
  return 1;
}


int main(int argc,char *argv[2])
{
  int sk,i,j;

  input=fopen(argv[1],"r");
  if (input==NULL) 
    printf("Input file %s not found\n",argv[1]);

  highest_score=oo;

  if (! read_case()) 
    {
      printf("Error: Inputfile in wrong format\n");
      fclose(input);
      return 0;
    }
  fclose(input);

  /* save the original board
   */
  for (i=0;i<rows;i++)
    for (j=0;j<cols;j++)
      {
	org_board[i][j]=board[i][j];
	org_isolated[i][j]=isolated[i][j];
      }
  org_actvalue=actvalue;
  org_pegs=pegs;

  /* search the best solution for different starting values
   */
  for (sk=10;sk<1000;sk++)
    for (moves_to_check=7;moves_to_check<14;moves_to_check++)
      {
	/* Initialise random number generator
	 * with different values
	 */
	srand(sk);

	DBG_MNR(
	  printf("New test case with %d moves to check\n",
		 moves_to_check);
	  );

	if(solve_case())
	  {
	    DBG(printf("Found new solution with %d moves\n",
		       move_count));
	    for (i=0;i<move_count;i++)
	      strcpy(best_solution[i],solution[i]);
	    highest_score=move_count;
	    best_mtoc=moves_to_check;

	    if (highest_score<org_pegs)
	      /* then there is no better solution possible
	       */
	      print_solution();
	  }

	/* set back to original board
	 */
	for (i=0;i<rows;i++)
	  for (j=0;j<cols;j++)
	    {
	      board[i][j]=org_board[i][j];
	      isolated[i][j]=org_isolated[i][j];
	    }
	actvalue=org_actvalue;
	pegs=org_pegs;
      }

  return 0;
}