```/*
* 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;	/* Defines the contents of all 25 squares
* and the individual distances from
* the final destinations.
*/
#ifdef KNOTS
char knotx;
char knoty;
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 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 = 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);
halfwidth = maxwidth/2;
doublewidth = maxwidth*2;
if (ac > 3) {
maxdepth = atoi(av);
}
}
/* 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, 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 = (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;
{
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;

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.X && j == p.Y) {
c = '+';
} else {
c = 'A' + 5*(int)p.pos[CPOS(i, j)].x + (int)p.pos[CPOS(i, j)].y;
}
printf("%c", c);
}
printf("\n");
}
*/
printf("trans= %d\n", (int)p.tturns);
#endif
/* Print out move sequence. */
printf("%s\n", p.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;
dst = dst = dst = dst = dst = dst = 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 += dst;
dst += dst;
for (i = 0; i < 8; i++) {
if (i < dst) {
dist += (12 - i);
} else if (i < dst) {
dist += (8 - i);
} else if (i < dst && 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;
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;
short n;
{
int i, j, k, ret, best;
short narr;

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
``` 