/*  POTM ENTRY:  PackMan                                          */
/*  Your Name:   Kevin Burfitt                                    */
/*  Your email:  kburfitt@au.infogrames.com                       */
/*  Compile instructions: None                                    */
/*  Version:     0.1.6                                            */
/*                                                                */
/*  Algorithm:   Combination of Brute-Force with some smarts      */
/*  that will prevent testing of redundant combinations or        */
/*  impossible moves. Finds some quick situations that have no    */
/*  solution, and will never try to move objects that are too big */
/*                                                                */
/*  Now has 'trivial' solution algorithm, for solving 'trivial'   */
/*  situations once it spots them                                 */

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>

#ifdef _MSC_VER
#include <conio.h>
#include <string.h>

#define DIAGNOSTICS
#define EXTRA_DIAGNOSTICS
const char *versionString="PackMan v0.1.6 - Kevin 'Zaph' Burfitt "
__DATE__;

// These things dont even exist in my entry, to keep the size down.
// Only used in my testing on the PC
void buildTestCase();
void writeCase(FILE *fp);
void dumpCase();
void dumpSolutionFile(int score);
char sourcename[256];

#define DEBUGBREAK _asm int 3
#else
#define DEBUGBREAK 0
#endif

typedef char suittype;
typedef struct {
	int width, height;
	int row,column;
	int area,numbers;
	unsigned int hmask;
	unsigned int wmask;
	bool nevermove;
} packObject;

typedef struct {
	int fromX,fromY;
	int toX,toY;
	int block;
} moveStruct;

suittype suitcase[15][30];
suittype sparecase[15][30];
short suitcaseNumbers[15*30];
short savedsuitcaseNumbers[15*30];
int suitcaseNumbersLen=15*30;
unsigned int impossible[15];
unsigned int savedimpossible[15];

bool theresATrivialSolution=true;
int trivialX=0;
int trivialY=0;
int trivialMoves=0;
int trivialType=0;
int trivialBigthing=0;
int trivialBigX=0;
int trivialBigY=0;

int triedAllBelow=0;
int currentSearchDepth=0;
int fastestSolution=0;
int hueristicfails=0;
bool randomTest=true;

unsigned int fasttest[15]; // Used for fast overlap testing
unsigned int savedfasttest[15]; // Used for fast overlap testing
unsigned int fastcopy[15];

const unsigned int flagbit[33]={
	0x00000000,
	0x80000000,	0x40000000,	0x20000000,	0x10000000,
	0x08000000,	0x04000000,	0x02000000,	0x01000000,
	0x00800000,	0x00400000,	0x00200000,	0x00100000,
	0x00080000,	0x00040000,	0x00020000,	0x00010000,
	0x00008000,	0x00004000,	0x00002000,	0x00001000,
	0x00000800,	0x00000400,	0x00000200,	0x00000100,
	0x00000080,	0x00000040,	0x00000020,	0x00000010,
	0x00000008,	0x00000004,	0x00000002,	0x00000001
};

const unsigned int initialbits[33]={
	0x00000000,
	0x80000000,	0xC0000000,	0xE0000000,	0xF0000000,
	0xF8000000,	0xFC000000,	0xFE000000,	0xFF000000,
	0xFF800000,	0xFFC00000,	0xFFE00000,	0xFFF00000,
	0xFFF80000,	0xFFFC0000,	0xFFFE0000,	0xFFFF0000,
	0xFFFF8000,	0xFFFFC000,	0xFFFFE000,	0xFFFFF000,
	0xFFFFF800,	0xFFFFFC00,	0xFFFFFE00,	0xFFFFFF00,
	0xFFFFFF80,	0xFFFFFFC0,	0xFFFFFFE0,	0xFFFFFFF0,
	0xFFFFFFF8,	0xFFFFFFFC,	0xFFFFFFFE,	0xFFFFFFFF
};


packObject things[20];
packObject savedthings[20];
packObject newThing;
//int thingOrder[20];
int numspaces = 0;
int suitcaseW,suitcaseH;
int numThings=0;
int totalmovestested=0;


int readEntryFile(char *fname);
int processSuitCase();
int canWeFinish();
int isThereASpace(const int w, const int h, int *x, int *y);
int isThereASpaceCopy(const int w, const int h, int *x, int *y);
void moveThing(const int i, const int x, const int y);
int theLoop();
void make_crc_table(void);
void checktime(void);
//  FAH REMOVED void startTime(void);
bool scanMoveList(const int currentDepth);
int perfectSolution(int *minBlocks, int currentDepth);
int quit(int score);
int findThing(char thing);
void getSuitcaseStats(int currentDepth);
void makeMeAnOrder(int *orderlist, int depth, moveStruct *bestmove);
#ifdef EXPERIMENTAL
int countOverlaps(int object, unsigned int hmask, unsigned int wmask,
				  int bailout);
int findLowOverlaps(int object, int nx, int ny);
#endif

int perfection=0;

unsigned long crcScore[1001];

moveStruct moves[1001];
moveStruct bestMoves[1001];

int bestSolution=999;
int truebestSolution=-1;
int totalmoves=0;

bool gotbest=false;

int finalX=0;
int finalY=0;

#define MAXCRCDEPTH 20
#define MAXCRCHIST  75
unsigned long last50crcs[MAXCRCDEPTH+1][MAXCRCHIST];


// Save the best move, in case we need an early exit!
void saveBest(int nummoves)
{
	if (gotbest && (nummoves > bestSolution))
	{
		printf("Oops, This isnt really the best! (%d v %d)\n",
			moves,
			bestSolution);
		DEBUGBREAK;
		return;
	}

	if (nummoves>0)
	{
		memcpy(bestMoves,moves,sizeof(moveStruct)*nummoves);
	}

	bestMoves[nummoves].toX = finalX;
	bestMoves[nummoves].toY = finalY;
	bestMoves[nummoves].block = 'X'-'A';

	bestSolution = nummoves;
	truebestSolution=nummoves;
	if (nummoves<currentSearchDepth)
		currentSearchDepth=nummoves;

#ifdef DIAGNOSTICS
	{
		printf("------------------------\n");
		for (int i=0; i<=bestSolution; i++)
		{
			printf("%c %d-%d\n",
				bestMoves[i].block+'A',
				bestMoves[i].toY+1,
				bestMoves[i].toX+1);
		}

		dumpCase();
		printf("------------------------\n");
	}
#endif

	gotbest=true;

	if (nummoves <= perfection)
	{
#ifdef DIAGNOSTICS
		printf("Emergency Out! - found the perfect solution!\n");
#endif
		quit(nummoves);
		return;
	}

	if (nummoves <= (triedAllBelow))
	{
#ifdef DIAGNOSTICS
		printf("Emergency Out! - we've done the shorter ones!\n");
#endif
		quit(nummoves);
		return;
	}

}

//-------------------------------------------------------------------------
int quit(int score)
{

	if (gotbest)
	{
		for (int i=0; i<=truebestSolution; i++)
		{
			printf("%c %d-%d\n",
				bestMoves[i].block+'A',
				bestMoves[i].toY+1,
				bestMoves[i].toX+1);
		}

	}
	else
		printf("NO SOLUTION\n");

#ifdef _MSC_VER
	dumpSolutionFile(score);
#endif

	if (!randomTest)
		exit(score);

	return score;
}

bool solutionPossible[15][30];
//-------------------------------------------------------------------------
bool checkForImpossible()
{
	int i;

	memset(solutionPossible,0,sizeof(bool)*15*30);

	if (newThing.area > numspaces)
	{
		// A quick game is a good game...
		return true;
	}

	int mw = suitcaseW - newThing.width;
	int mh = suitcaseH - newThing.height;

	// See if any individual piece is just too damn big!
	for (i=0; i<numThings; i++)
		if ((things[i].width > mw) && (things[i].height > mh))
		{

#ifdef DIAGNOSTICS
			printf("Cannot fit X and %c\n",i+'A');
#endif
			return true;
		}

	// Check to see if there are too many tall/long things... rare, but works
	int longrows=0;
	int freerows=0;
	int tallcols=0;
	int freecols=0;
	for (i=0; i<numThings; i++)
	{
		if (things[i].width > mw)
		{
			longrows+=things[i].height;
		}

		if (things[i].height > mh)
		{
			tallcols+=things[i].width;
		}
	}
	if (tallcols)
	{
		int maxcols = (suitcaseH/(mh+1))*mw;
		if (tallcols > maxcols)
		{
#ifdef DIAGNOSTICS
			printf("Not enough Columns\n");
#endif
			return true;
		}
	}

	if (longrows)
	{
		int maxrows = (suitcaseW/(mw+1))*mh;
		if (longrows > maxrows)
		{
#ifdef DIAGNOSTICS
			printf("Not enough Rows\n");
#endif
			return true;
		}
	}


	// Look for objects overlapping themselves and/or other
	// immovable objects (could be slow)
	// this doesnt actually do the final test for validity,
	// that is done by perfectSolution()
	unsigned int impossibleTest[15];

	memset(impossible,0xff,sizeof(unsigned int)*15);

	unsigned int clear=initialbits[suitcaseW];
	int x,y;

	for (y=0; y<suitcaseH; y++)
		impossible[y] = (impossible[y] & (~clear));

	unsigned int test;

	for (i=0; i<numThings; i++)
		if (things[i].nevermove)
		{
			test=initialbits[things[i].width];
			if (things[i].column)
				test = (test >> things[i].column);
			for (y=things[i].row; y<things[i].row+things[i].height; y++)
				impossible[y] |= test;
		}

	bool gotmore=true;
	while (gotmore)
	{
		gotmore=false;
		for (i=0; i<numThings; i++)
		{
			if (!things[i].nevermove)
			{
				test=initialbits[things[i].width];
				if (things[i].column)
					test = (test >> things[i].column);
				memcpy(impossibleTest,impossible, sizeof(unsigned int)*suitcaseH);
				for (y=things[i].row; y<things[i].row+things[i].height; y++)
				{
					impossibleTest[y] = (impossible[y]|test);
				}

				bool clear=false;
				for (x=0; x<suitcaseW-things[i].width+1; x++)
				{
					test=initialbits[things[i].width];
					if (x)
						test = (test >> x);

					for (y=0; y<suitcaseH-things[i].height+1; y++)
					{
						bool nope=false;
						for (int y2=y; y2<y+things[i].height; y2++)
						{
							if (impossibleTest[y2]&test)
								nope=true;
						}
						if (!nope)
							clear=true;
					}
				}

				if (!clear)
				{
					// Cannot move this piece!
					things[i].nevermove=true;
					gotmore=true;

					test=initialbits[things[i].width];
					if (things[i].column)
						test = (test >> things[i].column);
					for (y=things[i].row; y<things[i].row+things[i].height; y++)
						impossible[y] |= test;
				}
			}
		}
	}

	// Now work out which squares have a *possible* starting point
	// for the solution (speeds testing up, removes some false positives)

	memcpy(impossibleTest,impossible, sizeof(unsigned int)*suitcaseH);

	for (x=0; x<=suitcaseW-newThing.width; x++)
		for (y=0; y<=suitcaseH-newThing.height; y++)
		{
			test=initialbits[newThing.width];
			if (x)
				test = test>>x;

			bool nope=false;
			for (int y2=y; y2<y+newThing.height; y2++)
			{
				if (impossibleTest[y2]&test)
					nope=true;
			}
			if (!nope)
			{

				bool ok=true;
				for (int z=0; (z<numThings) && ok; z++)
				{
					// 4 tests, one for each corner
					if (!things[i].nevermove)
						if ((things[z].width > x)
							&& (x+things[z].width+newThing.width > suitcaseW))
							if ((things[z].height > y)
								&& (y+things[z].height+newThing.height > suitcaseH))
								ok=false;
				}
				if (ok)
					solutionPossible[y][x]=true;
			}
		}

	return false;
}

//-------------------------------------------------------------------------
void reset()
{
	memset(last50crcs,0,sizeof(unsigned long)*MAXCRCDEPTH*MAXCRCHIST);
}

void restoreAll()
{
	memcpy(suitcase,sparecase,sizeof(suittype)*30*15);
	memcpy(suitcaseNumbers,savedsuitcaseNumbers,sizeof(short)*30*15);
	memcpy(things,savedthings,sizeof(packObject)*20);
	memcpy(impossible,savedimpossible,sizeof(unsigned int)*15);
	memcpy(fasttest,savedfasttest,sizeof(unsigned int)*15);
}
void saveAll()
{
	memcpy(sparecase,suitcase,sizeof(suittype)*30*15);

	memcpy(savedsuitcaseNumbers,suitcaseNumbers,sizeof(short)*30*15);

	memcpy(savedthings,things,sizeof(packObject)*20);
	memcpy(savedimpossible,impossible,sizeof(unsigned int)*15);
	memcpy(savedfasttest,fasttest,sizeof(unsigned int)*15);
}

//-------------------------------------------------------------------------
int solvePuzzle(char *fname);

int randomseed=0;
int testMoves=4;
int main(int argc, char *argv[])
{
#ifdef DIAGNOSTICS
	printf("%s\n\n",versionString);
#endif

	if (argc <= 1)
	{
		printf("No Filename supplied\n");
		return 2;
	}

	if (sizeof(unsigned int) != 4)
	{
		printf("This program requires sizeof(unsigned int) to be 4\n");
		exit(-12345);
	}

	make_crc_table();

#ifdef _MSC_VER
	while (randomTest)
	{
		// FAH REMOVED startTime();
		solvePuzzle(argv[1]);

		printf("True Best Solution: %d, %d things\n",truebestSolution, numThings);
		if (randomTest &&
((truebestSolution>testMoves)||(truebestSolution>numThings)))
		{
			DEBUGBREAK;
			getch();
		}
	}
#else
	// FAH REMOVED startTime();
	solvePuzzle(argv[1]);
#endif
}

int solvePuzzle(char *fname)
{
	int ret;


	memset(suitcase,0,sizeof(suittype)*30*15);
	memset(things,0,sizeof(packObject)*20);
	memset(suitcaseNumbers,0xff,sizeof(short)*30*15);

	ret=readEntryFile(fname);

	randomTest = (ret!=0);

	theresATrivialSolution=true;
	triedAllBelow=0;
	currentSearchDepth=0;
	fastestSolution=0;
	hueristicfails=0;
	totalmovestested=0;
	bestSolution=999;
	truebestSolution=-1;
	gotbest=false;

#ifdef _MSC_VER
	if (randomTest)
		buildTestCase();
#endif
#ifdef DIAGNOSTICS
	strcpy(sourcename,fname);
#endif
	ret = processSuitCase();

	saveAll();
	//memcpy(sparecase,suitcase,sizeof(suittype)*30*15);
	//memcpy(savedthings,things,sizeof(packObject)*20);

	if (ret)
	{
		printf("Unable to decipher input file\n");
		quit(-ret);
		return -1;
	}

	if (checkForImpossible())
	{
		return -1;
	}
	//Is this the solution ?
	// A single move, trivial case ?
	if (ret=canWeFinish())
	{
		// At this point, the solution is at 0
		totalmoves=0;
		saveBest(0);

		return 0;
	}

//	int temp;
	//perfection = perfectSolution(&temp, 0);
	getSuitcaseStats(0);
	perfection=fastestSolution;

#ifdef _MSC_VER
	if (randomTest)
		if (perfection >testMoves)
			DEBUGBREAK;
#endif

#ifdef DIAGNOSTICS
	printf("A Perfect solution would take %d moves\n", perfection);
#endif

	if (perfection>=999)
	{
		return 999;
	}

	// A bizarre assertion by Zaph that most problems
	// can be solved in N/2 moves
	// Based on nothing other than gut-feeling!
	currentSearchDepth=numThings/2+1;

	if (currentSearchDepth < (perfection+1))
		currentSearchDepth = perfection+1;

	reset();
	ret=theLoop();

	if (!gotbest)
	{
#ifdef DIAGNOSTICS
		printf("No Gimme solution :(\n");
#endif
		triedAllBelow=currentSearchDepth;

		int last=currentSearchDepth;
		// Now I'm pretty certain that all puzzles have an N+1 solution...
		currentSearchDepth = numThings+1;
		if (currentSearchDepth<=last)
			currentSearchDepth=last+1;
		last=currentSearchDepth;

		reset();
		ret=theLoop();

		if (!gotbest)
		{
#ifdef DIAGNOSTICS
			printf("No n+1 solution :(\n");
#endif
			triedAllBelow=currentSearchDepth;

			currentSearchDepth = 2*numThings;
			if (currentSearchDepth<=last)
				currentSearchDepth=last+1;
			last=currentSearchDepth;

			reset();
			ret=theLoop();

			// actually, theres no chance this next loop will ever finish,
			// but I put it here for the test case that I havent seen yet :)
			if (!gotbest)
			{
#ifdef DIAGNOSTICS
				printf("Not even a medium sized solution :(\n");
#endif
				triedAllBelow=currentSearchDepth;
				currentSearchDepth = 998;
				reset();
				theLoop();
#ifdef DIAGNOSTICS
				if (gotbest)
					printf("Found an unusual one!\n");
#endif
			}
		}
	}

	if (gotbest)
	{
		quit(0);
		return 0;
	}
	else
	{
		quit(-666);
		return -666;
	}
}



/* Table of CRCs of all 8-bit messages. */
unsigned long crc_table[256];

/* Flag: has the table been computed? Initially false. */
int crc_table_computed = 0;

//-------------------------------------------------------------------------
/* Make the table for a fast CRC. */
void make_crc_table(void)
{
 unsigned long c;
 int n, k;

 for (n = 0; n < 256; n++) {
   c = (unsigned long) n;
   for (k = 0; k < 8; k++) {
     if (c & 1)
       c = 0xedb88320L ^ (c >> 1);
     else
       c = c >> 1;
   }
   crc_table[n] = c;
 }
 crc_table_computed = 1;
}

/* Update a running CRC with the bytes buf[0..len-1]--the CRC
  should be initialized to all 1's, and the transmitted value
  is the 1's complement of the final running CRC (see the
  crc() routine below)). */

//-------------------------------------------------------------------------
unsigned long update_crc(unsigned long crc, unsigned char *buf,
                        int len)
{
	unsigned long c = crc;
	int n;

#ifdef EXTRA_DIAGNOSTICS
	if (!crc_table_computed)
	{
		make_crc_table();
		printf("CRC table wasnt built!\n");
		exit(-1);
	}
#endif

	for (n = 0; n < len; n++) {
		c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
	}
	return c;
}

/* Return the CRC of the bytes buf[0..len-1]. */
//-------------------------------------------------------------------------
unsigned long calccrc(unsigned char *buf, int len)
{
	return update_crc(0xffffffffL, buf, len) ^ 0xffffffffL;
}

//-------------------------------------------------------------------------
unsigned long getCRC()
{
	unsigned long crc;
	crc=calccrc((unsigned char *)suitcaseNumbers,
		suitcaseNumbersLen);

	return crc;
}

unsigned long basecrcScore=0;

//-------------------------------------------------------------------------
bool checkCRC(int depth)
{
	bool repeated=false;

//	short spareNumbers[30*15];

	unsigned long crc = getCRC();
	crcScore[depth]=crc;

	if (crc == basecrcScore)
		repeated=true;
	else
	{
		for (int j=0; j<depth; j++)
			if (crc == crcScore[j])
			{
				repeated=true;
				return true;
			}

		if (!repeated)
		{
			int md = depth;
			if (md>MAXCRCDEPTH)
				md=MAXCRCDEPTH;
			for (int d=md; d>0; --d)
				for (int c=MAXCRCHIST-1; c>=0; --c)
					if (crc == last50crcs[d][c])
					{
						repeated=true;
						return true;
					}
		}
	}

	if (repeated)
		return true;

	return false;
}


int biggestW=0;
int biggestH=0;
int minimumBlocks=0;
int statsA[15][30];
int biggestA=0;


//-------------------------------------------------------------------------
void getSuitcaseStats(int currentDepth)
{
	int i,j;
	int w=0;
	int h=0;
	bool gotone=false;

	biggestW=0;
	biggestH=0;

	for (i=suitcaseW-1; i>=0; --i)
	{
		h=0;
		for (j=suitcaseH-1; j>=0; --j)
		{
			if (suitcase[j][i]=='_')
			{
				h++;
				if (h>biggestH)
					biggestH=h;
				else if (h+j < biggestH)
					break;
			}
			else
				h=0;
		}
	}


	// reverse order is critically important for this to work
	biggestA=0;
	for (j=suitcaseH-1; j>=0; --j)
	{
		w=0;
		for (i=suitcaseW-1; i>=0; --i)
		{
			if (suitcase[j][i]=='_')
			{
				w++;
				if (w>biggestW)
					biggestW=w;
				statsA[j][i]=w;
				if (j<(suitcaseH-1))
					statsA[j][i] += statsA[j+1][i];

				if (statsA[j][i] > biggestA)
					biggestA=statsA[j][i];
			}
			else
			{
				statsA[j][i]=0;
				w=0;
			}

		}
	}

	fastestSolution=perfectSolution(&minimumBlocks, currentDepth);

}


//-------------------------------------------------------------------------
bool scanMoveList(const int currentDepth)
{
	bool overlaps=false;
	bool repeatLetter=false;
	int i;
	int lookback=0;

	for (i=currentDepth-1; i>=0; i--)
	{
		// Have I already moved this letter ?
		if (moves[i].block == moves[currentDepth].block)
		{
			repeatLetter=true;
			lookback=i;
			break;
		}
	}

	if (repeatLetter)
	{
		int toX = moves[currentDepth].toX;
		int toY = moves[currentDepth].toY;
		int toXmax = toX+things[moves[currentDepth].block].width-1;
		int toYmax = toY+things[moves[currentDepth].block].height-1;
		// Lets see if this is an overlap free list!
		for (i=lookback; i<currentDepth; i++)
		{
			int mb = moves[i].block;

			int iLeft = moves[i].fromX;
			int iRight = iLeft + things[mb].width-1;
			// To
			if ((toX <= iRight) &&
				(toXmax >= iLeft))
			{
				int iTop = moves[i].fromY;
				int iBottom = iTop + things[mb].height-1;

				if ((toY <= iBottom) &&
					(toYmax >= iTop))
				{
					if (mb == moves[currentDepth].block)
					{
						if ((moves[i].fromX != toX)
							&& (moves[i].fromY != toY))
							return false;
					}
					else
						return false; // We have overlap
				}
			}
		}
		return true;
	}

	// Now look for repeated *shapes* instead of letters
	//(should be able to *just* do this test with the same result
	repeatLetter=false;
	for (i=currentDepth-1; i>=0; i--)
	{
		// Have I already moved this identical size ?
		if (things[moves[i].block].numbers ==
things[moves[currentDepth].block].numbers)
		{
			if ((moves[i].fromX == moves[currentDepth].toX)
				&& (moves[i].fromY == moves[currentDepth].toY))
			{
				// only accept EXACT overlaps of same-sized blocks
				repeatLetter=true;
				lookback=i;
				break;
			}
		}
	}

	if (repeatLetter)
	{
		int toX = moves[currentDepth].toX;
		int toY = moves[currentDepth].toY;
		int toXmax = toX+things[moves[currentDepth].block].width-1;
		int toYmax = toY+things[moves[currentDepth].block].height-1;
		// Lets see if this is an overlap free list!
		// This is checking for *any* block leaving an area overlapping
		// with the target area
		for (i=lookback+1; i<currentDepth; i++)
		{
			int mb = moves[i].block;
			int iLeft = moves[i].fromX;
			int iRight = iLeft + things[mb].width-1;
			// To
			if ((toX <= iRight) &&
				(toXmax >= iLeft))
			{
				int iTop = moves[i].fromY;
				int iBottom = iTop + things[mb].height-1;

				if ((toY <= iBottom) &&
					(toYmax >= iTop))
				{
					return false; // We have overlap
				}
			}
		}
		return true;
	}

	return false;
}

//-------------------------------------------------------------------------
void solveTrivial(int depth)
{
#ifdef DIAGNOSTICS
	printf("Solving trivial case\n");
	dumpCase();
#endif

	int startdepth=depth;

	if (trivialType==1)
	{
		// First move the 'big' item...
		moves[depth].fromX = things[trivialBigthing].column;
		moves[depth].fromY = things[trivialBigthing].row;
		moves[depth].toX=trivialBigX;
		moves[depth].toY=trivialBigY;
		moves[depth].block=trivialBigthing;

		moveThing(trivialBigthing,trivialBigX,trivialBigY);

		depth++;
	}

	for (int y=trivialY; y<trivialY+newThing.height; y++)
		for (int x=trivialX; x<trivialX+newThing.width; x++)
		{
			if (suitcase[y][x]!='_')
			{
				int l = suitcase[y][x]-'A';

				// Now find a place to store this one...
				int tx,ty;
				bool done=false;
				for (int yy=0; yy<suitcaseH; yy++)
					for (int xx=0; xx<suitcaseW; xx++)
					{
						if (!done && suitcase[yy][xx]=='_')
						{
							if ((xx >= trivialX)
								&& (xx < trivialX+newThing.width)
								&& (yy >= trivialY)
								&& (yy < trivialY+newThing.height))
							{
							}
							else
							{
								tx = xx;
								ty = yy;
								done=true;
								break;
							}
						}

					}

				int oldx=things[l].column;
				int oldy=things[l].row;

				moves[depth].fromX = oldx;
				moves[depth].fromY = oldy;
				moves[depth].toX=tx;
				moves[depth].toY=ty;
				moves[depth].block=l;

				moveThing(l,tx,ty);
				depth++;
			}
		}

	int ret=canWeFinish();
#ifdef DIAGNOSTICS
	if (!ret)
	{
		printf("Oh dear, fatal mistake!!\n");
		DEBUGBREAK;
	}

	dumpCase();
#endif

	saveBest(depth);

	// Now undo those moves!!
	for (int i=(depth-1); i>=startdepth; i--)
		moveThing(moves[i].block,moves[i].fromX,moves[i].fromY);

#ifdef DIAGNOSTICS
	dumpCase();
#endif
	depth=startdepth;
}

int lastFastest=9999;
//-------------------------------------------------------------------------
int theLoop()
{
	static int depth=-1;
	static int counter=0;
	static int deepest=0;

	int x,y;
	int ret;


	// depth will get 1 added to it for the next move,
	// then one more for the final move
	// So if we are currently at best-2 we will only get to 'best'
	// which we've already done, so why try again ?
	if (depth>=(currentSearchDepth-2))
	{
		return 0;
	}

	if (depth==-1)
	{
		// Someone has to remember the original one!
		unsigned long crc = getCRC();
		basecrcScore=crc;
		lastFastest=9999;
	}

	depth++;

#ifdef DIAGNOSTICS
	if (depth>deepest)
		deepest=depth;

	counter++;
	static int next=0;
	int now=clock();
	if (now>=next)
	{
		next+=5000;
		if (now==0)
			now=1;
		printf("In:%4dk %4.2f (%d) Mvs:%dk(%dkps) cur=%d/%d deep=%d-%d
bst=%d%c/%d ",
			counter/1000,
			(float)now/(float)counter,
			now,
			totalmovestested/1000,
			totalmovestested/now,
			depth,currentSearchDepth,
			deepest, triedAllBelow,
			bestSolution,
			(gotbest?'!':'.'),perfection);

		for (int i=0; i<depth; i++)
			printf("%c",moves[i].block+'A');
		printf("\n");
		dumpCase();
	}
#endif

	// Now would be a good time to reseed the tables...
	// Find the biggest free block, to help reduce choices
	// That kind of thing....


	getSuitcaseStats(depth);

	int myBiggestW = biggestW;
	int myBiggestH = biggestH;
	int myBiggestA = biggestA;
	int myFastestSolution=fastestSolution;
	int myMinimumBlocks=minimumBlocks;


	if (theresATrivialSolution)
	{
		if (!gotbest)
		{
			solveTrivial(depth);
			//depth--;
			//return 0;
		}
		else if (depth+trivialMoves < currentSearchDepth)
		{
			solveTrivial(depth);
			//depth--;
			//return 0;
		}
#ifdef DIAGNOSTICS
		else
			printf("Found trivial that was too long (%d vs
%d)\n",depth+trivialMoves,currentSearchDepth);
#endif
	}

	if (depth+myFastestSolution >= (currentSearchDepth))
	{
		depth--;
		return 0;
	}



	// Hueristics:
	if (myFastestSolution > lastFastest)
	{
		depth--;
		hueristicfails++;
		return 0;
	}

	checktime();

	int orderlist[20];
	moveStruct bestMove;
	makeMeAnOrder(orderlist,depth, &bestMove);

	if (bestMove.block < numThings)
	{
		int oldx=things[bestMove.block].column;
		int oldy=things[bestMove.block].row;

		moves[depth].fromX = oldx;
		moves[depth].fromY = oldy;
		moves[depth].toX=bestMove.toX;
		moves[depth].toY=bestMove.toY;
		moves[depth].block=bestMove.block;

		moveThing(bestMove.block, bestMove.toX, bestMove.toY);

		theLoop();

		moveThing(bestMove.block, oldx, oldy);

		if (depth>=(currentSearchDepth-1))
		{
			// Get out now, since all other solutions
			// in this loop will be the same number of moves
			depth--;
			return 1;
		}

	}

	// -------------- Loop ALOT!!
	for (int z=0; z<numThings; z++)
	{
		//int i=thingOrder[z]; // Sorted from biggest to smallest
		int i=orderlist[z];

		x=-1;
		y=-1;
		if ((!things[i].nevermove)
			&& (myBiggestW >= things[i].width)
			&& (myBiggestH >= things[i].height)
			&& (myBiggestA >= things[i].area))
		{

			bool skipthis=false;

			// Special case:  If we *must* find a single move solution
			// then we cant move things too tiny to free enough space!
			if (depth==currentSearchDepth-2)
			{
				if ((myFastestSolution==1)
					&& (myMinimumBlocks>things[i].area))
				{
					//dumpCase();
					skipthis=true;
				}
			}

			checktime();

			while (!skipthis
				&& isThereASpace(things[i].width, things[i].height, &x, &y))
			{
				//printf("I can move something! (%c)\n",i+'A');

				int oldx=things[i].column;
				int oldy=things[i].row;

				moves[depth].fromX = oldx;
				moves[depth].fromY = oldy;
				moves[depth].toX=x;
				moves[depth].toY=y;
				moves[depth].block=i;

				bool redundant=scanMoveList(depth);

				if (!redundant)
				{

					moveThing(i, x, y);
					totalmovestested++;

					if ((myFastestSolution==1) && (ret=canWeFinish()))
					{

						totalmoves = depth+1;
#ifdef DIAGNOSTICS
						printf("Found a solution that takes %d moves\n",
							totalmoves);
#endif
	//					quit(totalmoves);
						saveBest(totalmoves);

					}
					else /* if (better)*/
					{
						if (depth<(currentSearchDepth-2))
						{
							//bool repeated=false;

							bool repeated=checkCRC(depth);

							if (!repeated)
							{
#if 1
								if (depth<=MAXCRCDEPTH)
								{
									for (int ccc=(MAXCRCHIST-1); ccc>0; ccc--)
										last50crcs[depth][ccc] = last50crcs[depth][ccc-1];

									last50crcs[depth][0]=crcScore[depth];

								}
#endif
							//	dumpCase();

								//getSuitcaseStats(depth+1);
								int temp = myFastestSolution;
								lastFastest=myFastestSolution;

								theLoop();

							}
						}

					}
					// Undo move...
					moveThing(i, oldx, oldy);


					if (depth>=(currentSearchDepth-1))
					{
						// Get out now, since all other solutions
						// in this loop will be the same number of moves
						depth--;
						return 1;
					}
				}
			}

			if (depth>=(currentSearchDepth-1))
			{
				// Get out now, since all other solutions
				// in this loop will be the same number of moves
				depth--;
				return 1;
			}

		}
	}

	depth--;
	return 1;
}

//-------------------------------------------------------------------------
int shuffleMoves=-1;

//-------------------------------------------------------------------------
int readEntryFile(char *fname)
{
	FILE *fp;

	int rows=0;
	int cols=0;
	int xr=0;
	int xc=0;

	fp = fopen(fname,"r");
	if (fp)
	{
		int mode = 0;
		while (!feof(fp))
		{
			int ch = fgetc(fp);
			switch(mode)
			{
			case 0:
			case 2:
				if (ch == ' ')
				{
					mode = 1;
					rows++;
					cols=0;
				}
				else if (((ch < 'A') || ch > 'T') && (ch != '_'))
				{
					if (mode!=2)
					{
						rows++;
						cols=0;
					}
					mode = 2;
				}
				else
				{
					mode=0;
					suitcase[rows][cols]=ch;
					cols++;
				}
				break;
			case 1: // X's
				if (ch == 'X')
				{
					xc++;
				}
				else
				{
					xr++;
					mode=2;
				}
				break;

			}

		}

		fclose(fp);

#ifdef DIAGNOSTICS
		cols=0;
		rows=0;
		for (int i=0; i<30; i++)
			if (suitcase[0][i]!=0)
				cols++;

		for (int j=0; j<15; j++)
			if (suitcase[j][0]!=0)
				rows++;

		printf("Rows: %d  Cols %d\n",rows,cols);
		printf("Xsize == %dx%d\n\n",xr,(xc/xr));
#endif

		newThing.width=xc/xr;
		newThing.height=xr;
		newThing.area = newThing.width*newThing.height;
		newThing.column=0;
		newThing.row=0;
		newThing.hmask = (initialbits[newThing.height]>>newThing.row);
		newThing.wmask = (initialbits[newThing.width]>>newThing.column);

		return 0;
	}
	else
	{
		printf("Unable to open: '%s'\n",fname);
	}

	return -1;
}


//-------------------------------------------------------------------------
int processSuitCase()
{
	int i,j;
	int rows=0;
	int cols=0;

	for (i=0; i<30; i++)
		if (suitcase[0][i]!=0)
			cols++;

	for (j=0; j<15; j++)
		if (suitcase[j][0]!=0)
			rows++;

	suitcaseW=cols;
	suitcaseH=rows;

	numspaces=0;
	memset(fasttest,0,sizeof(unsigned int)*15);
	for (i=0; i<suitcaseW; i++)
		for (j=0; j<suitcaseH; j++)
		{
			if (suitcase[j][i]=='_')
				numspaces++;
			else
				fasttest[j] |= flagbit[i+1];
		}



	numThings=0;
	for (char thing='A'; thing<='T';thing++)
	{  //LINE 1461 ... just before int ret=findThing(thing); was chopped

		int ret=findThing(thing);
		if (ret)
		{
			numThings++;
		}
		else
			break;
	}

	for (i=0; i<suitcaseW; i++)
		for (j=0; j<suitcaseH; j++)
		{
			if (suitcase[j][i]=='_')
			{
				suitcaseNumbers[j*suitcaseW+i]=0;
			}
			else
			{
				suitcaseNumbers[j*suitcaseW+i]=
					things[suitcase[j][i]-'A'].numbers;
			}
		}

	suitcaseNumbersLen = sizeof(short)*suitcaseW*suitcaseH;

	return 0;
}


//-------------------------------------------------------------------------
int perfectSolution(int *minBlocks, int currentDepth)
{
	int gotit[20];
	int bestyet=999;

	theresATrivialSolution=false;

	trivialMoves=999; // Assume there is no good trivial move to start with

	bool cantmove[20];
	for (int z=0; z<numThings; z++)
		if ((things[z].width > biggestW)
			|| (things[z].height>biggestH)
			|| (things[z].area > biggestA))
			cantmove[z]=true;
		else
			cantmove[z]=false;

	*minBlocks=999;
	for (int j=0; j<=suitcaseH-newThing.height; j++)
		for (int i=0; i<=suitcaseW-newThing.width; i++)
		if (solutionPossible[j][i])
		{
			memset(gotit,0,numThings*sizeof(int));
			int total=0;
			int spaces=0;
			int totalthings=0;
			int lastthing=0;

			bool trivialSolution=true;
			bool onebigthing=false;
			int bigthing=-1;
			const int ey = j+newThing.height;
			const int ex = i+newThing.width;
			const int rightEdge=suitcaseW-i-newThing.width;
			const int bottomEdge=suitcaseH-j-newThing.height;
			unsigned int test=initialbits[newThing.width];

			if (i)
				test = (test >> i);

			for (int y=j; y<ey; y++)
			{
				if (impossible[y]&test)
				{
					total=1111;
					goto getoutofhere;
				}

				if (fasttest[y]&test)
				{
					int startY=y*suitcaseW;
					for (int x=i; x<ex; x++)
					{

						if (suitcaseNumbers[startY+x])
						{
							int t = suitcase[y][x]-'A';

							if (!gotit[t])
							{
								if (suitcaseNumbers[startY+x] > 0x0101)
								{
									if (!onebigthing)
									{
										onebigthing=true;
										bigthing=t;
									}
									else
										trivialSolution=false;
								}

								total++;
								totalthings++;
								if (t>lastthing)
									lastthing=t;

								if ((things[t].width > i)
									&& (things[t].width > rightEdge))
								{
									if ((things[t].height > j)
										&& (things[t].height > bottomEdge))
											total+=999;
								}

								if ((!trivialSolution) && (total > bestyet))
									goto getoutofhere;
							}
							gotit[t]++;
						}
						else
							spaces++;
					}
				}
				else
				{
					spaces += newThing.width;
				}
			}

			if (trivialSolution && ((!gotbest) ||
(truebestSolution>(total+currentDepth))))
			{
			//	printf("TRIVIAL!... in %d moves\n", total);
				if (onebigthing)
				{
					if ((!theresATrivialSolution) || (total<trivialMoves))
						if (things[bigthing].area <= (numspaces-spaces))
						{
							{

								memcpy(fastcopy,fasttest,sizeof(unsigned int)*suitcaseH);

								unsigned int testX=initialbits[newThing.width];

								if (i)
									testX = (testX >> i);

								for (int zy=j; zy<j+newThing.height; zy++)
								{
									// prevent any movement INTO this area, for this test
									fastcopy[zy] |= testX;
								}

								int tx,ty;
								if (isThereASpaceCopy(things[bigthing].width,
														things[bigthing].height,
														&tx, &ty))
								{
									theresATrivialSolution=true;
									trivialX=i;
									trivialY=j;
									trivialMoves=total;
									trivialType=1;
									trivialBigthing=bigthing;
									trivialBigX=tx;
									trivialBigY=ty;
								}
								/*
								else
								{
									int laps = findLowOverlaps(bigthing, i, j);
									total+=laps;
								}
								*/

							}
							//else
							//	total++; // cannot be done without moving something else

						}
				}
				else if ((!theresATrivialSolution) || (total<trivialMoves))
				{
					theresATrivialSolution=true;
					trivialX=i;
					trivialY=j;
					trivialMoves=total;
					trivialType=0;
				}
			}

			{
				if (total<bestyet)
				{
					int z;

					// Look for something thats going to require 2 moves extra!
#ifdef EXPERIMENTAL
					int totalblocks=0;
					int objectsum=0;
					int overlapsum=0;
					bool overlaps=false;
					for (z=0; z<=lastthing; z++)
					{
						if (gotit[z])
						{
							totalblocks+=gotit[z];
							objectsum+=things[z].area;

//							if (things[z].area - gotit[z] > (numspaces-spaces))
							if (things[z].area > 1)
							{
								int laps = findLowOverlaps(z, i, j);
								if (laps>overlapsum)
								{
									overlapsum=laps;
									overlaps=true;
								}
							}
						}
					}
					if (overlaps)
					{
						total+=overlapsum;
						goto getoutofhere;
					}
					for (z=0; z<=lastthing; z++)
					{
						if (gotit[z] < things[z].area)
						{
							if (totalblocks-gotit[z] == objectsum-things[z].area)
							{
								// this means we are the ONLY overlapping area
								if ((things[z].width > biggestW)
									|| (things[z].height > biggestH)
									|| (things[z].area > biggestA))
								{
									total += 2;
									goto getoutofhere;
								}

							}
						}
					}
#else
					// Look for something thats going to require 2 moves extra!
					for (z=0; z<=lastthing; z++)
					{
						if (gotit[z])
						{
							if (things[z].area - gotit[z] > (numspaces-spaces))
							{
								// found one case where it cant be moved right now
								total+=2;
								goto getoutofhere;
							}
						}
					}
#endif
/*
					for (z=0; z<numThings; z++)
						if (gotit[z])
							for (int z2=z+1; z2<numThings; z2++)
								if (gotit[z2])
									if (things[z].numbers == things[z2].numbers)
										gotit[z2]=0; // Reduce the working set!
*/
					// Look for something that will require one move extra
					for (z=0; z<=lastthing; z++)
					{
						if (gotit[z])
						{
							if ((things[z].width > biggestW)
								|| (things[z].height > biggestH)
								|| (things[z].area > biggestA))
							{
								total+=1;
								goto getoutofhere;
							}
						}
					}

					{
						memcpy(fastcopy,fasttest,sizeof(unsigned int)*suitcaseH);

						unsigned int testX=initialbits[newThing.width];

						if (i)
							testX = (testX >> i);

						for (int zy=j; zy<j+newThing.height; zy++)
						{
							// prevent any movement INTO this area, for this test
							fastcopy[zy] |= testX;
						}

						for (z=0; z<=lastthing; z++)
						{
							if (gotit[z] && (things[z].area > 1))
							{
								int tx=-1,ty=-1;
								if (isThereASpaceCopy(things[z].width,
														things[z].height,
														&tx, &ty))
								{
								}
								else
								{
									total += 1;
									goto getoutofhere;
								}
							}
						}
					}

				}
			}
getoutofhere:
			if (total<=bestyet)
			{
				// smallest number of blocks we have to move to solve problem!
				if ((total<bestyet) || ((newThing.area - spaces)<*minBlocks))
					*minBlocks = newThing.area - spaces;

				bestyet=total;

				//if (bestyet<=1)
				//	return bestyet; // go home early
			}
		}

	return bestyet;
}

//-------------------------------------------------------------------------
int findThing(const char thing)
{
	int index = thing-'A';

	things[index].column=0;
	things[index].row=0;
	things[index].width=0;
	things[index].height=0;

	int i,j;
	bool gotit=false;

	for (i=0; i<suitcaseW; i++)
		for (j=0; j<suitcaseH; j++)
		{
			if (suitcase[j][i] == thing)
			{
				if (!gotit)
				{
					things[index].column=i;
					things[index].row=j;
					things[index].width = 1;
					things[index].height = 1;
					gotit=true;
				}
				else
				{
					things[index].width = (i-things[index].column)+1;
					things[index].height = (j-things[index].row)+1;
				}
			}
		}

	if (gotit)
	{
		int w = things[index].width;
		int h = things[index].height;
		things[index].area = w * h;
		// Unique size ID to reduce identical cases
		things[index].numbers = w * 256 + h;

		things[index].hmask = (initialbits[h]>>things[index].row);
		things[index].wmask = (initialbits[w]>>things[index].column);

		// Based on these stats, we can never move the object
		if (((w >= newThing.width) && (h >= newThing.height))
			|| (things[index].area > numspaces))
			things[index].nevermove=true;
		else
			things[index].nevermove=false;

		// can never move if its kind of trapped here
		if (((things[index].row < h)
			&& (suitcaseH-h-things[index].row <h))
			&& ((things[index].column < w)
			&& (suitcaseW-w-things[index].column < w)))
			things[index].nevermove=true;

		return 1;
	}
	else
		return 0;
}


//-------------------------------------------------------------------------
int isThereASpaceCopy(const int w, const int h, int *x, int *y)
{
	int i,j;

	// These are the starting coords... so they have a limited range
	int xstop = suitcaseW-w;
	int ystop = suitcaseH;

	unsigned int test = initialbits[w];
	for (i=0; i<=xstop; i++)
	{

		int sequence=0;
		for (j=0; j<ystop; j++)
			if (!(fastcopy[j]&test))
			{
				sequence++;
				if (sequence==h)
				{
					*x = i;
					*y = j-h+1;
					return 1;
				}
			}
			else
				sequence=0;

		test = test>>1;
	}

	return 0;
}

//-------------------------------------------------------------------------
int isThereASpace(const int w, const int h, int *x, int *y)
{
	int i,j;

	int sx=0;
	int sy=-1;

	if (*x >=0)
	{
		sx = *x;
		sy = *y;

//		sx++;
	}

	// These are the starting coords... so they have a limited range
	int xstop = suitcaseW-w;
	int ystop = suitcaseH; //-h;

	unsigned int test = initialbits[w];

	if (sx)
		test = (test>>sx);

	for (i=sx; i<=xstop; i++)
	{

		int sequence=0;
		for (j=0; j<ystop; j++)
		if ((i>sx) || (j>sy))
		{
			if (!(fasttest[j]&test))
			{
				sequence++;
				if (sequence==h)
				{
					*x = i;
					*y = j-h+1;
					return 1;
				}
			}
			else
				sequence=0;
		}

		test = (test>>1);
	}

	return 0;
}


//-------------------------------------------------------------------------
int canWeFinish()
{
	int x=-1;
	int y=-1;
	int ret=0;

	ret = isThereASpace(newThing.width,newThing.height, &x, &y);
	if (ret)
	{
		finalX=x;
		finalY=y;
		return 1;
	}

	return 0;
}

//-------------------------------------------------------------------------
void moveThing(const int i, const int x, const int y)
{
	packObject *mything = &things[i];

	{
		int c = mything->column;
		int r = mything->row;
		int ce = c+mything->width;
		int re = r+mything->height;

		unsigned int test=initialbits[mything->width];
		if (c)
			test = (test >> c);

		test = (~test);
		for (int y1=r; y1<re; y1++)
		{
			int sy=y1*suitcaseW;

			// Turn these bits OFF
			fasttest[y1] &= test;

			for (int x1=c; x1<ce; x1++)
			{
#ifdef EXTRA_DIAGNOSTICS
				if (suitcase[y1][x1]!=i+'A')
				{
					printf("Not The Right square\n");
					DEBUGBREAK;
				}
#endif

				suitcase[y1][x1]='_';
				suitcaseNumbers[sy+x1]=0;
			}
		}
	}

	{
		unsigned int test=initialbits[mything->width];
		if (x)
			test = (test >> x);

		for (int y1=y; y1<y+mything->height; y1++)
		{
			int sy=y1*suitcaseW;

			// Turn these bits ON
			fasttest[y1] |= test;

			for (int x1=x; x1<x+mything->width; x1++)
			{
#ifdef EXTRA_DIAGNOSTICS
				if (suitcase[y1][x1]!='_')
				{
					printf("Non-empty square\n");
					DEBUGBREAK;
				}
#endif

				suitcase[y1][x1]=i+'A';
				suitcaseNumbers[sy+x1]=mything->numbers;
			}
		}
	}

	things[i].column = x;
	things[i].row = y;

	things[i].hmask = (initialbits[things[i].height]>>y);
	things[i].wmask = (initialbits[things[i].width]>>x);

}


#ifndef _MSC_VER
#include <sys/times.h>	/* for the TMS structure */
#define MAXTIME 598	/* 10 minutes worth of seconds */
#define CLK_TCK 100	/* Note: this may be different on YOUR box, you
			   might find the value of HZ in YOUR param.h, but
			   it's gotta be 100 when you ship your entry!
			   Alternatively, use sysconf to deduce CLK_TCK -
			   this approach should work on both systems!	*/
void checktime(void)
{
	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 >= MAXTIME)
	{
		/* PRINT OUT YOUR SOLUTION BEFORE YOU GO! */
		quit(0);
	}
}
#endif


// ----- CUT HERE FOR ENTRY, All else is diagnostics that are not needed

//-------------------------------------------------------------------

void makeMeAnOrder(int *orderlist, int depth, moveStruct *bestmove)
{
	getSuitcaseStats(depth);

	int myBiggestW = biggestW;
	int myBiggestH = biggestH;
	int myBiggestA = biggestA;
	int myFastestSolution=fastestSolution;
	int myMinimumBlocks=minimumBlocks;
	int lowestblocks=minimumBlocks;

	int x,y;
	int bestscore[20];
	int worstscore[20];

	bestmove->block=999;

	int bestever=fastestSolution;
	bool trivial=false;

	for (int z=0; z<numThings; z++)
	{
	//	int i=thingOrder[z]; // Sorted from biggest to smallest
		int i=z;
		bestscore[i]=999;
		worstscore[i]=0;

		x=-1;
		y=-1;
		if ((!things[i].nevermove)
			&& (myBiggestW >= things[i].width)
			&& (myBiggestH >= things[i].height)
			&& (myBiggestA >= things[i].area))
		{

			while (isThereASpace(things[i].width, things[i].height, &x, &y))
			{
				//printf("I can move something! (%c)\n",i+'A');

				int oldx=things[i].column;
				int oldy=things[i].row;

				moves[depth].fromX = oldx;
				moves[depth].fromY = oldy;
				moves[depth].toX=x;
				moves[depth].toY=y;
				moves[depth].block=i;

				moveThing(i, x, y);

				bool redundant=scanMoveList(depth);

				if (!redundant)
				{
					bool repeated=checkCRC(depth);
					if (!repeated)
					{
						getSuitcaseStats(depth);
						if (fastestSolution<bestscore[i])
							bestscore[i]=fastestSolution;
						if (fastestSolution>worstscore[i])
							worstscore[i]=fastestSolution;

						//if (fastestSolution < bestever)
						if (theresATrivialSolution)
						{
							if ((trivialMoves+depth < currentSearchDepth) || (!gotbest))
							{
								if ((!trivial)
									|| ((fastestSolution < bestever)
									||((fastestSolution==bestever)
									&&(minimumBlocks<lowestblocks))))
								{
									memcpy(bestmove, &moves[depth], sizeof(moveStruct));
									bestever=fastestSolution;
									lowestblocks=minimumBlocks;
									trivial=true;
								}
							}
						}
						else if ((!trivial)
							&& ((fastestSolution < bestever)
							||((fastestSolution==bestever)
							&&(minimumBlocks<lowestblocks))))
						{

							memcpy(bestmove, &moves[depth], sizeof(moveStruct));
							bestever=fastestSolution;
							lowestblocks=minimumBlocks;
						}
					}
				}

				moveThing(i, oldx, oldy);
			}
		}
	}

	int neworder[20];
	for (int l1=0; l1<numThings; l1++)
	{
		neworder[l1]=l1;
	}

	for (l1=0; l1<numThings; l1++)
	{
		for (int l2=l1+1; l2<numThings; l2++)
		{
			int n1=neworder[l1];
			int n2=neworder[l2];

			if (!things[n1].nevermove && things[n2].nevermove)
			{
				int swap=neworder[l2];
				neworder[l2]=neworder[l1];
				neworder[l1]=swap;
			}
			else if (things[n1].nevermove && !things[n2].nevermove)
			{
			}
			else if (bestscore[n1]>bestscore[n2])
			{
				int swap=neworder[l2];
				neworder[l2]=neworder[l1];
				neworder[l1]=swap;
			}
			else if (worstscore[n1]>worstscore[n2])
			{
				int swap=neworder[l2];
				neworder[l2]=neworder[l1];
				neworder[l1]=swap;
			}
		}
	}

	memcpy(orderlist,neworder,sizeof(int)*20);

}

//--------------------------------------------------------------------------
//--------------------------------------------------------------------------
//              NOTHING BELOW HERE BELONGS IN THIS FILE FOR THE ACTUAL ENTRY
//--------------------------------------------------------------------------
//--------------------------------------------------------------------------
#ifdef _MSC_VER
#include "packextra.cpp"
#endif

//--
//Kevin Burfitt - Technology Development Group Lead
//Infogrames Melbourne House +61-3-9866-8300 x230
//kburfitt@au.infogrames.com http://www.infogrames.com.au
//Personal Email: zaph@torps.com http://www.torps.com