/*
 * This is scrambloyd, by Bill Tanenbaum.
 */

/*
 * This code is almost, but not quite identical with my entry.
 * It is even better.
 * It solves the third final square in 86 moves instead of 94.
 * On the other four final squares, it does the same as my entry.
 * This code was written before the finals.
 */
/*
 * NOTE: The conditionally compiled stuff inside #ifdef KNOTS or #ifdef FDIST
 * is needed only for very anomalous starting positions.  They are refinements
 * of the evaluation function in cases where it would otherwise be too low.
 * I have not commented any of this code.  On the five squares in the finals,
 * the program actually does better in total without this code.
 */

#include 
#include 

/* define some constants */

#define HASHBITS 12
#define HASH2 ((HASHBITS)+(HASHBITS))
#define HASH3 ((HASHBITS)+(HASH2))
#define HASHBINS (1 << HASHBITS)
#define HASHMASK ((HASHBINS) - 1)

/* Maximum number of turns to solve puzzle */
#define MMAX 150

/* Maximum allowed value of evaluation function */
#define DMAX 290

/* defines square in grid as function of row and column */
#define CPOS(a, b) ((5*(a))+(b))

#define DIST(a) ((a)->FDist)


/* Defines structure indicating the current contents of one grid square. */
typedef struct {
	char x; /* Destination row of letter. Range 0-4 */
	char y; /* Destination column of letter. Range 0-4 */
	char dist; /* Minimum possible no. of moves to reach destination,
		    * including possible transport move from center to
		    * destination, if that helps. Range 0-5.
		    * Zero means letter is at its destination.
		    */
} INFO;

/* Possible moves */
typedef enum {
	D,
	U,
	L,
	R,
	T,
	NMOVES,
} MOVES;

/* Inverses of the moves ( yes, I know T is not its own inverse) */
MOVES Inverse[NMOVES] = { U, D, R, L, T};

/* Structure defining a configuration (i.e. "position") for the entire grid,
 * plus the past move history.  For performance reasons, there is some
 * redundant information also stored.
 */
typedef struct {
	INFO pos[25];	/* Defines the contents of all 25 squares
			 * and the individual distances from
			 * the final destinations.
			 */
#ifdef KNOTS
	char knotx[5];
	char knoty[5];
	short Kdist;
#endif
	short Dist; /* Sum of distances from destination of all 24 letters */
	short FDist; /* Dist + 2 * Adist + Bdist (weighted distance) */
		     /* This is the return value of the evaluation
		      * function.  The weighting gives an incentive
		      * to complete the top and left letters first.  This
		      * gives better results than without.
		      */
	short Adist; /* Sum of distances from destination of letters
		      * destined for first row or column, (ABCDEFKPU)
		      * Get these letters in place early!
		      */
	short Bdist; /* Sum of distances from destination of letters
		      * destined for second row or column, (GHIJLQV)
		      * Get these letters in place after the ones
		      * in Adist!  (The letters MNORSTWX can wait.)
		      */
	short tturns; /* Total no. of transport moves so far. */
#ifdef FDIST
	short distmax;
#endif
#ifndef DUPS
	unsigned short hashval; /* Hash value of pos[25] array.
				 * Used for eliminating duplicate positions.
				 */
#endif
	char parity; /* 0 (1) = final pos can(not) be reached without t move */
	char prev;	/* Previous move. (enum) D, U, L, R, T */
	char X;		/* Row of empty square.  0-4 */
	char Y;		/* Column of empty square. 0-4 */
	char Moves[NMOVES]; /* entries for DULRT. 1 = possible next move,
			     * 0 = illegal move or reverses last move.
			     */
	char moves[MMAX]; /* character string - move history to reach pos. */
} POSIT;

/* GLOBAL VARIABLES BEGIN HERE */

POSIT *Pos;	/* Pointer to array of positions before current turn */ 
POSIT *Npos; 	/* Pointer to array of positions after current turn */

int Best; /* minimum value of eval. function for current positions. */
int Turns; /* Number of moves to get to each current position from init. pos. */
int Nn;	/* misc. counter for number of positions */
int maxdepth; /* give up if can't solve in this number of moves.
		* Defaults to 149 unless overridden from command line.
		*/
int maxwidth = 16000;	/* Maximum number of positions to keep at
			 * any given turn.  Running time is approx.
			 * linear in this number.  Reducing this number
			 * speeds things up, but may give less optimal
			 * solution.  The default of 16000 can be overridden
			 * from command line.  
			 */
int halfwidth; 	/* = maxwidth/2 */
int doublewidth; /* = maxwidth * 2 */

void read_grid();
void elimdups();
int moveit();
void dumpit();
void donext();
char getdist();
char gdist();

int  Dists[DMAX]; /* Array that gives the number of current positions that
	* have the subscript as the value of the evaluation function.
	* If Dists[67] = 25, then 25 current positions have an evaluation
	* function of 67.
	*/
#ifndef DUPS
unsigned short hash();

/* These arrays are used to eliminate duplicate positions. */
int  Counts[HASHBINS];
int  count[HASHBINS];
POSIT **Ptrs[HASHBINS];

#ifdef DEBUG
int dupselim;
#endif
#endif

/* FInally, the main program! */
main(ac, av)
int ac;
char *av[];
{
	maxdepth = MMAX - 1; /* default for maxdepth */
	/* possibly override defaults of maxdepth and maxwidth from cmd line */
	if (ac > 2) {
		maxwidth = atoi(av[2]);
		halfwidth = maxwidth/2;
		doublewidth = maxwidth*2;
		if (ac > 3) {
			maxdepth = atoi(av[3]);
		}
	}
	/* Allocate a position, and zero it out */
	Pos = (POSIT *)calloc(1, sizeof(POSIT));

	/* Read the input grid, filling in most of Pos. */
	read_grid(av[1], Pos);
	/* Fill in parity */
	Pos->parity = parity(Pos);
	/* Since there is only one initial position, don't
	 * bother with weighting.
	 */
	Pos->FDist = Pos->Dist;
#ifdef KNOTS
	Pos->FDist += Pos->Kdist; 
#endif
	Best = DIST(Pos); /* Evaluation function of initial position */
	Dists[Best] = 1;
	if (Best == 0) {
		/* Just in case initial position was final position! */
		printf("\n");
		exit(0);
	}
	Nn = 1; /* We have only one initial position. */

	/* Now loop over turns, one at a time. */
	for (Turns = 0; Turns <= maxdepth; Turns++) {
		/* From the current (old) positions (Pos), determine
		 * the (new) positions after one more turn (Npos).
		 * (If the final position is reached, donext()
		 * does not return).
		 */
		donext(Pos, &Npos);
		/* Discard old positions. */
		free(Pos);
		/* New positions are now old positions */
		Pos = Npos;
	}
	/* If we get here, we failed to find a solution */
	exit(1);
}

/* Get possible new positions from old positions */
void
donext(pi, pp)
POSIT *pi;	/* old positions */
POSIT **pp;	/* New positions */
{
	int i, k;
	int n = Nn; /* Save number of old positions */
	int best; 
	int leeway;
	int ttbest = Turns + 2;
	POSIT *pj;
	POSIT *ttj;

	Nn = 0;	/* Initialize counter of positions to keep. */
	/* Start at minimum evaluation function, and count
	 * old positions (which have already been evaluated)
	 * until either maxwidth positions are encountered,
	 * or we run out of positions.
	 */
	for (i = Best; i < DMAX; i++) {
		int d = Dists[i];
		if (d) { 
			int lee = i - Best;
			if ((Nn + d) > maxwidth) {
				/* 
				 * This value (i) for the evaluation
				 * function gives us too many (>maxwidth)
				 * positions.  Except for unusual
				 * cases, break out and stop at i-1.
				 */
				/* If we already have > maxwidth/2,
				 * break out if the evaluation function
				 * is more than 2 above its best value.
				 */
				if (Nn > halfwidth && lee > 2) break;

				/* Don't go over maxwidth * 2, except
				 * if there are no positions if we don't.
				 */
				if ((Nn + d) > doublewidth && Nn > 0) break;
			}
			Nn += d;
			leeway = lee;
		}
	}

	/* Set eval. function cutoff for keeping old positions. */
	best = Best + leeway;
#ifdef DEBUG
	printf("%d %d %d %d %d\n", Best, Best+Turns, n, Nn, leeway);
#endif
	/* Eliminate duplicate positions, and also positions above cutoff */
	/* The positions to be eliminated are tagged with FDist = -1 */
	/* Also, the possible Moves for each old position are filled in,
	 * eliminating the inverse of the previous move.
	 */
	elimdups(pi, n, Nn, best);

	/* Malloc enough space for new positions.
	 * Except for the very first move, there is a maximum of
	 * four (not five) possible moves.  After d, u, l, or r,
	 * we do not allow the inverse move.  Also, after t,
	 * another t is impossible because the center square is empty.
	 */
	Nn++;
	Nn *= 4; 
	pj = (POSIT *)malloc(Nn*sizeof(POSIT));
	if (pj == 0) {
		printf("malloc fails %d\n", Nn);
		exit(1);
	}
	*pp = pj;
	/* zero Dists array */
	memset((char *)Dists, 0, sizeof(Dists));

	/* Initialize Best to a large value */
	Best = MMAX;

	/* Now we loop over the old positions,
	 * determining the possible new positions after one more move.
	 */
	for (i = 0; i < n; pi++, i++) {
		/* Ignore old positions that were discarded,
		 * either as duplicates, or because there were
		 * too many positions.  All these have
		 * been tagged with FDist = -1.
		 */
		if (pi->FDist >= 0) {
			/* Loop over the five moves (D U L R T) */
			for (k = 0; k < 5; k++) {
				int dist;
				/* Skip move that reverses last one */
				if (!pi->Moves[k]) continue;

				/* moveit() attempts to make the move.
				 * If impossible, moveit() returns 0.
				 * Otherwise, pj points to the new position.
				 * Note that if the move was impossible,
				 * the pointer pj is not incremented.
				 */
				if (moveit(pi, pj, k)) {
					/* Move was made */
					/* Eval. function */
					dist = DIST(pj);
					/* Increment appropriate
					 * member of Dists array.
					 */
					if (dist < DMAX)
						Dists[dist]++;
					/* Is this the best, so far? */
					if (dist < Best) Best = dist;
					/* Have we reached perfection? */
					if (dist == 0) {
						/*
						 * Yes, but we may reach the
						 * same pos. by multiple
						 * paths. Pick the path
						 * with fewest t moves.
						 */
						if (pj->tturns < ttbest) {
							ttbest = pj->tturns;
							ttj = pj;
						}
					}
					pj++;
				}
			}
		}
	}
	Nn = pj - *pp; /* This is the number of new positions */
	if (Best <= 0) {
		/* If we reached the final position,
		 * print out the move sequence and exit.
		 */
		dumpit(ttj);
		exit(0);
	}
}

void
elimdups(pb, n, nn, best)
POSIT *pb;	/* positions */
int n;		/* Number of positions */
int nn;		/* Approx number of positions to keep */
int best;	/* Max value of eval. function of position to keep */
{
	int i, j, k;
	POSIT *p;
	POSIT *pe;

	if (n == 1) return;
	pe = pb + n;
#ifndef DUPS
	memset((char *)Counts, 0, sizeof(Counts));
#endif
	/* Loop over positions */
	for (p = pb; p < pe; p++) {
		/* If the eval. function is above cutoff, tag for elim. */
		if (DIST(p) > best) {
			p->FDist = -1;
		} else {
			/* Below cutoff.  Keep unless duplicate */
#ifndef DUPS
			/* Save hash value over position */
			p->hashval = hash(p->pos);
			Counts[p->hashval]++;
#endif
			/* Disallow move that is inverse of previous move. */
			p->Moves[D] = p->Moves[U] = p->Moves[L] = p->Moves[R] =
				p->Moves[T] = 1; 
			p->Moves[Inverse[p->prev]] = 0;

			/* If the position is symmetric around the
			 * main diagonal, we can disallow U and D moves
			 * as equivalent to L and R respectively.
			 */
			if (symmet(p->pos)) {
				p->Moves[U] = p->Moves[D] = 0;
				switch (p->prev) {
				case D:
					p->Moves[L] = 0;
					break;
				case U:
					p->Moves[R] = 0;
					break;
				}
			}
		}
	}

	/* The remaining code in this function tags duplicate
	 * positions for elimination.
	 */
#ifndef DUPS
	/* Malloc some space, and set up some counters and pointers. */
	Ptrs[0] = (POSIT **)malloc(nn*sizeof(POSIT *));
	for (i = 1; i < HASHBINS; i++) {
		Ptrs[i] = Ptrs[i-1] + Counts[i-1];
	}
	memset((char *)count, 0, sizeof(count));
	/* Loop over positions, skipping those already tagged for elim. */
	for (p = pb; p < pe; p++) {
		if (p->FDist < 0) continue;
		k = p->hashval;
		Ptrs[k][count[k]++] = p;
		if (count[k] > Counts[k]) {
			printf("WHOOPS\n");
			exit();
		}
	}
#ifdef DEBUG
	dupselim = 0;
#endif
	/* Loop over hashbins */
	for (k = 0; k < HASHBINS; k++) {
		POSIT **pp = Ptrs[k];

		/* Loop over positions in this hashbin */
		for (i = 0; i < count[k]; i++) {
			POSIT *pi = pp[i];

			/* skip position if tagged for elim. */
			if (pi->FDist < 0) continue;

			/* Second loop over positions in this hashbin */
			for (j = 0; j < i; j++) {
				POSIT *pj = pp[j];
				int l;

				/* skip position if tagged for elim. */
				if (pj->FDist < 0) continue;

				/* Check if positions are the same. */
				for (l = 0; l < 25; l++) {
					if (pi->pos[l].x != pj->pos[l].x) goto skip;
					if (pi->pos[l].y != pj->pos[l].y) goto skip;
				}
				{
					/* Both positions are the same.
					 * Tag the one with the most
					 * t moves in its history for
					 * elimination.
					 */
					POSIT *pd, *pk;
					if (pi->tturns < pj->tturns) {
						pd = pj;
						pk = pi;
					} else {
						pd = pi;
						pk = pj;
					}
					pd->FDist = -1;
					/* The moves that were disallowed for
					 * EITHER position can be disallowed.
					 */
					pk->Moves[D] = pj->Moves[D] && pi->Moves[D];
					pk->Moves[U] = pj->Moves[U] && pi->Moves[U];
					pk->Moves[L] = pj->Moves[L] && pi->Moves[L];
					pk->Moves[R] = pj->Moves[R] && pi->Moves[R];
					pk->Moves[T] = pj->Moves[T] && pi->Moves[T];
#ifdef DEBUG
					dupselim++;
#endif
				}
skip:				continue;
			}
		}
	}
#ifdef DEBUG
	printf("dups %d out of %d\n", dupselim, nn);
#endif
#endif
}

/* Determines if position has symmetry around the main diagonal. */
int symmet(pos)
INFO pos[25];
{
	int i, j;
	/* Don't have to check diagonal elements! */
	for (i = 0; i < 5; i++) {
		for (j = 0; j < i; j++) {
			INFO *p1 = &pos[CPOS(i, j)];
			INFO *p2 = &pos[CPOS(j, i)];
			if (p1->x != p2->y) return(0);
			if (p2->x != p1->y) return(0);
		}
	}
	return(1);
}

/* Reads initial grid and fills in most of the initial position. */
void
read_grid(filename, p)
char *filename;
POSIT *p;
{
	register int i, j, k;
	int fp;
	char buffer[29];

	fp = open(filename, O_RDONLY);
	(void)read(fp, buffer, 29);
	for (i = 0; i < 5; i++) {
		for (j = 0; j < 5; j++) {
			int x,y;
			INFO *ip = &p->pos[CPOS(i,j)];

			char c = buffer[6*i + j];
			if (c == '+') {
				p->X = i;
				p->Y = j;
			} else {
				k = c - 'A';
				x = k/5;
				y = k%5;
				ip->x = x;
				ip->y = y;
				ip->dist = getdist(i, j, x, y);
				p->Dist += ip->dist;
				if (x*y == 0) p->Adist += ip->dist;
				else if ((x-1)*(y-1) == 0) p->Bdist += ip->dist;
			}
		}
	}
#ifdef KNOTS
	for (i = 0; i < 5; i++) {
		p->knotx[i] = get_knots(p, i, 0);
		p->knoty[i] = get_knots(p, i, 1);
		p->Kdist += (p->knotx[i] + p->knoty[i]);
	}
#endif
#ifdef FDIST
	p->distmax = 55;
#endif
	for (i = 0; i < NMOVES; i++) {
		p->Moves[i] = 1;
	}
	if (symmet(p->pos)) {
		p->Moves[D] = p->Moves[U] = 0;
	}
}

void dumpit(p)
POSIT *p;
{
#ifdef DEBUG
/*
	register int i, j;
	printf("\n");
	for (i = 0; i < 5; i++) {
		for (j = 0; j < 5; j++) {
			int c;
			if (i == p[0].X && j == p[0].Y) {
				c = '+';
			} else {
			c = 'A' + 5*(int)p[0].pos[CPOS(i, j)].x + (int)p[0].pos[CPOS(i, j)].y;
			}
			printf("%c", c);
		}
		printf("\n");
	}
*/
	printf("trans= %d\n", (int)p[0].tturns);
#endif
	/* Print out move sequence. */
	printf("%s\n", p[0].moves);
}

/* gets the minimum number of times the letter must be moved. */
char getdist(i, j, x, y)
char i, j, x, y;
{
	/* i, j, is current position.  x, y is destination. */
	char d1, d2;

	/* Try it without 't' move */
	d1 = gdist(i, j, x, y);

	/* Try it with final 't' move from center */
	d2 = gdist(i, j, (char)2, (char)2) + 1;

	/* Pick the better of the two */
	if (d2 >= d1) return(d1);
	else return(d2);
}

/* gets the minimum number of times the letter must be moved
 with 't' moves disallowed */
char gdist(i, j, x, y)
char i, j, x, y;
{
	/* i, j, is current position.  x, y is destination. */
	char d1, d2;
	d1 = (i >= x ? i-x : x-i);
	d2 = (j >= y ? j-y : y-j);
	return(d1 + d2);
}

/* makes a move */
/* return 0 if move not made, 1 if made. */
int
moveit(p1, p2, m)
POSIT *p1; /* old position (input) */
POSIT *p2; /* new mosition (output) */
int m; 	   /* move D, U, L, R, or T */
{
	INFO *ip1;	/* ptr to pos[] of letter to be moved */
	INFO *ip2;	/* ptr to pos[] of (empty) square letter moved to */
	char c;
	int n;

#define SIZE (sizeof(POSIT) + Turns - MMAX)
	switch(m) {
	case R:
		/* Impossible if blank in column 0 */
		if (p1->Y == 0) goto bad;

		/* Pos[] of letter to be moved */
		ip1 = &p1->pos[CPOS(p1->X, p1->Y-1)];

		/* If letter to be moved R is in its final dest. square
		 * in the leftmost column, disallow the move.
		 * Also, if the letter to be moved R is in its final dest.
		 * square in the second column from the left, and
		 * the first row and column are completely done,
		 * disallow the move.
		 */
		if (ip1->dist == 0) {
			if (p1->Y == 1) goto bad;
			if (p1->Adist == 0 && p1->Y == 2) goto bad;
		}
		/* Copy position from old to new */
		memcpy(p2, p1, SIZE);

		/* Pos[] of letter that was moved */
		ip2 = &p2->pos[CPOS(p2->X, p2->Y)];

		/* Adjust position of blank */
		p2->Y--;
		c = 'r';
		break;
	case L:
		/* Impossible if blank in column 4 */
		if (p1->Y == 4) goto bad;

		/* Pos[] of letter to be moved */
		ip1 = &p1->pos[CPOS(p1->X, p1->Y+1)];

		/* Copy position from old to new */
		memcpy(p2, p1, SIZE);

		/* Pos[] of letter that was moved */
		ip2 = &p2->pos[CPOS(p2->X, p2->Y)];

		/* Adjust position of blank */
		p2->Y++;
		c = 'l';
		break;
	case U:
		/* Impossible if blank in row 4 */
		if (p1->X == 4) goto bad;

		/* Pos[] of letter to be moved */
		ip1 = &p1->pos[CPOS(p1->X+1, p1->Y)];

		/* Copy position from old to new */
		memcpy(p2, p1, SIZE);

		/* Pos[] of letter that was moved */
		ip2 = &p2->pos[CPOS(p2->X, p2->Y)];

		/* Adjust position of blank */
		p2->X++;
		c = 'u';
		break;
	case D:
		/* Impossible if blank in row 0 */
		if (p1->X == 0) goto bad;

		/* Pos[] of letter to be moved */
		ip1 = &p1->pos[CPOS(p1->X-1, p1->Y)];

		/* If letter to be moved D is in its final dest. square
		 * in the top row , disallow the move.
		 * Also, if the letter to be moved D is in its final dest.
		 * square in the second row from the top, and
		 * the first row and column are completely done,
		 * disallow the move.
		 */
		if (ip1->dist == 0) {
			if (p1->X == 1) goto bad;
			if (p1->Adist == 0 && p1->X == 2) goto bad;
		}
		/* Copy position from old to new */
		memcpy(p2, p1, SIZE);

		/* Pos[] of letter that was moved */
		ip2 = &p2->pos[CPOS(p2->X, p2->Y)];

		/* Adjust position of blank */
		p2->X--;
		c = 'd';
		break;
	case T:
		/* Impossible if blank in center square */
		/* Disallowed if blank is adjacent to center square
		 * (equivalent to D, U, L or R in that case)
		 */
		if (p1->X == 2 && p1->Y >= 1 && p1->Y <= 3) goto bad;
		if (p1->Y == 2 && p1->X >= 1 && p1->X <= 3) goto bad;

		/* Pos[] of letter to be moved */
		ip1 = &p1->pos[CPOS(2, 2)];

		/* Copy position from old to new */
		memcpy(p2, p1, SIZE);

		/* Pos[] of letter that was moved */
		ip2 = &p2->pos[CPOS(p2->X, p2->Y)];
		/* parity may change */
		if (!((p2->X + p2->Y) & 1)) p2->parity = 1 - p2->parity;

		/* Adjust position of blank (to center square) */
		p2->X = (char)2;
		p2->Y = (char)2;
		p2->tturns++; /* increment no. of 't' moves */
		c = 't';
		break;
	}
	/* Copy moved letter from old location to new location */
	*ip2 = *ip1;

	/* save last move */
	p2->prev = m;

	/* New distance of moved letter */
	ip2->dist = getdist(p1->X, p1->Y, ip2->x, ip2->y);

	/* Adjust total distances */
	p2->Dist += (ip2->dist - ip1->dist);
	if (ip1->x == 0 || ip1->y == 0) p2->Adist += (ip2->dist - ip1->dist);
	else if (ip1->x == 1 || ip1->y == 1) p2->Bdist += (ip2->dist - ip1->dist);
	{
		/* Distance of blank always set to zero */
		INFO *p = &p2->pos[CPOS(p2->X, p2->Y)];
		p->dist = 0;
		/* Destination of blank is lower right corner */
		p->x = p->y = 4;
	}
#ifdef KNOTS
	switch(m) {
	case R:
	case L:
		p2->knotx[p1->Y] = get_knots(p2, p1->Y, 0);
		p2->knotx[p2->Y] = get_knots(p2, p2->Y, 0);
		p2->Kdist += (p2->knotx[p1->Y] - p1->knotx[p1->Y]);
		p2->Kdist += (p2->knotx[p2->Y] - p1->knotx[p2->Y]);
		break;
	case U:
	case D:
		p2->knoty[p1->X] = get_knots(p2, p1->X, 1);
		p2->knoty[p2->X] = get_knots(p2, p2->X, 1);
		p2->Kdist += (p2->knoty[p1->X] - p1->knoty[p1->X]);
		p2->Kdist += (p2->knoty[p2->X] - p1->knoty[p2->X]);
		break;
	case T:
		p2->knoty[p1->X] = get_knots(p2, p1->X, 1);
		p2->knotx[p1->Y] = get_knots(p2, p1->Y, 0);
		p2->Kdist += (p2->knoty[p1->X] - p1->knoty[p1->X]);
		p2->Kdist += (p2->knotx[p1->Y] - p1->knotx[p1->Y]);
		break;
	}
#endif
	/* Set Evaluation function to total distance, for now */
	p2->FDist = p2->Dist;
#ifdef KNOTS
	p2->FDist += p2->Kdist;
#endif
	/* Positions with evaluation function less than 7 and the wrong
	 * parity must have their evaluation function raised.
	 */
	if (p2->parity && p2->FDist < 7) {
		if (p2->X == 2 && p2->Y == 2) p2->FDist = 7;
		if (p2->FDist < 6) {
			if ((p2->X + p2->Y) & 1) p2->FDist = 6;
		}
		if (p2->FDist < 5) p2->FDist = 5;
	}
#ifdef FDIST
	if (p2->FDist <= p2->distmax && p2->FDist > 1) {
		int i, j, d;
		int dist = 0;
		int dst[6];
		dst[0] = dst[1] = dst[2] = dst[3] = dst[4] = dst[5] = 0;
		for (i = 0; i < 5; i++) {
			for (j = 0; j < 5; j++) {
				d = p2->pos[CPOS(i, j)].dist;
				dst[d]++;
				if (d > 1) dist = 4;
			}
		}
		dst[4] += dst[5];
		dst[3] += dst[4];
		for (i = 0; i < 8; i++) {
			if (i < dst[5]) {
				dist += (12 - i);
			} else if (i < dst[4]) {
				dist += (8 - i);
			} else if (i < dst[3] && i < 4) {
				dist += (4 - i);
			} else {
				break;
			}
		}
		p2->distmax = dist;
		if (p2->FDist < dist) {
			p2->FDist = dist;
		}
	}
#endif
	/* Add weightings to eval. function. */
	p2->FDist += p2->Bdist;
	p2->FDist += 2 * p2->Adist;

	/* Add last move to move history */
	n = strlen(p1->moves);
	p2->moves[n] = c;
	p2->moves[n+1] = 0;

	return(1);
bad:
	/* impossible or disallowed move */
	return(0);
}

/*
 * Calculates parity of position.
 */
int
parity(p)
POSIT *p;
{
	int i, j;
	int parity = 0;
	INFO info;
	POSIT *pp;

	pp = (POSIT *)calloc(1, sizeof(POSIT));
	*pp = *p;
	pp->pos[CPOS(pp->X, pp->Y)].x = 4;
	pp->pos[CPOS(pp->X, pp->Y)].y = 4;
	for (i = 4; i >= 0; i--) {
		for (j = 4; j >= 0; j--) {
			INFO *ip;
			INFO *ip2;
again:
			ip = &pp->pos[CPOS(i, j)];
			ip2 = &pp->pos[CPOS(ip->x, ip->y)];
			if (ip2 == ip) {
				continue;
			}
			if (i == 4 && j == 4 && ip2->x == 4 && ip2->y == 4) {
				if (!((ip->x + ip->y) & 1)) parity = 1 - parity;
			} else {
				parity = 1 - parity;
			}
			info = *ip;
			*ip = *ip2;
			*ip2 = info;
			goto again;
		}
	}
	free(pp);
	return(parity);
}

#ifdef KNOTS
int get_knots(p, i, y)
POSIT *p;
int i;
int y;
{
	int j, k, n;
	INFO *ip;

	short arr[5];
	if (i == 2) return(0);
	if (y) {
		for (j = k = 0; j < 5; j++) {
			ip = &p->pos[CPOS(i, j)];
			if (ip->x == i) {
				if (i != 4 || ip->y != 4) arr[k++] = ip->y;
			}
		}
	} else {
		for (j = k = 0; j < 5; j++) {
			ip = &p->pos[CPOS(j, i)];
			if (ip->y == i) {
				if (i != 4 || ip->x != 4) arr[k++] = ip->x;
			}
		}
	}
	n = knots (arr, k);
	if (i == 0 || i == 4) n *= 2;
	return(n);
}

int
knots(arr, n)
short arr[5];
short n;
{
	int i, j, k, ret, best;
	short narr[5];

	if (n <= 1) return(0);
	best = 0;
	for (i = 0; i < n; i++) {
		int ai = arr[i];
		for (j = 0; j < i; j++) {
			if (ai < arr[j]) best++;
		}
	}
	if (best <= 1) return(best);
	for (i = 0; i < n; i++) {
		for (j = k = 0; j < n; j++) {
			if (j == i) continue;
			narr[k] = arr[j];
			k++;
		}
		ret = knots(narr, n - 1) + 1;
		if (ret < best) best = ret;
	}
	return(best);
}
#endif

#ifndef DUPS
unsigned
short
hash(pos)
INFO *pos;
{
	unsigned short c;
	INFO *ip;
	INFO *ppos = pos + 25;
	unsigned int h = 0;
	unsigned int hh;
	for (ip = pos; ip < ppos; ip++) {
		h += ip->x; 
		h += (ip->y << 3); 
		h *= 5381;
	}
	hh = (h) ^ (h >>HASHBITS) ^ (h >>(HASH2)) ^ (h >>HASH3);
	c = (hh & HASHMASK);
	return(c);
}
#endif DUPS