#define NDEBUG
// GLOBAL.H
//
// some global macros, just for my convenience

#ifndef GLOBAL_H
#define GLOBAL_H

#include <iostream>
#include <fstream>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <time.h>
#include <vector>

using namespace std;

inline int max(int a,int b) { return (a>b)? a : b;};
inline int min(int a,int b) { return (a>b)? b : a;};
inline int sqr(int x){return x*x;};
//inline bool isLetter(char c) {return c>='A' /*&& c <='Z'*/;};
// using a macro is much faster because of the missing optimizer on the target machine
#define isLetter(c) ((c)>='A')

inline double ClockSec() {return (double)clock()/CLOCKS_PER_SEC;};

typedef unsigned long  ULONG; 
typedef unsigned short USHORT;
typedef unsigned char  UBYTE; 
typedef signed long    LONG;
typedef signed short   SHORT;
typedef signed char    BYTE; 

// *******************************************************************

// display error and stop program
void Error(char *);

// global indicator for DebugOutput
extern bool DebugMode;

// maximum word length/grid size
#define MAXWORDLENGTH 16
#define MAXWORDS 512

#define ROWS 16
#define COLUMNS 32

#define MAXTIME 59

#endif

#ifndef INSERTPOSITION_H
#define INSERTPOSITION_H


// struct containg information where to insert a word into the grid
struct InsertPosition
{
	char x,y;
	bool horizontal;
};

// an insert position with a score
struct ScoredInsPos : public InsertPosition
{
	int poolIdx;
	int score;
	int gridIdx;  // number of the grid to which this position was applied
};

// a priority queue for ScoredInsPos, top scores first
class PQScoredInsPos 
{
//	vector<ScoredInsPos> _heap;
	// make memory allocation "by hand", because its faster without optimization
	ScoredInsPos *_heap;
	int _capacity;
	int _size;

public:
	PQScoredInsPos()
		:_capacity(100000),_size(0)
	{
		// use malloc because we need realloc later
		_heap=(ScoredInsPos *)malloc(sizeof(ScoredInsPos)*_capacity);
	};
	~PQScoredInsPos()
	{
		free(_heap);
	}

	// insert a new object into the queue
	void Insert(const ScoredInsPos &newInsPos);

	// get a reference to the topmost element with the highest score (or NULL, if empty)
	const ScoredInsPos *Top() const
	{
		if(_size>0)
			return &_heap[0];
		else
			return NULL;
	}
	
	// remove the top element from the heap
	void Pop();

	int Size() const {return _size;}
};


#endif
// WORDPOOL.H
//
// static pool of all words in the wordlist
//
// (base class for all word lists)

#ifndef WORDPOOL_H
#define WORDPOOL_H



// a word together with its length
struct Word
{
	char *word;  // the characters of the word
	int length;		   // the word length
};

// pair of a word index and a character position
struct WordCharPosPair
{
	short poolIdx;
	short charPos;  // character position in this word
};

typedef vector<WordCharPosPair> WordIndexVector;

class WordPool
{
private:
	static int _poolsize;
	static Word _wordList[MAXWORDS];

	// foreach letter of the alphabet: vector containing all words having this letter
	static WordIndexVector _wordsPerChar[26];
	
	// foreach letter pair: vector containing all words having this letter combination
	static WordIndexVector _wordsPer2Chars[26][26];

	// foreach letter triple: vector containing all words having this letter combination
	static WordIndexVector _wordsPer3Chars[26][26][26];

	// foreach letter pair or letter triple: marker, if the pair/triple exists in the pool
	static bool  _pairExists[26][26];
	static bool  _tripleExists[26][26][26];

private:
	// no constructor is allowed outside: everything is static here
	WordPool(){};
	
	// Initialize the lookup table '_wordsPerChar' and '_wordsPer2Chars'
	static void InitLookupTables();

	// sort the _wordList
	static void SortWords();

	// helper functions for sorting
	static void CalcLetterScore(int *letterScore,const Word *wordList, int listsize);
	static void CalcWordScore(int *wordscore,const int *letterScore,const Word *wordList,int listsize);
	static void SordWordsByScore(Word *wordList,int listsize ,int *wordScore);


public:
	static void ReadPool(const char *filename);
	static int GetPoolSize() {return _poolsize;};

	static int GetWordLength(int nr)
	{
		assert(nr>=0 && nr < _poolsize);
		return _wordList[nr].length;
	}
	// get word and length in one step
	static const Word *GetPoolWord(int nr)
	{
		assert(nr>=0 && nr <_poolsize);
		return &_wordList[nr];
	}


	static WordIndexVector &GetWordsPerChar(char c)
	{
		assert(isLetter(c));
		return _wordsPerChar[c-'A'];
	}
	
	static WordIndexVector &GetWordsPer2Chars(char c1,char c2)
	{
		assert(isLetter(c1));
		assert(isLetter(c2));
		return _wordsPer2Chars[c1-'A'][c2-'A'];
	}

	static WordIndexVector &GetWordsPer3Chars(char c1,char c2,char c3)
	{
		assert(isLetter(c1));
		assert(isLetter(c2));
		assert(isLetter(c3));
		return _wordsPer3Chars[c1-'A'][c2-'A'][c3-'A'];
	}
	static WordIndexVector &GetWordsPer12Chars(char c,char cAfter)
	{
		if(cAfter!=0)
			return GetWordsPer2Chars(c,cAfter);
		else
			return GetWordsPerChar(c);
	}

	static WordIndexVector &GetWordsPer123Chars(char c1,char c2,char c3)
	{
		if(c1!=0 && c3 !=0)
			return GetWordsPer3Chars(c1,c2,c3);
		else if(c1!=0)
			return GetWordsPer2Chars(c1,c2);
		else if(c3!=0)
			return GetWordsPer2Chars(c2,c3);
		else
			return GetWordsPerChar(c2);
	}

	static bool PairExists(char c1,char c2)
	{
		assert(isLetter(c1));
		assert(isLetter(c2));
		return _pairExists[c1-'A'][c2-'A'];
	}
	static bool TripleExists(char c1,char c2,char c3)
	{
		assert(isLetter(c1));
		assert(isLetter(c2));
		assert(isLetter(c3));
		return _tripleExists[c1-'A'][c2-'A'][c3-'A'];
	}
	static bool PairOrTripleExists(char c1,char c2,char c3)
	{
		if(c1!=0 && c3!=0) return TripleExists(c1,c2,c3);
		if(c1!=0) return PairExists(c1,c2);
		if(c3!=0) return PairExists(c2,c3);
		return true;
	}

	// return index of word in "pool", or -1 if word not in pool
	static int FindWordIndex(const char *word)
	{
		// ** slow version, to be optimized
		for(int i=0;i<_poolsize;++i)
			if(strcmp(word,_wordList[i].word)==0)
				return i;
		return -1;
	}
};

#endif

// class for crossword grids;
// every grid knows the words already stored in it
// words can be inserted, but never removed

#ifndef GRID_H
#define GRID_H

// blocking character
#define BLOCK_CHAR '#'

// guessed coverage percentage for the empty cells
#ifndef COVERAGE
#define COVERAGE 87
#endif

// State of a character in the grid
enum State_e
{
	ST_EMPTY=0,ST_HORIZONTAL=1,ST_VERTICAL=2,ST_HORVERT=3,ST_BLOCKED=4
};

// ******************************************************************
// the grid class

class Grid
{
	// **********************************************************************
	// member variables

	// the grid _cells
	char _cells[COLUMNS][ROWS];
	UBYTE _cellState[COLUMNS][ROWS];

	// indicator whether the flipper was used
	bool _hasFlipper;

	// sum of the number of characters of all words
	int _charCount;

	// the first column where new characters are expected for score guessing
	BYTE _firstFreeColumnEdge[ROWS];

	// analogue to _firstFreeColumnEdge
	BYTE _firstFreeRowEdge[COLUMNS];
	BYTE _firstFreeRow[COLUMNS];

	// the number of empty cells outside the maximum row or maximum column
	int _emptyCellsHoriz, _emptyCellsVertic;

	// the position of the first incomplete word (x=y=-1, if there is no incomplete word)
	InsertPosition _firstIncompleteWord;
	bool _firstIncompleteWordValid;	// indicator if _firstIncompleteWord has to be calculated

	// **********************************************************************
	// put letter c into the grid, direction information included
	void PutLetter(char c, int x,int y,State_e dir)
	{
		assert(isLetter(c));
		assert(x>=0 && y>=0 && x<COLUMNS && y<ROWS);
		assert(dir==ST_HORIZONTAL ||dir==ST_VERTICAL);

		_cells[x][y]=c;
		UBYTE *pState = &_cellState[x][y];
		UBYTE state = *pState | dir;
		if((state & ST_HORVERT)==ST_HORVERT)
			state |= ST_BLOCKED;
		*pState = state;
	}

	// put letter c into the grid, direction information included;
	// if there is already another character at (x,y), use the flipper
	void PutLetterFlipper(char c, int x,int y,State_e dir)
	{
		assert(isLetter(c));
		assert(x>=0 && y>=0 && x<COLUMNS && y<ROWS);
		assert(dir==ST_HORIZONTAL ||dir==ST_VERTICAL);

		if(isLetter(_cells[x][y]) && _cells[x][y]!=c)
		{
			_cells[x][y]='*';
			assert(!_hasFlipper);
			_hasFlipper = true;
		}
		else
			_cells[x][y]=c;

		UBYTE *pState = &_cellState[x][y];
		UBYTE state = *pState | dir;
		if((state & ST_HORVERT)==ST_HORVERT)
			state |= ST_BLOCKED;
		*pState = state;
	}

	// put BLOCK_CHAR into the grid, direction information included
	void PutBlockChar(int x,int y,State_e dir)
	{
		assert(x>=0 && y>=0 && x<COLUMNS && y<ROWS);
		assert(dir==ST_HORIZONTAL ||dir==ST_VERTICAL);

		_cells[x][y]=BLOCK_CHAR;
		_cellState[x][y] |= dir;
	}


	// remove a letter from a cell 
	void RemoveLetter(int x,int y,State_e dir)
	{
		assert(x>=0 && y>=0 && x<COLUMNS && y<ROWS);
		assert(dir==ST_HORIZONTAL ||dir==ST_VERTICAL);
		assert((_cellState[x][y] & dir)!=0);
		assert(isLetter(_cells[x][y]));

		UBYTE state = (_cellState[x][y] &= ~(dir|ST_BLOCKED));
		if((state &ST_HORVERT)==0)
			_cells[x][y] = ' ';
	}

	// remove a blocking character from a cell 
	void RemoveBlockChar(int x,int y,State_e dir)
	{
		assert(x>=0 && y>=0 && x<COLUMNS && y<ROWS);
		assert(dir==ST_HORIZONTAL ||dir==ST_VERTICAL);
		assert(_cells[x][y] == BLOCK_CHAR);

		UBYTE *pState = &_cellState[x][y];
		char *pCell = &_cells[x][y];
		UBYTE state = (*pState & ~(dir));

		// do not delete blocking character if it is also the end of another word
		// in the current direction
		if(dir == ST_HORIZONTAL)
		{
			if(x>0 && isLetter(*(pCell-ROWS)) && (*(pState-ROWS) & dir)!=0)
				return;
			if(x<COLUMNS-1 && isLetter(*(pCell+ROWS)) && (*(pState+ROWS) & dir)!=0)
				return;
		}
		else
		{
			if(y>0 && isLetter(*(pCell-1)) && (*(pState-1) & dir)!=0)
				return;
			if(y<ROWS-1 && isLetter(*(pCell+1)) && (*(pState+1) & dir)!=0)
				return;
		}

		*pState =state;  // now unset the directional bit
		if((state &ST_HORVERT)!=0)
			return;

		*pCell = ' ';
	}

	void IncreaseFirstFreeColumnEdge(int y,int newFreeCol)
	{
		assert(y>=0 && y<ROWS);
		if(newFreeCol>COLUMNS)
			newFreeCol = COLUMNS;
		if(newFreeCol>_firstFreeColumnEdge[y])
		{
			_emptyCellsHoriz -= newFreeCol - _firstFreeColumnEdge[y];
			_firstFreeColumnEdge[y]=newFreeCol;
		}
	}

	// adjust _firstFreeColumnEdge[y-1,y,y+1]
	void AdjustFreeColumns(int y,int x)
	{
		int col = x+1;
		IncreaseFirstFreeColumnEdge(y,col+1);
		if(y>0)
			IncreaseFirstFreeColumnEdge(y-1,col);
		if(y<ROWS-1)
			IncreaseFirstFreeColumnEdge(y+1,col);
	}

	void IncreaseFirstFreeRowEdge(int x,int newFreeRow)
	{
		assert(x>=0 && x<COLUMNS);
		if(newFreeRow>ROWS)
			newFreeRow = ROWS;
		if(newFreeRow>_firstFreeRowEdge[x])
		{
			_emptyCellsVertic -= newFreeRow - _firstFreeRowEdge[x];
			_firstFreeRowEdge[x]=newFreeRow;
		}
	}

	// adjust _firstFreeRow and related arrays after inserting a letter at (x,y)
	void AdjustFreeRows(int x,int y)
	{
		int row = y+1;
		if(row>_firstFreeRow[x])
			_firstFreeRow[x]=row;
		// adjust _firstFreeRowEdge
		IncreaseFirstFreeRowEdge(x,row+1);
		if(x>0)
			IncreaseFirstFreeRowEdge(x-1,row);
		if(x<COLUMNS-1)
			IncreaseFirstFreeRowEdge(x+1,row);
	}

	// test if a word matches the grid characters at a specific position
	// (without checking neighbours and cell states)
	bool DoCharsMatchHoriz (const Word &word,int x,int y) const;
	bool DoCharsMatchVertic(const Word &word,int x,int y) const;

	// test if a word matches the grid characters at a specific position except 1
	// (without checking neighbours and cell states)
	bool DoCharsMatchHoriz1Miss (const Word &word,int x,int y) const;
	bool DoCharsMatchVertic1Miss(const Word &word,int x,int y) const;

	bool IsCompletableVertic(char c,int x,int y) const;
	bool IsCompletableHoriz(char c,int x,int y) const;

	bool FindIncompleteWordPosHoriz(int &xResult,int &yResult) const;
	bool FindIncompleteWordPosVertic(int &xResult,int &yResult) const;

	// try to insert a word into the grid horizontally or vertically
	void InsertWordHoriz(int poolIdx,int x,int y);
	void InsertWordVertic(int poolIdx,int x,int y);

	// try to insert a word into the grid horizontally or vertically, using the flipper square
	// exactly once.
	void InsertWordHorizWithFlipper(int poolIdx,int x,int y);
	void InsertWordVerticWithFlipper(int poolIdx,int x,int y);

	// remove a word, returns the letters in "word"
	void RemoveWordHoriz(int x,int y,char *word);
	void RemoveWordVertic(int x,int y,char *word);

	// helper functions to get cells before and after a given position
	// returns 0 for empty cells or border
	void GetNeighboursHoriz(int x, int y, char &cBefore,char &cAfter) const
	{
		cBefore=0;
		cAfter=0;
		register const char *pCell = &_cells[x-1][y];
		if(x>0)
		{
			cBefore = *pCell;
			if(!isLetter(cBefore))
				cBefore = 0;

		}
		if(x<COLUMNS-1)
		{
			pCell +=ROWS+ROWS;
			cAfter = *pCell;
			if(!isLetter(cAfter))
				cAfter = 0;
		}
	}
	void GetNeighboursVertic(int x,int y, char &cBefore,char &cAfter) const
	{
		cBefore=0;
		cAfter=0;
		register const char *pCell = &_cells[x][y-1];
		if(y>0)
		{
			cBefore = *pCell;
			if(!isLetter(cBefore))
				cBefore = 0;
		}
		if(y<ROWS-1)
		{
			pCell+=2;
			cAfter = *pCell;
			if(!isLetter(cAfter))
				cAfter = 0;
		}
	}

	bool AreNeighboursBlockedVertic(int x,int y) const
	{
		register const UBYTE *pState = &_cellState[x][y-1];
		if(y>0)
		{
			if(*pState & ST_BLOCKED)
				return true;
		}
		if(y<ROWS-1)
		{
			pState+=2;
			if(*pState & ST_BLOCKED)
				return true;
		}
		return false;
	}

	bool AreNeighboursBlockedHoriz(int x, int y) const
	{
		register const UBYTE *pState = &_cellState[x-1][y];
		if(x>0)
		{
			if(*pState & ST_BLOCKED)
				return true;

		}
		if(x<COLUMNS-1)
		{
			pState +=ROWS+ROWS;
			if(*pState & ST_BLOCKED)
				return true;
		}
		return false;
	}

public:
	// test how many cells are empty before the current cell (horizontally)
	int CountEmptyCellsBeforeHoriz(int xStart,int y) const
	{
		register int count=0;
		register int x=xStart-1;
		register const char *pCell = &_cells[x][y];
		while(x>=0 && *pCell==' ')
		{
			++count;
			--x;
			pCell-=ROWS;
		}
		return count;
	}
	// test how many cells are empty before the current cell (vertically)
	int CountEmptyCellsBeforeVertic(int x,int yStart) const
	{
		register int count=0;
		register int y=yStart-1;
		register const char *pCell = &_cells[x][y];
		while(y>=0 && *pCell==' ')
		{
			++count;
			--y;
			--pCell;
		}
		return count;
	}

private:

	// find the first column where a newly inserted word can start
	// if it has to cross (x,y)
	int FindStarterColumn(int xStart,int y) const
	{
		register int x=xStart;
		register int result = x;
		register const char *pCell =  &_cells[x-1][y];
		register const UBYTE *pState = &_cellState[x-1][y];
		while(x>0)
		{
			if(*pCell == BLOCK_CHAR)
				return x;
			if (*pCell ==' ')
				result = x;
			if((*pState&ST_BLOCKED)!=0)
				return result;
			pCell-=ROWS;
			pState-=ROWS;
			--x;
		}
		return 0;
	}

	// find the first row where a newly inserted word can start
	// if it has to cross (x,y)
	int FindStarterRow(int x,int yStart) const
	{
		register int y=yStart;
		register int result = y;
		register const char *pCell =  &_cells[x][y-1];
		register const UBYTE *pState = &_cellState[x][y-1];
		while(y>0)
		{
			if(*pCell == BLOCK_CHAR)
				return y;
			if(*pCell ==' ')
				result = y;
			if((*pState&ST_BLOCKED)!=0)
				return result;
			--pCell;
			--pState;
			--y;
		}
		return 0;
	}


	// unblock all cells that are not used in both directions
	void UnblockPossibleCells()
	{
		register UBYTE state;
		register UBYTE *pState=&_cellState[0][0];
		register int x,y;

		for(x=0;x<COLUMNS;++x)
		{
			for(y=0;y<ROWS;++y)
			{
				state = *pState;
				if((state & ST_HORVERT)!=ST_HORVERT)
				{
					state &= ~ST_BLOCKED;  // clear "blocked" state
					*pState=state;
					ResetBlockedState(x,y);  //but reset it, if no word can be inserted there
				}
				++pState;
			}
		}
	}

	void ResetBlockedState(int x,int y);

	// test for incompleteness in the area where a new word was inserted
	void CheckIncompleteAfterHorizInsert(int x,int y,int length);
	void CheckIncompleteAfterVerticInsert(int x,int y,int length);

public:
	// default constructor
	Grid();                     

	// comparison
	bool operator==(const Grid &grid) const;
	bool operator<(const Grid &grid) const;  // to allow set operations

	// hash code calculation (not const because of buffering results)
	ULONG HashCode();

	// get content of a grid cell;
	// empty fields have spaces, blocked fields are '#'
	char GetCell(int x,int y) const
	{
		assert(0<=x && x < COLUMNS);
		assert(0<=y && y < ROWS);
		return _cells[x][y];
	}

	// expose the adress of a cell to the caller
	const char *GetPtrCell(int x,int y) const
	{
		assert(0<=x && x < COLUMNS);
		assert(0<=y && y < ROWS);
		return &_cells[x][y];
	}

	bool IsLetter(int x,int y) const
	{
		assert(0<=x && x < COLUMNS);
		assert(0<=y && y < ROWS);
		return isLetter(_cells[x][y]);
	}

	// state of a grid cell;
	State_e GetCellState(int x,int y) const
	{
		assert(0<=x && x < COLUMNS);
		assert(0<=y && y < ROWS);
		return (State_e) _cellState[x][y];
	}

	// set the cell state to "BLOCKED" to avoid further searching
	void BlockCell(int x,int y)
	{
		assert(0<=x && x < COLUMNS);
		assert(0<=y && y < ROWS);
		_cellState[x][y] |= ST_BLOCKED;
	}

	// Tries to insert a word into the grid
	// returns false if not possible
	void InsertWord(int poolIdx,int x,int y,bool horizontalDir);

	// Tries to insert a word into the grid, using the flipper square
	void InsertWordWithFlipper(int poolIdx,int x,int y,bool horizontalDir);

	// test if a word can be inserted at the given position in the specific direction
	bool DoesWordFit(int poolIdx,int x, int y,bool horizontalDir);

	// test if a word can be inserted at the given position (includes neighbour checking)
	bool DoesWordFitHoriz(const Word *word,int x,int y);
	bool DoesWordFitVertic(const Word *word,int x,int y);

	// test if a word can be inserted at the given position, with 1 flipper square (includes neighbour checking)
	bool DoesWordFit1Miss(int poolIdx,int x, int y,bool horizontalDir);
	bool DoesWordFitHorizFlipper(const Word *word,int x,int y);
	bool DoesWordFitVerticFlipper(const Word *word,int x,int y);

	// get characters at xStart,yStart till the next BLOCK_CHAR
	// never return more than MAXWORDLENGTH characters
	int GetCharPattern(int xStart,int yStart,bool horizontalDir,char *pattern) const;
	int GetCharPatternHoriz(int xStart,int yStart,char *pattern) const;
	int GetCharPatternVertic(int xStart,int yStart,char *pattern) const;


	int GetFirstFreeRow(int x) const
	{
		assert(0<=x && x < COLUMNS);
		return _firstFreeRow[x];
	}

	// the score (only characters, not number of words) 
	int Score() const {return _charCount ;}

	// the guessed score when about x% of the empty space will be used
	int ExpectedScore() const 
	{
		int emptyCells = _emptyCellsHoriz+_emptyCellsVertic;
		return _charCount+ emptyCells * _charCount *COVERAGE / (2*ROWS*COLUMNS - emptyCells)/100;
	}

	// the expected number of seconds to get the expected score
	double ExpectedTime() const
	{
		if(Score()>0)
			return ClockSec() / Score() * ExpectedScore();
		else return 54;
	}

	// calculate the score after inserting, without actually doing the insert
	int ScoreAfterInsert(int poolIdx,int x,int y,bool horizontalDir) const
	{
		return _charCount+WordPool::GetWordLength(poolIdx);
	}

	// the guessed score when about x% of the empty space will be used
	// (corresponding to ScoreAfterInsert)
	int ExpectedScoreAfterInsert(int poolIdx,int x,int y,bool horizontalDir) const;

	// look for an incomplete word in the current grid
	// returns true, if there is one, and in insPos the result
	bool FindIncompleteWordPos(InsertPosition &insPos);

	// remove word starting at x,y in horizontal or vertical direction
	// (very slow, since this class is optimized for inserting and copying, but not for removal)
	void RemoveWord(int x,int y,bool horizontalDir);

	// test if there is a removable word at position x,y
	bool IsThereRemoveableWord(int x, int y,bool horizontalDir) const
	{
		assert(0<=x && x < COLUMNS);
		assert(0<=y && y < ROWS);
		if(!isLetter(_cells[x][y]))
			return false;

		if(horizontalDir)
		{
			if((_cellState[x][y] & ST_HORIZONTAL)==0)
				return false;
			if(x>0 && _cells[x-1][y]!=BLOCK_CHAR)
				return false;
		}
		else
		{
			if((_cellState[x][y] & ST_VERTICAL)==0)
				return false;
			if(y>0 && _cells[x][y-1]!=BLOCK_CHAR)
				return false;
		}
		return true;
	}

	// test if the words are connected (needed after removal)
	bool IsConnected() const;

	bool HasFlipper() const 
	{
		return _hasFlipper;
	}
};

// print the grid
ostream& operator<< (ostream &os,const Grid &grid);


#endif

#ifndef HASHTABLE_H
#define HASHTABLE_H


// class for ULONG hash sets
// implemented for closed hashing
class Hashtable
{
	int _size;
	ULONG *_tableMem;

public:
	Hashtable(int size):_size(size)
	{
		_tableMem = new ULONG[size];
		memset(&_tableMem[0],0,size*sizeof(ULONG));
	}
	~Hashtable()
	{
		delete[] _tableMem;
	}
	void Insert(ULONG value)
	{
		++value; // make sure value is not zero
		int i=value%_size;
		while(_tableMem[i]!=0)
		{
			++i;
			if(i==_size)
				i=1;
		}
		_tableMem[i]=value;
	}
	bool Test(ULONG testValue)
	{
		++testValue;
		int i=testValue%_size;
		register ULONG value;
		while((value=_tableMem[i])!=0)
		{
			if(value==testValue)
				return true;
			++i;
			if(i==_size)
				i=1;
		}
		return false;
	}
};

#endif
#ifndef SOLVER_H
#define SOLVER_H


class Grid;


// the main problem solving class
class Solver
{
	static int _LevelSize;
	
	static void FindInitialGrids(vector<Grid> &gridVec);
	static void FindNextGridLevel(vector<Grid> &gridVec,vector<Grid> &nextGridVec);
	static void AddWordsThroughCell(Grid &grid,int gridIdx,int x,int y,PQScoredInsPos &posQueue);
	static void AddAllGridsWithOneWordLess(const Grid &grid,vector<Grid> *gridVec);
	static void AddAllGridsWithTwoWordLess(const Grid &grid,vector<Grid> *gridVec);

	static void GetMatchingWordsWithFlipper(Grid &theGrid,int gridIdx, int xStart,int yStart, bool horizontalDir, vector<ScoredInsPos> &result);
	static void FindAllWordsWithFlipper(vector<Grid> &gridVec,vector<Grid> &nextGridVec);

	// find all positions where a word can be removed from the grid (without
	// checking for connectedness)
	static void FindRemovePositions(const Grid &grid,vector<InsertPosition> &posVec);

public:
	static Grid *FindBestGrid();
};

#endif


// insert a new object into the priority queue
void PQScoredInsPos::Insert(const ScoredInsPos &newInsPos)
{
	int pos = _size;
	++_size;
	if(_size>=_capacity)
	{
		_capacity*=2;
		_heap=(ScoredInsPos *)realloc(_heap,sizeof(ScoredInsPos)*_capacity);
	}

	while(pos>0)
	{
		int posAbove = (pos-1)>>1;
		if(_heap[posAbove].score< newInsPos.score)
		{
			_heap[pos]=_heap[posAbove];
			pos=posAbove;
		}
		else break;
	}
	_heap[pos] = newInsPos;
}


// remove the top element from the heap (and re-heap)
void PQScoredInsPos::Pop()
{
#ifdef _DEBUG
	if(_size<=0)
		Error("calling Pop for an empty heap");
#endif
	ScoredInsPos insPos = _heap[_size-1];  // remember last element
	--_size;
	int pos=0;  // Position where to place insPos
	int posBelow = 1;
	while(posBelow<_size)
	{
		// set posBelow to the sucessor element with the bigger score
		if(posBelow+1 < _size && (_heap[posBelow].score < _heap[posBelow+1].score) )
			++posBelow;
		if(insPos.score<_heap[posBelow].score)
		{
			_heap[pos]=_heap[posBelow];
			pos = posBelow;
			posBelow=pos+pos +1;
		}
		else break;
	}
	_heap[pos] = insPos;
}


// WordPool.cpp
//
// pool of all words in the wordlist
//


int WordPool::_poolsize=0;
Word WordPool::_wordList[MAXWORDS];
WordIndexVector WordPool::_wordsPerChar[26];
WordIndexVector WordPool::_wordsPer2Chars[26][26];
WordIndexVector WordPool::_wordsPer3Chars[26][26][26];

bool WordPool::_pairExists[26][26];
bool WordPool::_tripleExists[26][26][26];


// ********************************************************************

// helper function
bool TestIfContainsIdx(const WordIndexVector &wiVec,int poolIdx)
{
	int size = (int)wiVec.size();
	for(int k=0;k<size;++k)
	{
		if(wiVec[k].poolIdx==poolIdx)
			return true;
	}
	return false;
}

void WordPool::SortWords()
{
	// give each letter a score
	int letterScore[26];
	CalcLetterScore(letterScore,_wordList,_poolsize);

	// score for each word is the sum of each letter score
	int wordScore[MAXWORDS];
	CalcWordScore(wordScore,letterScore,_wordList,_poolsize);

	SordWordsByScore(_wordList,_poolsize,wordScore);

}

// count how many times a letter occurs
void WordPool::CalcLetterScore(int *letterScore,const Word *wordList, int listsize)
{
	int i,j;
	// clear the score table
	for(i=0;i<26;++i)
		letterScore[i]=0;
	
	// count the letters
	for(i=0;i<listsize;++i)
	{
		const Word *word = &wordList[i];
		for(j=0;j<word->length;++j)
		{
			++letterScore[word->word[j]-'A'];
		}
	}
}

void WordPool::CalcWordScore(int *wordscore,const int *letterScore,const Word *wordList,int listsize)
{
	int i,j;

	// foreach word: 
	for(i=0;i<listsize;++i)
	{
		const Word *word = &wordList[i];
		// sum up the letter scores for this word
		int sum=0;
		for(j=0;j<word->length;++j)
			sum+=letterScore[word->word[j]-'A'];
		// subtract the score for the letters of the word itself
		sum-=word->length;
		// remember the score
		wordscore[i]=sum / word->length;
	}
}

// sort words by score, higher score first
void WordPool::SordWordsByScore(Word *wordList,int listsize ,int *wordScore)
{
	int i,j;
	for(i=0;i<listsize;++i)
	{
		// find word with max score
		int maxScore=-1;
		int idx;
		for(j=i;j<listsize;++j)
		{
			if(wordScore[j]>maxScore)
			{
				maxScore = wordScore[j];
				idx=j;
			}
		}
		if(idx==i)
			continue;
		// bring the found word to the front of the list
		Word tmpWord=wordList[idx];
		wordList[idx]=wordList[i];
		wordList[i]=tmpWord;
		
		int tmpScore = wordScore[idx];
		wordScore[idx]=wordScore[i];
		wordScore[i]=tmpScore;
	}
}


void WordPool::InitLookupTables()
{
	int i,j,length;
	const char *word;
	char c;
	WordCharPosPair newPair;

	memset(_pairExists,0,sizeof(bool)*26*26);
	memset(_tripleExists,0,sizeof(bool)*26*26*26);
	
	for(i=0;i<_poolsize;++i)
	{
		length=_wordList[i].length;
		word=_wordList[i].word;
		for(j=0;j<length;++j)
		{
			c=word[j];
			if(!isLetter(c))
			{
				cerr << "word number " << i << ", letter number " << j << endl;
				Error("wrong letter in InitLookupTables");
			}

			WordIndexVector &wiVec = _wordsPerChar[c-'A'];
			newPair.poolIdx = (short)i;
			newPair.charPos = j;
			wiVec.push_back(newPair);

			// next part is only for two letter sequences
			if(j+1>=length)
				continue;

			char c2=word[j+1];
			_pairExists[c-'A'][c2-'A']=true;

			WordIndexVector &wiVec2 = _wordsPer2Chars[c-'A'][c2-'A'];
			newPair.poolIdx = (short)i;
			newPair.charPos = j;
			wiVec2.push_back(newPair);

			// and the last one is for three letter sequences
			if(j+2>=length)
				continue;
			char c3=word[j+2];
			_tripleExists[c-'A'][c2-'A'][c3-'A']=true;

			WordIndexVector &wiVec3 = _wordsPer3Chars[c-'A'][c2-'A'][c3-'A'];
			newPair.poolIdx = (short)i;
			newPair.charPos = j;
			wiVec3.push_back(newPair);
		}
	}
}


// read a list of words into the word pool from the input stream 'is'
void WordPool::ReadPool(const char *filename)
{
	char buf[MAXWORDLENGTH+2];
	int i,j,length;
	FILE *file;

	file=fopen(filename,"r");
	if(!file)
		Error("file not found");

	_poolsize=0;
	for(i=0;i<MAXWORDS;i++){
		if(!fgets(buf,MAXWORDLENGTH+2,file))
			break;
		length=(int)strlen(buf);
		while(length>0 && !isalpha(buf[length-1]))
			buf[--length]=0;                     // remove eol characters
		if(length<=0)                        // ignore empty lines
			continue;
		// convert buffer to upper case
		for(j=0;j<length;++j)
			buf[j]=toupper(buf[j]);

		_wordList[_poolsize].word=new char[length+1];  // and copy it into the pool
		strcpy(_wordList[_poolsize].word,buf);
		_wordList[_poolsize].length=length;             // remember its length
		_poolsize++;
	}

	// Sort word list, words with often used letters first
//	SortWords();
	if(DebugMode)
	{
		cerr << "---------------------\n";
		for(int i=0;i<_poolsize;++i)
		{
			cerr << _wordList[i].word << "\n";
		}
		cerr << "---------------------\n";
	}


	InitLookupTables();
	if(DebugMode)
		cerr << "Poolsize: " << _poolsize << endl;
}


// Grid.cpp
//
// class for crossword grids;


// ******************************************************************
// constructor for empty Grid
Grid::Grid()
:_hasFlipper(false),_charCount(0),
	_emptyCellsHoriz(ROWS*COLUMNS),
	_emptyCellsVertic(ROWS*COLUMNS),
	_firstIncompleteWordValid(true)
{
	memset(_cells,(int)' ',ROWS*COLUMNS*sizeof(char));
	memset(_cellState,ST_EMPTY,ROWS*COLUMNS*sizeof(UBYTE));
	memset(_firstFreeColumnEdge,0,ROWS*sizeof(BYTE));
	memset(_firstFreeRowEdge,0,COLUMNS*sizeof(BYTE));
	memset(_firstFreeRow,0,COLUMNS*sizeof(BYTE));
	_firstIncompleteWord.x=-1;
	_firstIncompleteWord.y=-1;
}

// comparison
bool Grid::operator==(const Grid &grid) const
{
	if(_charCount != grid._charCount)
		return false;
	if(_hasFlipper != grid._hasFlipper)
		return false;
	return memcmp(_cells,grid._cells,ROWS*COLUMNS*sizeof(UBYTE)) == 0;
}

bool Grid::operator<(const Grid &grid) const
{
	if(_charCount<grid._charCount)
		return true;
	if(_charCount>grid._charCount)
		return false;
	return memcmp(_cells,grid._cells,ROWS*COLUMNS*sizeof(UBYTE)) < 0;
}
// *****************************************************************




// calculation of a hash code.
// important: blocked or filled cells are treated equal!
// so two equally shaped grids with same insertion points cells give the same hash code
ULONG Grid::HashCode()
{
	register ULONG result=0;
	register ULONG mult = 1;
	register ULONG cell;
	register UBYTE *pState;
	register char *pCell;
	register const ULONG pi=314159;
	register int count;

	result += _charCount * mult;
	mult *= pi;
	
	pState = &_cellState[0][0];
	pCell = &_cells[0][0];

	// unrolled loop to speed up calculation
	for(count=0;count<COLUMNS;++count)
	{
// helper makro for loop unrolling
#define HASHADD	{ \
		cell = *pCell; \
		if(cell == ' ') \
			result+= mult<<5; \
		else \
			if(cell != BLOCK_CHAR && (*pState & ST_BLOCKED)==0) \
				result+=cell * mult; \
		mult *= pi; \
		++pState; \
		++pCell; \
	}
// end of macro

		HASHADD;
		HASHADD;
		HASHADD;
		HASHADD;

		HASHADD;
		HASHADD;
		HASHADD;
		HASHADD;

		HASHADD;
		HASHADD;
		HASHADD;
		HASHADD;

		HASHADD;
		HASHADD;
		HASHADD;
		HASHADD;
	}

	return result;
}

// *****************************************************************
// insert a word into the grid horizontally at (xstart,ystart), using the flipper square
void Grid::InsertWordHorizWithFlipper(int poolIdx,int xstart,int ystart)
{
	const Word *word=WordPool::GetPoolWord(poolIdx);

#ifdef _DEBUG
	// does the the word match?
	if(!DoesWordFitHorizFlipper(word,xstart,ystart))
		Error("InsertWordHorizWithFlipper, word does not fit");
#endif

	// get the word out of the word pool
	int length = word->length ;
	_charCount+= length;

	// put the characters into the grid
	int xend=xstart + length;
	const char *pWord = word->word;
	for(int x=xstart;x<xend;x++)
	{
		PutLetterFlipper(*pWord,x,ystart,ST_HORIZONTAL);
		AdjustFreeRows(x,ystart);
		++pWord;
	}
	AdjustFreeColumns(ystart,xend-1);

	// word start/end by blocking character
	if(xstart>0)
		PutBlockChar(xstart-1,ystart,ST_HORIZONTAL);
	if(xend<COLUMNS)
		PutBlockChar(xend,ystart,ST_HORIZONTAL);
}

// try to insert a word into the grid vertically at (xstart,ystart)
void Grid::InsertWordVerticWithFlipper(int poolIdx,int xstart,int ystart)
{
	// get the word out of the word pool
	const Word *word=WordPool::GetPoolWord(poolIdx);

#ifdef _DEBUG
	// does the word match the grid?
	if(!DoesWordFitVerticFlipper(word,xstart,ystart))
		Error("InsertWordVertic, word does not fit");
#endif

	int length = word->length;

	_charCount+= length;

	// put the word into the grid
	int yend = ystart + length;
	const char *pWord = word->word;
	for(int y=ystart;y<yend;y++)
	{
		PutLetterFlipper(*pWord,xstart,y,ST_VERTICAL);
		AdjustFreeColumns(y,xstart);
		++pWord;
	}
	AdjustFreeRows(xstart,yend-1);
	if(ystart>0)
		PutBlockChar(xstart,ystart-1,ST_VERTICAL);
	if(yend<ROWS)
		PutBlockChar(xstart,yend,ST_VERTICAL);
}

// insert a word at a specific position, using the flipper square
void Grid::InsertWordWithFlipper(int poolIdx,int x,int y,bool horizontalDir)
{
	if(horizontalDir)
		InsertWordHorizWithFlipper(poolIdx,x,y);
	else
		InsertWordVerticWithFlipper(poolIdx,x,y);
	if(_firstIncompleteWordValid && _firstIncompleteWord.x <0)
	{
		int length = WordPool::GetPoolWord(poolIdx)->length;
		if(horizontalDir)
			CheckIncompleteAfterHorizInsert(x,y,length);
		else
			CheckIncompleteAfterVerticInsert(x,y,length);
	}
	else _firstIncompleteWordValid=false;
}

// try to insert a word into the grid horizontally at (xstart,ystart)
void Grid::InsertWordHoriz(int poolIdx,int xstart,int ystart)
{
	const Word *word=WordPool::GetPoolWord(poolIdx);

#ifdef _DEBUG
	// does the the word match?
	if(!DoesWordFitHoriz(word,xstart,ystart))
		Error("InsertWordHoriz, word does not fit");
#endif

	// get the word out of the word pool
	int length = word->length ;
	_charCount+= length;

	// put the characters into the grid
	int xend=xstart + length;
	const char *pWord = word->word;
	for(int x=xstart;x<xend;x++)
	{
		PutLetter(*pWord,x,ystart,ST_HORIZONTAL);
		AdjustFreeRows(x,ystart);
		++pWord;
	}
	AdjustFreeColumns(ystart,xend-1);

	// word start/end by blocking character
	if(xstart>0)
		PutBlockChar(xstart-1,ystart,ST_HORIZONTAL);
	if(xend<COLUMNS)
		PutBlockChar(xend,ystart,ST_HORIZONTAL);
}


// try to insert a word into the grid vertically at (xstart,ystart)
void Grid::InsertWordVertic(int poolIdx,int xstart,int ystart)
{
	// get the word out of the word pool
	const Word *word=WordPool::GetPoolWord(poolIdx);

#ifdef _DEBUG
	// does the word match the grid?
	if(!DoesWordFitVertic(word,xstart,ystart))
		Error("InsertWordVertic, word does not fit");
#endif

	int length = word->length;

	_charCount+= length;

	// put the word into the grid
	int yend = ystart + length;
	const char *pWord = word->word;
	for(int y=ystart;y<yend;y++)
	{
		PutLetter(*pWord,xstart,y,ST_VERTICAL);
		AdjustFreeColumns(y,xstart);
		++pWord;
	}
	AdjustFreeRows(xstart,yend-1);
	if(ystart>0)
		PutBlockChar(xstart,ystart-1,ST_VERTICAL);
	if(yend<ROWS)
		PutBlockChar(xstart,yend,ST_VERTICAL);
}

int Grid::GetCharPattern(int xStart,int yStart,bool horizontalDir,char *pattern) const
{
	if(horizontalDir)
		return GetCharPatternHoriz(xStart,yStart,pattern);
	else
		return GetCharPatternVertic(xStart,yStart,pattern);
}

int Grid::GetCharPatternHoriz(int xStart,int yStart,char *pattern) const
{
	int length=0;
	int x=xStart;
	char c;

	if(_cellState[xStart][yStart] & ST_HORIZONTAL)
		return 0;
	while(length<MAXWORDLENGTH && x<COLUMNS && (c=_cells[x][yStart])!=BLOCK_CHAR)
	{
		pattern[length]=c;
		++x;
		++length;
	}
	return length;
}

int Grid::GetCharPatternVertic(int xStart,int yStart,char *pattern) const
{
	int length=0;
	int y=yStart;
	char c;

	if(_cellState[xStart][yStart] & ST_VERTICAL)
		return 0;
	while(length<MAXWORDLENGTH && y<ROWS && (c=_cells[xStart][y])!=BLOCK_CHAR)
	{
		pattern[length]=c;
		++y;
		++length;
	}
	return length;
}


// insert a word at a specific position (must fit!)
void Grid::InsertWord(int poolIdx,int x,int y,bool horizontalDir)
{
	if(horizontalDir)
		InsertWordHoriz(poolIdx,x,y);
	else
		InsertWordVertic(poolIdx,x,y);
	if(_firstIncompleteWordValid && _firstIncompleteWord.x <0)
	{
		int length = WordPool::GetPoolWord(poolIdx)->length;
		if(horizontalDir)
			CheckIncompleteAfterHorizInsert(x,y,length);
		else
			CheckIncompleteAfterVerticInsert(x,y,length);
	}
	else _firstIncompleteWordValid=false;
}

void Grid::RemoveWordHoriz(int x,int y,char *word)
{
	// extract word characters, and remove them
	char c;
	register char *pWord = word;
	int xl = x;

	while(xl<COLUMNS && (c=_cells[xl][y])!=BLOCK_CHAR)
	{
		*pWord=c;
		RemoveLetter(xl,y,ST_HORIZONTAL);
		assert(xl-x<MAXWORDLENGTH);
		++xl;
		++pWord;
	}
	*pWord=0;
	if(x>0)
	{
		assert(_cells[x-1][y]==BLOCK_CHAR);
		RemoveBlockChar(x-1,y,ST_HORIZONTAL);
	}
	if(xl<COLUMNS)
	{
		assert(_cells[xl][y]==BLOCK_CHAR);
		RemoveBlockChar(xl,y,ST_HORIZONTAL);
	}
	_charCount-=xl-x;

	// adjusting of _firstFreeColumnEdge/_firstFreeRowEdge is omitted
}

void Grid::RemoveWordVertic(int x,int y,char *word)
{
	// extract word characters, and remove them
	char c;
	register char *pWord = word;
	int yl = y;
	while(yl<ROWS &&(c=_cells[x][yl])!=BLOCK_CHAR)
	{
		*pWord=c;
		RemoveLetter(x,yl,ST_VERTICAL);
		assert(yl-y<MAXWORDLENGTH);
		++yl;
		++pWord;
	}
	*pWord=0;
	if(y>0)
	{
		assert(_cells[x][y-1]==BLOCK_CHAR);
		RemoveBlockChar(x,y-1,ST_VERTICAL);
	}
	if(yl<ROWS)
	{
		assert(_cells[x][yl]==BLOCK_CHAR);
		RemoveBlockChar(x,yl,ST_VERTICAL);
	}
	_charCount-=yl-y;

	// adjusting of _firstFreeColumnEdge/_firstFreeRowEdge is omitted
}


// remove word starting at x,y in horizontal or vertical direction
// (very slow, since this class is optimized for inserting and copying, but not for removal)
void Grid::RemoveWord(int x,int y,bool horizontalDir)
{
	char word[MAXWORDLENGTH+1];
	
	if(horizontalDir)
		RemoveWordHoriz(x,y,word);
	else
		RemoveWordVertic(x,y,word);
	
	_firstIncompleteWordValid=false;

	// clear the "blocked" state for all cells that are not used in both directions any more
	UnblockPossibleCells();
}

// Test if there are any words that can be inserted at (x,y); if not, block the cell
void Grid::ResetBlockedState(int x,int y)
{
	UBYTE cellState = _cellState[x][y];
	if((cellState & ST_BLOCKED)!=0)
		return;

	char cellChar = _cells[x][y];
	if(!isLetter(cellChar))
		return;
	
	bool horizontalDir;
	if((cellState & ST_VERTICAL)==0)
		horizontalDir = false;
	else if((cellState & ST_HORIZONTAL)==0)
		horizontalDir = true;
	else 
		Error("unexpected cell state");

	char cellAfter=0;
	
	if(horizontalDir)
	{
		if(x<COLUMNS-1)
		{
			cellAfter = _cells[x+1][y];
			if(!isLetter(cellAfter))
				cellAfter = 0;
		}
	}
	else 
	{
		if(y<ROWS-1)
		{
			cellAfter = _cells[x][y+1];
			if(!isLetter(cellAfter))
				cellAfter = 0;
		}
	}

	int xstart,ystart,poolIdx,charPos;

	// process words containing cellChar
	bool found = false;
	WordIndexVector &words = WordPool::GetWordsPer12Chars(cellChar,cellAfter);
	const WordCharPosPair *pWordsEnd = &(*words.end());
	for(const WordCharPosPair *itWord = &(*words.begin()); itWord!= pWordsEnd; ++itWord)
	{
		poolIdx=itWord->poolIdx;
		charPos=itWord->charPos;   // position where cellChar occurs
		
		const Word *word = WordPool::GetPoolWord(poolIdx);
		assert(charPos >=0 && charPos<word->length);
		assert(word->word[charPos]==cellChar);

		// if there is a word crossing "(x,y)": the cell cannot be blocked
		if(horizontalDir)
		{
			xstart = x-charPos;
			ystart = y;
			if(DoesWordFitHoriz(word,xstart,ystart ))
				return;
		}
		else
		{
			xstart = x;
			ystart = y-charPos;
			if(DoesWordFitVertic(word,xstart,ystart))
				return;
		}
	}

	BlockCell(x,y);
}


// **********************************************************************


bool Grid::DoCharsMatchHoriz (const Word &word,int xstart,int ystart) const
{
	int length = word.length;

	// (1) first try whether the word fits into the grid by its size
	if(xstart<0 || ystart<0 || ystart>=ROWS || xstart+length > COLUMNS)
		return false;

	// (2) now check if the word matches the other characters in the grid
	const char *pWord=word.word;
	const char *pCellStart = &_cells[xstart][ystart];
	const char *pCell = pCellStart;
	const char *pCellEnd = pCell + ROWS*length;
	register char c;
	
	while(pCell!=pCellEnd)
	{
		c = *pCell;
		if(c != ' ' && c != *pWord)  // speed enhanced 
			return false;
		++pWord;
		pCell+=ROWS;  // goto next column
	}
	if(xstart>0)
	{
		pCellStart-=ROWS;
		c= *pCellStart;
		if(c != ' ' && c != BLOCK_CHAR)
			return false;
	}
	if(xstart+length<COLUMNS)
	{
		c= *pCellEnd;
		if(c != ' ' && c != BLOCK_CHAR)
			return false;
	}

	return true;
}

bool Grid::DoCharsMatchVertic(const Word &word,int xstart,int ystart) const
{
	int length = word.length;

	// (1) first try whether the word fits into the grid or not
	if (xstart<0 || xstart>=COLUMNS || ystart<0 || ystart+length>ROWS)
		return false;

	// (2) now check if the word matches the other characters in the grid
	const char *pWord=word.word;
	const char *pCellStart = &_cells[xstart][ystart];
	const char *pCell = pCellStart;
	const char *pCellEnd = pCell + length;
	register char c;

	while(pCell != pCellEnd)
	{
		c = *pCell;
		if(c != ' ' && c != *pWord)  // speed enhanced 
			return false;
		++pWord;
		++pCell;  // goto next row
	}
	if(ystart>0)
	{
		--pCellStart;
		c= *pCellStart;
		if(c != ' ' && c != BLOCK_CHAR) 
			return false;
	}
	if(ystart+length<ROWS)
	{
		c= *pCellEnd;
		if(c != ' ' && c != BLOCK_CHAR) 
			return false;
	}

	return true;
}


// test if the characters of a word match a specific position in the grid
// with exactly 1 miss
bool Grid::DoCharsMatchHoriz1Miss (const Word &word,int xstart,int ystart) const
{
	int length = word.length;

	// try whether the word fits into the grid by its size
	if(xstart<0 || ystart<0 || ystart>=ROWS || xstart+length > COLUMNS)
		return false;

	// count non-matches; stop when count reaches 2
	const char *pWord=word.word;
	const char *pCellStart = &_cells[xstart][ystart];
	const char *pCell = pCellStart;
	const char *pCellEnd = pCell + ROWS*length;
	register char c;
	int missCount=0;
	
	while(pCell!=pCellEnd)
	{
		c = *pCell;
		if(c == BLOCK_CHAR)
			return false;
		if(c != ' ' && c != *pWord)  // speed enhanced 
		{
			++missCount;
			if(missCount>1)
				return false;
		}
		++pWord;
		pCell+=ROWS;  // goto next column
	}
	if(missCount!=1)
		return false;
	if(xstart>0)
	{
		pCellStart-=ROWS;
		c= *pCellStart;
		if(c != ' ' && c != BLOCK_CHAR)
			return false;
	}
	if(xstart+length<COLUMNS)
	{
		c= *pCellEnd;
		if(c != ' ' && c != BLOCK_CHAR)
			return false;
	}

	return true;
}


// test if the characters of a word match a specific position in the grid
// with exactly 1 miss
bool Grid::DoCharsMatchVertic1Miss(const Word &word,int xstart,int ystart) const
{
	int length = word.length;

	// (1) first try whether the word fits into the grid or not
	if (xstart<0 || xstart>=COLUMNS || ystart<0 || ystart+length>ROWS)
		return false;

	// (2) now check if the word matches the other characters in the grid
	const char *pWord=word.word;
	const char *pCellStart = &_cells[xstart][ystart];
	const char *pCell = pCellStart;
	const char *pCellEnd = pCell + length;
	register char c;
	int missCount=0;

	while(pCell != pCellEnd)
	{
		c = *pCell;
		if(c == BLOCK_CHAR)
			return false;
		if(c != ' ' && c != *pWord)
		{
			++missCount;
			if(missCount>1)
				return false;
		}
		++pWord;
		++pCell;  // goto next row
	}
	if(missCount!=1)
		return false;
	if(ystart>0)
	{
		--pCellStart;
		c= *pCellStart;
		if(c != ' ' && c != BLOCK_CHAR) 
			return false;
	}
	if(ystart+length<ROWS)
	{
		c= *pCellEnd;
		if(c != ' ' && c != BLOCK_CHAR) 
			return false;
	}

	return true;
}


// Test if adding a character at the given position will yield an incomplete
// word in vertical direction and, if so, if there is a chance to complete it.
// returns true, if there is no incomplete word, or if there is another
// fitting word in the pool for this position
bool Grid::IsCompletableVertic(char c,int x,int y) const
{
	if(_cells[x][y] != ' ' && (_cellState[x][y]&ST_VERTICAL)!=0)
		return true;  // there is already a vertical word there
	
	// because of the possible flipper square, test the assertion not earlier
	assert(_cells[x][y]==c || _cells[x][y]==' ');

	char cBefore,cAfter;
	GetNeighboursVertic(x,y,cBefore,cAfter);
	if(cBefore == 0 && cAfter == 0)
		return true; // no incomplete word

	if(AreNeighboursBlockedVertic(x,y))
		return false;

	const WordIndexVector *wiVec;
	int ystart=y;
	if(cBefore!=0)
		--ystart;
	wiVec = &WordPool::GetWordsPer123Chars(cBefore,c,cAfter);

	// speed improvement by restricting the starting column
	int firstRow = FindStarterRow(x,y);

	// test if any of the words may fit
	int poolIdx,y2;
	// using pointers is faster for unoptimized code
	const WordCharPosPair *wiVecEnd = &(*wiVec->end());
	for(const WordCharPosPair* it = &(*wiVec->begin()); it!= wiVecEnd; ++it)
	{
		poolIdx = it->poolIdx;
		y2 = ystart - it->charPos;
		if(y2<firstRow)
			continue;

		if(DoCharsMatchVertic(*WordPool::GetPoolWord(poolIdx),x,y2))
			return true; // we found a matching word: that's a solution
	}

	return false;
}


// Test if adding a character at the given position will yield an incomplete
// word in horizontal direction and, if so, if there is a chance to complete it.
// returns true, if there is no incomplete word, or if there is another
// fitting word in the pool for this position
bool Grid::IsCompletableHoriz(char c,int x,int y) const
{
	if(_cells[x][y] != ' ' && (_cellState[x][y]&ST_HORIZONTAL)!=0)
		return true;  // there is already a horizontal word there

	assert(_cells[x][y]==c || _cells[x][y]==' ');
	
	char cBefore,cAfter;
	GetNeighboursHoriz(x,y,cBefore,cAfter);
	if(cBefore == 0 && cAfter == 0)
		return true; // no incomplete word

	if(AreNeighboursBlockedHoriz(x,y))
		return false;

	const WordIndexVector *wiVec;
	int xstart = x;
	if(cBefore!=0)
		xstart--;
	wiVec = &WordPool::GetWordsPer123Chars(cBefore,c,cAfter);

	// speed improvement by restricting the starting column
	int firstCol = FindStarterColumn(x,y);

	// test if any of the words may fit
	int poolIdx,x2;
	// using pointers is faster for unoptimized code
	const WordCharPosPair *wiVecEnd = &(*wiVec->end());
	for(const WordCharPosPair* it = &(*wiVec->begin()); it!= wiVecEnd; ++it)
	{
		poolIdx = it->poolIdx;
		x2 = xstart - it->charPos;
		if(x2<firstCol)  // speed enhancement
			continue;

		if(DoCharsMatchHoriz(*WordPool::GetPoolWord(poolIdx),x2,y))
			return true; // we found a matching word: that's a solution
	}

	return false;
}


// **********************************************************************

void Grid::CheckIncompleteAfterHorizInsert(int xStart,int yStart,int length)
{
	// check for incompleteness after a horizontal insert

	register int x,y,xEnd;

	xEnd=xStart+length;
	for(x=xStart; x<xEnd; ++x)
	{
		if(yStart>0)
		{
			y=yStart-1;
			if(isLetter(_cells[x][y]) && (_cellState[x][y] & ST_VERTICAL)==0)
			{
				_firstIncompleteWord.x=x;
				_firstIncompleteWord.y=y;
				_firstIncompleteWord.horizontal=false;
				_firstIncompleteWordValid=true;
				return;
			}
		}
		if(yStart<ROWS-1)
		{
			y=yStart+1;
			if(isLetter(_cells[x][y]) && (_cellState[x][y] & ST_VERTICAL)==0)
			{
				_firstIncompleteWord.x=x;
				_firstIncompleteWord.y=y-1;
				_firstIncompleteWord.horizontal=false;
				_firstIncompleteWordValid=true;
				return;
			}
		}
	}
	_firstIncompleteWord.x=-1;
	_firstIncompleteWord.y=-1;
	_firstIncompleteWordValid=true;
}

// check for incompleteness after a vertical insert
// remember result in _firstIncompleteWord
void Grid::CheckIncompleteAfterVerticInsert(int xStart,int yStart,int length)
{
	register int x,y,yEnd;

	yEnd=yStart+length;

	for(y=yStart; y<yEnd; ++y)
	{
		if(xStart>0)
		{
			x=xStart-1;
			if(isLetter(_cells[x][y]) && (_cellState[x][y] & ST_HORIZONTAL)==0)
			{
				_firstIncompleteWord.x=x;
				_firstIncompleteWord.y=y;
				_firstIncompleteWord.horizontal=true;
				_firstIncompleteWordValid=true;
				return;
			}
		}
		if(xStart<COLUMNS-1)
		{
			x=xStart+1;
			if(isLetter(_cells[x][y]) && (_cellState[x][y] & ST_HORIZONTAL)==0)
			{
				_firstIncompleteWord.x=x-1;
				_firstIncompleteWord.y=y;
				_firstIncompleteWord.horizontal=true;
				_firstIncompleteWordValid=true;
				return;
			}
		}
	}
	_firstIncompleteWord.x=-1;
	_firstIncompleteWord.y=-1;
	_firstIncompleteWordValid=true;
}


// look for any incomplete word in horizontal direction
bool Grid::FindIncompleteWordPosHoriz(int &xResult,int &yResult) const
{
	register int x,y;
	register char cell1, cell2;
	register const char *pCell;
	
	for(y=0;y<ROWS;++y)
	{
		pCell = &_cells[0][y];
		for(x=0;x<COLUMNS-1;++x)
		{
			// is there a two letter sequence with no horizontal crossing?
			cell1=*pCell;
			if(isLetter(cell1))
			{
				cell2=*(pCell+ROWS);
				if(isLetter(cell2))
				{ 
					if((_cellState[x][y] & ST_HORIZONTAL)==0)
					{
						xResult=x;
						yResult=y;
						return true;
					}
					else
					{
						// there is already a horizontal word: go to the end
						pCell+=ROWS;
						++x;
						do
						{
							pCell+=ROWS;
							++x;
						} while(x<COLUMNS-1 && *pCell!=BLOCK_CHAR);
					}
				}
				else
				{
					pCell+=ROWS;
					++x;
				}
			}
			pCell+=ROWS;
		}
	}
	return false;
}

// look for any incomplete word in vertical direction
bool Grid::FindIncompleteWordPosVertic(int &xResult,int &yResult) const
{
	register int x,y;
	register char cell1, cell2;
	register const char *pCell;
	
	for(x=0;x<COLUMNS;++x)
	{
		pCell =  &_cells[x][0];
		for(y=0;y<ROWS-1;++y)
		{
			// is there a two letter sequence with no vertical crossing?
			cell1=*pCell;
			if(isLetter(cell1))
			{
				cell2=*(pCell+1);
				if(isLetter(cell2))
				{
					if((_cellState[x][y] & ST_VERTICAL)==0)
					{
						xResult=x;
						yResult=y;
						return true;
					}
					else
					{
						// there is already a vertical word: go to the end
						++pCell;
						++y;
						do
						{
							++pCell;
							++y;
						} while(y<ROWS-1 && *pCell!=BLOCK_CHAR);
					}
				}
				else
				{
					++pCell;
					++y;
				}
			}
			++pCell;
		}
	}
	return false;
}


// test if a grid contains incomplete words and if so, return the first found position
bool Grid::FindIncompleteWordPos(InsertPosition &insPos) 
{
	int x,y;
	if(!_firstIncompleteWordValid)
	{
		if(FindIncompleteWordPosHoriz(x,y))
		{
			_firstIncompleteWord.x = x;
			_firstIncompleteWord.y = y;
			_firstIncompleteWord.horizontal = true;
		}
		else if(FindIncompleteWordPosVertic(x,y))
		{
			_firstIncompleteWord.x = x;
			_firstIncompleteWord.y = y;
			_firstIncompleteWord.horizontal = false;
		}
		else
		{
			_firstIncompleteWord.x = -1;
			_firstIncompleteWord.y = -1;
		}
		_firstIncompleteWordValid=true;
	}

	if(_firstIncompleteWord.x>=0)
	{
		insPos = _firstIncompleteWord;
		return true;
	}
	else return false;
}

// **********************************************************************
bool Grid::DoesWordFitHoriz(const Word *word,int xstart,int ystart) 
{
	// (1) make sure there is no word in horizontal direction starting there
	// (testing the direction of the first character should be sufficient,
	// otherwise the next test will fail)
	if(_cellState[xstart][ystart]&ST_HORIZONTAL)
		return false;

	// (2) test if the characters match
	if(!DoCharsMatchHoriz(*word,xstart,ystart))
		return false;

	// (3) now check the neighbour characters above and below if there
	//     are words in the pool that might fit to them
	int xend = xstart + word->length;
	register const char *pWord=word->word;
	for(register int x=xstart;x<xend;x++)
	{
		// test if adding a character at the given position will yield an incomplete
		// word and, if so, if there is a chance to complete it
		if(!IsCompletableVertic(*pWord, x, ystart))
			return false;
		++pWord;
	}

	return true;
}


// try to insert a word into the grid vertically at (xstart,ystart)
bool Grid::DoesWordFitVertic(const Word *word,int xstart,int ystart)
{
	// (1) make sure the word is not already there 
	// (testing the direction of the first character should be sufficient)
	if(_cellState[xstart][ystart] & ST_VERTICAL)
		return false;

	// (2) test if the characters match
	if(!DoCharsMatchVertic(*word,xstart,ystart))
		return false;

	// (3) now check the neighbour characters left and right if there
	//     are words in the pool that might fit to them
	int yend = ystart + word->length;	
	register const char *pWord = word->word;
	for(register int y=ystart;y<yend;y++)
	{
		// test if adding a character at the given position will yield an incomplete
		// word and, if so, if there is a chance to complete it
		if(!IsCompletableHoriz(*pWord,xstart,y))
			return false;
		++pWord;
	}

	return true;
}

bool Grid::DoesWordFit(int poolIdx,int x, int y,bool horizontalDir)
{
	const Word *word = WordPool::GetPoolWord(poolIdx);
	if(horizontalDir)
		return DoesWordFitHoriz(word,x,y);
	else
		return DoesWordFitVertic(word,x,y);
}


bool Grid::DoesWordFitHorizFlipper(const Word *word,int xstart,int ystart) 
{
	// (1) make sure there is no word in horizontal direction starting there
	// (testing the direction of the first character should be sufficient,
	// otherwise the next test will fail)
	if(_cellState[xstart][ystart]&ST_HORIZONTAL)
		return false;

	// (2) test if the characters match
	if(!DoCharsMatchHoriz1Miss(*word,xstart,ystart))
		return false;

	// (3) now check the neighbour characters above and below if there
	//     are words in the pool that might fit to them
	int xend = xstart + word->length;
	register const char *pWord=word->word;
	for(register int x=xstart;x<xend;x++)
	{
		// test if adding a character at the given position will yield an incomplete
		// word and, if so, if there is a chance to complete it
		if(!IsCompletableVertic(*pWord, x, ystart))
			return false;
		++pWord;
	}

	return true;
}


// try to insert a word into the grid vertically at (xstart,ystart)
bool Grid::DoesWordFitVerticFlipper(const Word *word,int xstart,int ystart)
{
	// (1) make sure the word is not already there 
	// (testing the direction of the first character should be sufficient)
	if(_cellState[xstart][ystart] & ST_VERTICAL)
		return false;

	// (2) test if the characters match
	if(!DoCharsMatchVertic1Miss(*word,xstart,ystart))
		return false;

	// (3) now check the neighbour characters left and right if there
	//     are words in the pool that might fit to them
	int yend = ystart + word->length;	
	register const char *pWord = word->word;
	for(register int y=ystart;y<yend;y++)
	{
		// test if adding a character at the given position will yield an incomplete
		// word and, if so, if there is a chance to complete it
		if(!IsCompletableHoriz(*pWord,xstart,y))
			return false;
		++pWord;
	}

	return true;
}

bool Grid::DoesWordFit1Miss(int poolIdx,int x, int y,bool horizontalDir)
{
	const Word *word = WordPool::GetPoolWord(poolIdx);
	if(horizontalDir)
		return DoesWordFitHorizFlipper(word,x,y);
	else
		return DoesWordFitVerticFlipper(word,x,y);
}


// helper struct
struct PosPair
{
	char x,y;
};


// try to insert a new element into the PosPair queue
void InsertNextPosPair(PosPair posQueue[], char cells[COLUMNS][ROWS],int x,int y, int &queueSize)
{
	if(!isLetter(cells[x][y]))
		return;
	cells[x][y]='.';  // no letter any more
	assert(queueSize < COLUMNS*ROWS);
	posQueue[queueSize].x=x;
	posQueue[queueSize].y=y;
	++queueSize;
}

// helper function to "flood fill" a grid area with ".", starting from point (x,y)
void FloodFill(char cells[COLUMNS][ROWS],int x,int y)
{
	PosPair posQueue[COLUMNS*ROWS];  // enough elements for all cells
	int queueSize = 0;
	PosPair p;

	InsertNextPosPair(posQueue,cells,x,y,queueSize);

	PosPair *nextElement = posQueue;
	while(nextElement < posQueue + queueSize)
	{
		// take one element out of the queue, insert all free neighbours into
		p = *nextElement;
		++nextElement;
		if(p.x>0) InsertNextPosPair(posQueue,cells,p.x-1,p.y,queueSize);
		if(p.x<COLUMNS-1) InsertNextPosPair(posQueue,cells,p.x+1,p.y,queueSize);
		if(p.y>0) InsertNextPosPair(posQueue,cells,p.x,p.y-1,queueSize);
		if(p.y<ROWS-1) InsertNextPosPair(posQueue,cells,p.x,p.y+1,queueSize);
	}
}


// test if the words are connected (needed after removal)
bool Grid::IsConnected() const
{
	char cells[COLUMNS][ROWS];
	
	// first, make a copy of all cells
	memcpy(cells,_cells,COLUMNS*ROWS*sizeof(char));

	int count=0;
	for(int x=0;x<COLUMNS;++x)
	{
		for(int y=0;y<ROWS;++y)
		{
			if(isLetter(cells[x][y]))
			{
				++count;     // count number of connected areas
				if(count>1)  // if there is more than one area, the grid is not connected
					return false;
				FloodFill(cells,x,y);
			}
		}
	}
	return true;
}



// *********************************************************************


// calculate the score one can gain at all when inserting this word
int Grid::ExpectedScoreAfterInsert(int poolIdx,int x,int y,bool horizontalDir) const
{
	int length = WordPool::GetWordLength(poolIdx);
	int charcount = _charCount+length;

	// calculate the new values for the emptyCells counters
	register int emptyCellsHoriz = _emptyCellsHoriz;
	register int emptyCellsVertic = _emptyCellsVertic;
	register int i;
	int iStart,iEnd;
	register int freeRowCol,newFreeRowCol;

	if(horizontalDir)
	{
		iStart= ((x>0)?-1:0);
		iEnd= ((x+length < COLUMNS) ?length+1:length);
		for(i=iStart;i<iEnd;++i)
		{
			freeRowCol = _firstFreeRowEdge[i+x];
			newFreeRowCol = y+2;
			if(i<0 || i>length-1)
				newFreeRowCol--;
			if(newFreeRowCol>ROWS)
				newFreeRowCol= ROWS;
			if(freeRowCol < newFreeRowCol)
				emptyCellsVertic -= (newFreeRowCol - freeRowCol);
		}

		iStart= ((y>0)?-1:0);
		iEnd=   ((y< ROWS-1) ? 2:1);
		for(i=iStart;i<iEnd;++i)
		{
			freeRowCol = _firstFreeColumnEdge[y+i];
			newFreeRowCol = x+length+1;
			if(i<0 || i>0)
				newFreeRowCol--;
			if(newFreeRowCol>COLUMNS)
				newFreeRowCol= COLUMNS;
			if( freeRowCol < newFreeRowCol)
				emptyCellsHoriz -= newFreeRowCol - freeRowCol;
		}
	}
	else
	{
		iStart= ((y>0)?-1:0);
		iEnd= ((y+length < ROWS) ?length+1:length);

		for(i=iStart;i<iEnd;++i)
		{
			freeRowCol = _firstFreeColumnEdge[i+y];
			newFreeRowCol = x+2;
			if(i<0 || i>length-1)
				newFreeRowCol--;
			if(newFreeRowCol>COLUMNS)
				newFreeRowCol= COLUMNS;
			if(freeRowCol<newFreeRowCol)
				emptyCellsHoriz -= (newFreeRowCol - freeRowCol);
		}

		iStart= ((x>0)?-1:0);
		iEnd=   ((x< COLUMNS-1) ? 2:1);
		for(i=iStart;i<iEnd;++i)
		{
			freeRowCol = _firstFreeRowEdge[x+i];
			newFreeRowCol = y+length+1;
			if(i<0 || i>0)
				newFreeRowCol--;
			if(newFreeRowCol>ROWS)
				newFreeRowCol= ROWS;
			if(freeRowCol < newFreeRowCol)
				emptyCellsVertic -= newFreeRowCol - freeRowCol;
		}
	}

	int emptyCells = emptyCellsHoriz+emptyCellsVertic;
	return charcount + emptyCells * charcount*COVERAGE/(2*ROWS*COLUMNS-emptyCells )/100;
}

// **********************************************************************


// put the cross word grid into the output stream
ostream& operator<< (ostream &os,const Grid &grid)
{
	int x,y;
	char c;

	for(y=0;y<ROWS;y++){
		for(x=0;x<COLUMNS;x++){
			c=grid.GetCell(x,y);
			if(c==' ' || c==BLOCK_CHAR )
				os << '_';
			else
				os << c ;
		}

		os << '\n';
	}
	return os;
}



// commment before sending entry
//#define BENCHMARK

#ifndef BENCHMARK
	#define MAXLEVELSIZE 3000
	#define MINLEVELSIZE 700
	#define STARTLEVELSIZE 1500
#else
// for benchmarking purposes, use these values
	#define LEVELSIZE 500
	#define MAXLEVELSIZE LEVELSIZE
	#define MINLEVELSIZE LEVELSIZE
	#define STARTLEVELSIZE LEVELSIZE
#endif

#define MAXSIBLINGS 200
#define LEVELSIZESTEP 100
#define LOWERSCOREGRIDS 15
int Solver::_LevelSize;


// when the estimated time is below LOWERTIMELIMIT,
// the levelsize is increase; if it is over UPPER_TIMELIMIT,
// the levelsize is decreased.
#define LOWER_TIMELIMIT 52
#define UPPER_TIMELIMIT 55
#define MAXUPPER_TIMELIMIT 58

// make a list of all potential starting grids
// idea: start with all words in the upper left corner
// horizontally of vertically
// returns: vector of grids,
void Solver::FindInitialGrids(vector<Grid> &gridVec)
{
	int i;
	int size = WordPool::GetPoolSize();
	
	for(i=0;i<size;++i)
	{
		Grid g1;
		g1.InsertWord(i,0,0,true);
		gridVec.push_back(g1);
//		g2.InsertWord(i,0,0,false);
//		gridVec.push_back(g2);
	}
}


// find the next grid level
// gridVec contains all interesting grids with n words,
// nextGridVec will contain all interesting grids with n+1 words
void Solver::FindNextGridLevel(vector<Grid> &gridVec,vector<Grid> &nextGridVec)
{
	int i;
	ULONG hash;
	// foreach grid
	int gvsize= (int)gridVec.size();
	InsertPosition insPos;
	register int x,y;

	PQScoredInsPos posQueue;
	for(i=0;i<gvsize;++i)
	{
		Grid &grid = gridVec[i];
		int maxSize = posQueue.Size()+MAXSIBLINGS;
		
		// if the grid is has incomplete words, create only missing words
		if(grid.FindIncompleteWordPos(insPos))
		{
			AddWordsThroughCell(grid,i,insPos.x,insPos.y,posQueue);
		}
		else // if there are no incomplete words, try to insert everything
		{
			// foreach non-empty cell: test if insertion would be possible
			register const char *pCell;
			for(x=0;x<COLUMNS;++x)
			{
				pCell = grid.GetPtrCell(x,0);
				int firstFreeRow = grid.GetFirstFreeRow(x);

				// unrolled loop 
#define ADDWORDS_ORSTOP \
				if(*(pCell++)>='A') AddWordsThroughCell(grid,i,x, y,posQueue); \
				if(posQueue.Size()>maxSize) break; \
				++y;

				y=0;
				switch(firstFreeRow)
				{
					case 16: ADDWORDS_ORSTOP
					case 15: ADDWORDS_ORSTOP
					case 14: ADDWORDS_ORSTOP
					case 13: ADDWORDS_ORSTOP
					case 12: ADDWORDS_ORSTOP
					case 11: ADDWORDS_ORSTOP
					case 10: ADDWORDS_ORSTOP
					case 9: ADDWORDS_ORSTOP
					case 8: ADDWORDS_ORSTOP
					case 7: ADDWORDS_ORSTOP
					case 6: ADDWORDS_ORSTOP
					case 5: ADDWORDS_ORSTOP
					case 4: ADDWORDS_ORSTOP
					case 3: ADDWORDS_ORSTOP
					case 2: ADDWORDS_ORSTOP
					case 1: ADDWORDS_ORSTOP
					default: ;
				}
				if(posQueue.Size()>maxSize) break;
			}
#ifndef BENCHMARK
			if(ClockSec()>MAXUPPER_TIMELIMIT)
				return;
#endif
		}
	}
	if(DebugMode)
	{
		cerr << "Level size: " << posQueue.Size() << endl;
#ifdef XXX
		if(posQueue.Size()==0)
		{
			for(i=0;i<gvsize;++i)
			{
				cerr << i << ":\n" << gridVec[i] << endl;
				cerr << "Score="<< gridVec[i].Score() << endl << endl;
			}
		}
#endif
	}

	// find top _LevelSize insert positions and apply them to the current grid
	nextGridVec.reserve(MAXLEVELSIZE);
	//set<ULONG> gridHashes;  // hash codes of the already accepted grids
	Hashtable gridHashes(4*_LevelSize);
	int lastscore;
	while((int)nextGridVec.size() < _LevelSize)
	{
		const ScoredInsPos *scInsPos = posQueue.Top();
		if(scInsPos==NULL)  // stop if there no more elements in the queue
			break;
		if(!gridVec[scInsPos->gridIdx].DoesWordFit(scInsPos->poolIdx,scInsPos->x,scInsPos->y,scInsPos->horizontal))
		{
			posQueue.Pop();
			continue; // possible when later tested words block new cells
		}
		
		// for greater diversity: make sure the last X grids will have different scores
		if(nextGridVec.size() == _LevelSize-LOWERSCOREGRIDS)
			lastscore = scInsPos->score;
		else if((int)nextGridVec.size()>_LevelSize-LOWERSCOREGRIDS)
		{
			if(scInsPos->score==lastscore)
			{
				posQueue.Pop();
				continue; 
			}
			else
				lastscore=scInsPos->score;
		}

		nextGridVec.push_back(gridVec[scInsPos->gridIdx]); // make a copy!
		Grid &grid = nextGridVec.back();

#ifdef _DEBUG
		int score = grid.ScoreAfterInsert(scInsPos->poolIdx,scInsPos->x,scInsPos->y,scInsPos->horizontal);
		int expectedScore = grid.ExpectedScoreAfterInsert(scInsPos->poolIdx,scInsPos->x,scInsPos->y,scInsPos->horizontal);
#endif

		grid.InsertWord(scInsPos->poolIdx,scInsPos->x,scInsPos->y,scInsPos->horizontal);

#ifdef _DEBUG
		assert(score == grid.Score());
		assert(expectedScore == grid.ExpectedScore());
#endif

		// test if the grid hash code is already there; if not, accept the grid, else search for it
		hash = grid.HashCode();
		if(!gridHashes.Test(hash))
		{
			gridHashes.Insert(hash); // keep the new grid
		}
		else nextGridVec.pop_back();  // do not keep the grid

		posQueue.Pop();
	}
	
	if(DebugMode)
	{
		cerr << (int)nextGridVec.size() << " new grids constructed\n";
	}
}

// construct possible insert positions (crossing through one cell) and calculate their scores 
void Solver::AddWordsThroughCell(Grid &theGrid,int gridIdx, int x,int y, PQScoredInsPos &posQueue)
{
	State_e cellState = theGrid.GetCellState(x,y);
	if((cellState & ST_BLOCKED)!=0)
		return;

	char cellChar = theGrid.GetCell(x,y);
	assert(isLetter(cellChar));
	
	bool horizontalDir;
	if((cellState & ST_VERTICAL)==0)
		horizontalDir = false;
	else if((cellState & ST_HORIZONTAL)==0)
		horizontalDir = true;
	else 
		Error("unexpected cell state in Solver::AddWordsThroughCell");

	char cellAfter=0;
	
	int maxStartBefore;  // maximum number cells where a new word is checked
	if(horizontalDir)
	{
		if(x<COLUMNS-1)
		{
			cellAfter = theGrid.GetCell(x+1,y);
			if(!isLetter(cellAfter))
				cellAfter = 0;
		}
		maxStartBefore = theGrid.CountEmptyCellsBeforeHoriz(x,y);
	}
	else 
	{
		if(y<ROWS-1)
		{
			cellAfter = theGrid.GetCell(x,y+1);
			if(!isLetter(cellAfter))
				cellAfter = 0;
		}
		maxStartBefore = theGrid.CountEmptyCellsBeforeVertic(x,y);
	}

	int xstart,ystart,poolIdx,charPos;
	ScoredInsPos insPos;

	// process words containing cellChar
	bool found = false;
	WordIndexVector &words = WordPool::GetWordsPer12Chars(cellChar,cellAfter);
	const WordCharPosPair *pWordsEnd = &(*words.end());
	for(const WordCharPosPair *itWord = &(*words.begin()); itWord!= pWordsEnd; ++itWord)
	{
		poolIdx=itWord->poolIdx;
		charPos=itWord->charPos;   // position where cellChar occurs
		
		const Word *word = WordPool::GetPoolWord(poolIdx);
		assert(charPos >=0 && charPos<word->length);
		assert(word->word[charPos]==cellChar);

		if(horizontalDir)
		{
			xstart = x-charPos;
			ystart = y;
			if(!theGrid.DoesWordFitHoriz(word,xstart,ystart ))
				continue;
		}
		else
		{
			xstart = x;
			ystart = y-charPos;
			if(!theGrid.DoesWordFitVertic(word,xstart,ystart))
				continue;
		}
		
		// there is a word crossing "(x,y)": remember that
		found = true;
		// do not insert words that have been inserted by a previous call of AddWordsThroughCell
		if(charPos > maxStartBefore)  
			continue;

		insPos.x = (char)xstart;
		insPos.y = (char)ystart;
		insPos.poolIdx = poolIdx;
		insPos.horizontal = horizontalDir;
		insPos.gridIdx = gridIdx;
		
		// get the score, but do not insert the word into the grid
		insPos.score = theGrid.ExpectedScoreAfterInsert(poolIdx,xstart,ystart,horizontalDir);

		posQueue.Insert(insPos);
	}
	// do not test the same cell if not necessary 
	if(!found)
		theGrid.BlockCell(x,y);
}


// get all insert positions starting at (x,y) which may be possible with 1 non-matching character
void Solver::GetMatchingWordsWithFlipper(Grid &theGrid,int gridIdx, int xStart,int yStart, bool horizontalDir, vector<ScoredInsPos> &result)
{
	int x,y;
	ScoredInsPos insPos;

	int patternLength;
	char pattern[MAXWORDLENGTH];
	
	// get the characters in the grid up to the next BLOCK_CHAR
	patternLength = theGrid.GetCharPattern(xStart,yStart,horizontalDir,pattern);
	if(patternLength < 2)
		return;

	// the word has to reach the first character and can stop only at an empty space
	int minlength=0;
	while(minlength<patternLength && pattern[minlength]==' ')
		++minlength;
	if(minlength>=patternLength)  // stop if there are only spaces in the pattern
		return;
	while(minlength<patternLength && pattern[minlength]!=' ')
		++minlength;

	// process every word
	int nWords = WordPool::GetPoolSize();
	for(int i=0;i<nWords;++i)
	{
		const Word *word = WordPool::GetPoolWord(i);
		int length = word->length;
		if(length<minlength || length>patternLength)
			continue;

		// process every position between x-length+1 and x
		x=xStart;
		y=yStart;
		for(int count=0;count<length;++count)
		{
			if(theGrid.DoesWordFit1Miss(i,x,y,horizontalDir))
			{
				insPos.x = (char)x;
				insPos.y = (char)y;
				insPos.poolIdx = i;
				insPos.horizontal = horizontalDir;
				insPos.gridIdx = gridIdx;
				
				// get the score, but do not insert the word into the grid
				insPos.score = theGrid.ExpectedScoreAfterInsert(i,x,y,horizontalDir);
				result.push_back(insPos);
			}
			if(horizontalDir)
				++x;
			else
				++y;
		}
	}
}

void Solver::FindAllWordsWithFlipper(vector<Grid> &gridVec,vector<Grid> &nextGridVec)
{
	int i,x,y;

	vector<ScoredInsPos> insPosVec;
	insPosVec.reserve(100000);

	if(DebugMode)
	{
		cerr << "gridVec.size()=" << (int)gridVec.size() << "\n";
	}
	for(i=0;i<(int)gridVec.size();++i)
	{
		Grid &grid = gridVec[i];
		int maxsize=(int)insPosVec.size()+MAXSIBLINGS;

		for(x=0;x<COLUMNS;++x)
		{
			for(y=0;y<ROWS;++y)
			{
				GetMatchingWordsWithFlipper(grid,i, x,y, true, insPosVec);
				GetMatchingWordsWithFlipper(grid,i, x,y,false, insPosVec);
				if((int)insPosVec.size()>maxsize)
					break;
			}
			if((int)insPosVec.size()>maxsize)
				break;
#ifndef BENCHMARK
			if(ClockSec()>MAXUPPER_TIMELIMIT)
				return;
#endif
		}
	}
	if(DebugMode)
	{
		cerr << "insPosVec.size()=" << (int)insPosVec.size() << "\n";
	}

	for(i=0;i<(int)insPosVec.size();++i)
	{
		ScoredInsPos insPos = insPosVec[i];
		nextGridVec.push_back(gridVec[insPos.gridIdx]); // make a copy
		nextGridVec.back().InsertWordWithFlipper(insPos.poolIdx,insPos.x,insPos.y,insPos.horizontal);
	}
	if(DebugMode)
	{
		cerr << "algorithm restarted with " << (int)nextGridVec.size() << " grids\n\n";
	}
}

// fill the grid vector with all grids having one word less than the given grid
void Solver::AddAllGridsWithOneWordLess(const Grid &grid,vector<Grid> *gridVec)
{
	int x,y;
	for(x=0;x<COLUMNS;++x)
	{
		for(y=0;y<ROWS;++y)
		{
			for(int dir=0;dir<2;++dir)
			{
				if(grid.IsThereRemoveableWord(x,y,dir==0))
				{
					gridVec->push_back(grid); // make a copy!
					gridVec->back().RemoveWord(x,y,dir==0);
					if(!gridVec->back().IsConnected())
						gridVec->pop_back();
				}
			}
		}
	}
	if(DebugMode)
	{
		cerr << "algorithm restarted with " << (int)gridVec->size() << " grids\n\n";
	}
}

// find all positions where a word can be removed from the grid (without
// checking for connectedness)
void Solver::FindRemovePositions(const Grid &grid,vector<InsertPosition> &posVec)
{
	int x,y;
	InsertPosition insPos;
	for(x=0;x<COLUMNS;++x)
	{
		for(y=0;y<ROWS;++y)
		{
			for(int dir=0;dir<2;++dir)
			{
				if(grid.IsThereRemoveableWord(x,y,dir==0))
				{
					insPos.x = x;
					insPos.y = y;
					insPos.horizontal = (dir==0);
					posVec.push_back(insPos);
				}
			}
		}
	}
}

// fill the grid vector with all grids having two word fewer than the given grid
void Solver::AddAllGridsWithTwoWordLess(const Grid &grid,vector<Grid> *gridVec)
{
	vector<InsertPosition> posVec;
	posVec.reserve(ROWS*COLUMNS*2);

	FindRemovePositions(grid,posVec);

	int size = (int)posVec.size();
	for(int i=0;i<size;++i)
	{
		for(int j=i+1;j<size;++j)
		{
			gridVec->push_back(grid); // makes a copy!
			gridVec->back().RemoveWord(posVec[i].x,posVec[i].y,posVec[i].horizontal);
			gridVec->back().RemoveWord(posVec[j].x,posVec[j].y,posVec[j].horizontal);
			if(!gridVec->back().IsConnected())
				gridVec->pop_back();
		}
	}
	if(DebugMode)
	{
		cerr << "algorithm restarted with " << (int)gridVec->size() << " grids\n\n";
	}
}


Grid *Solver::FindBestGrid()
{
	vector<Grid> *gridVec = new vector<Grid>;
	vector<Grid> *nextGridVec = new vector<Grid>;
	vector<Grid> *tmpVec;
	InsertPosition tmp;

	_LevelSize = STARTLEVELSIZE;

	FindInitialGrids(*gridVec);

	Grid bestGrid;
	int bestScore = -1;

	// repeat until no more words could be inserted
	int level=1;
	
	// when no more words can be inserted, there are two strategies for continuation:
	// 3 == insert best grid so far alone
	// 2 == insert all grids with one word less
	// 1 == use flipper square
	// 0 == stop the algorithm
	int continueStrategyCount=3;

	while(gridVec->size()>0 || continueStrategyCount>0)
	{
		// now, choose the grid with the highest score
		// but no grids with incomplete words!
		Grid *gridVecEnd=&(*gridVec->end());
		for(Grid *it = &(*gridVec->begin());it!=gridVecEnd;++it)
		{
			if(it->Score()>bestScore && !it->FindIncompleteWordPos(tmp))
			{
				bestGrid= *it;
				bestScore = bestGrid.Score();
				continueStrategyCount = 3;
			}
		}

		double currentTime = ClockSec();
		
#ifndef BENCHMARK		
		// play it safe, except we make a benchmark
		if(currentTime>MAXUPPER_TIMELIMIT)
			break;
#endif
		double expectedTime = bestGrid.ExpectedTime();
		if(expectedTime < LOWER_TIMELIMIT && _LevelSize < MAXLEVELSIZE && level>4)
			_LevelSize += LEVELSIZESTEP;
		else if ((currentTime > LOWER_TIMELIMIT || expectedTime > UPPER_TIMELIMIT) && _LevelSize > MINLEVELSIZE)
		{
			_LevelSize -= 2*LEVELSIZESTEP;
			if (expectedTime > MAXUPPER_TIMELIMIT)
				_LevelSize -= 6*LEVELSIZESTEP;
			if(_LevelSize < MINLEVELSIZE)
				_LevelSize=MINLEVELSIZE;
		}

		if(DebugMode)
		{
			cerr << bestGrid;
			cerr << "best grid score:    " << bestScore << endl;
			cerr << "expected score :    " << bestGrid.ExpectedScore() << endl;
			cerr << "current time :      " << currentTime << endl;
			cerr << "estimated time :    " << expectedTime << endl;
			cerr << "current level  :    " << level << endl;
			cerr << "current level size: " << _LevelSize << endl;
		}

		// basic algorithm:
		// create all grids with one word more, choose a subset among them
		nextGridVec->clear();
		FindNextGridLevel(*gridVec,*nextGridVec);

		// if level is empty, try different continuation strategies
		if(nextGridVec->size()==0)
		{
			if(DebugMode)
				cerr << "continue strategy=" << continueStrategyCount << endl;

			if(continueStrategyCount == 0)  // stop if there was no improvement after last continuation
				break;

			// make sure the algo does not stop though there are obvious continuations
			gridVec->clear();
			if(continueStrategyCount==3)
			{
				if(DebugMode)
					cerr << "continue with best grid alone ...\n";
				gridVec->push_back(bestGrid);
				FindNextGridLevel(*gridVec,*nextGridVec);
			}
			else if(continueStrategyCount==2 && !bestGrid.HasFlipper())
			{
				AddAllGridsWithOneWordLess(bestGrid,gridVec);
				FindNextGridLevel(*gridVec,*nextGridVec);
		}
			else if(continueStrategyCount==1 && !bestGrid.HasFlipper())
			{
//				gridVec->push_back(bestGrid);
				AddAllGridsWithOneWordLess(bestGrid,gridVec);
				FindAllWordsWithFlipper(*gridVec,*nextGridVec);
			}

			--continueStrategyCount;
		}
		
		tmpVec = gridVec;  // switch both vectors quickly
		gridVec = nextGridVec;  
		nextGridVec = tmpVec; 
		level++;
	}
	delete gridVec;
	delete nextGridVec;

	// return copy of the best grid
	return new Grid(bestGrid);
}


// WordOMatic.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//


bool DebugMode=false;
bool ShowTimeResult = false;


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

	if(argc<2)
		Error("missing file name");
	
	// check additional arguments
	for(i=2;i<argc;++i)
	{
		if(strcmp((const char *)argv[i],"-d")==0)
		{
			ShowTimeResult=true;
			DebugMode=true;
		}
		else if(strcmp((const char *)argv[i],"-t")==0)
			ShowTimeResult=true;
	}


	// 1. read the word list
	WordPool::ReadPool((const char *)argv[1]);

	// 2. find a good grid in MAXTIME seconds
	Grid *g=Solver::FindBestGrid();

	// 3. output grid
	cout << *g;

	// 4. if ShowTimeResult option is on, output score
	if(ShowTimeResult )
	{
		cout << "Score=" << g->Score() << endl;
		cout << "Time =" << ClockSec() << endl;
	}

	delete g;
	return 0;
}

void Error(char *string)
{
	cerr << string << "\n";
	exit(1);
}