/*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define N 13
#define NBMOTS 24

typedef struct
{
	int	len;
	int pos;
	int dir;
	int croise[5];
} ORDER;

ORDER ordre[NBMOTS] =
{
	{ 9,N*6+2,1,	6,4,1,5,7 },		//0
	{ 9,N*2+6,N,	2,3,-1,-1,-1 },		//1
	{ 9,N*2+2,1,	6,16,17,7,-1 },		//2
	{ 9,N*10+2,1,	4,22,23,5,-1 },		//3

	{ 7,N*6+3,N,	18,12,-1,-1,-1 },	//4
	{ 7,N*6+9,N,	19,13,-1,-1,-1 },	//5
	{ 7,N*0+2,N,	8,14,-1,-1,-1 },	//6
	{ 7,N*0+10,N,	9,15,-1,-1,-1 },	//7

	{ 6,N*0+0,1,	10,16,-1,-1,-1 },	//8
	{ 6,N*0+7,1,	17,11,-1,-1,-1 },	//9

	{ 7,N*0+0,N,	14,-1,-1,-1,-1 },	//10
	{ 7,N*0+12,N,	15,-1,-1,-1,-1 },	//11

	{ 6,N*12+0,1,	20,22,-1,-1,-1 },	//12
	{ 6,N*12+7,1,	23,21,-1,-1,-1 },	//13

	{ 5,N*4+0,1,	16,-1,-1,-1,-1 },	//14
	{ 5,N*4+8,1,	17,-1,-1,-1,-1 },	//15
	{ 5,N*0+4,N,	-1,-1,-1,-1,-1 },	//16
	{ 5,N*0+8,N,	-1,-1,-1,-1,-1 },	//17

	{ 5,N*8+0,1,	20,-1,-1,-1,-1 },	//18
	{ 5,N*8+8,1,	21,-1,-1,-1,-1 },	//19
	{ 5,N*8+0,N,	-1,-1,-1,-1,-1 },
	{ 5,N*8+12,N,	-1,-1,-1,-1,-1 },

	{ 3,N*10+5,N,	-1,-1,-1,-1,-1 },
	{ 3,N*10+7,N,	-1,-1,-1,-1,-1 }

};

char tableau[N*N];
int nbmots = 0;
#define MAX_MOTS 1600
#define MAX_LEN 9
typedef struct
{
	char mot[MAX_LEN+1];
	char used;
} MOT;

MOT Mot[MAX_MOTS];

// pointeurs sur les longueurs et les premiers mots
int NbMots[MAX_LEN+1];
MOT *Mots[MAX_LEN+1];

char memo[NBMOTS][MAX_LEN];
int value[256];

void store(char *p)
{
	int len;
	if (strlen(p) > MAX_LEN)
	{
		printf("Mot %s trop grand\n",p);
		exit(1);
	}
	if (nbmots >= MAX_MOTS)
	{
		printf("Trop de mots\n");
		exit(1);
	}

	len = strlen(p);
	if (Mots[len] == NULL)
	{
		Mots[len] = &Mot[nbmots];
	}
	++NbMots[len];
	
	strcpy(Mot[nbmots].mot,p);
	Mot[nbmots].used = 0;
	++nbmots;
}

int parse(char *name)
{
	FILE *in;
	char str[200];
	int c,n;

	in = fopen(name,"rb");
	if (in == NULL)
	{
		printf("Unable to open\n");
		return 1;
	}

	for (n = 0;n <= MAX_LEN;++n)
	{
		NbMots[n] = 0;
		Mots[n] = NULL;
	}

	n = 0;
	while (1)
	{
		c = fgetc(in);
		if (c == EOF)
		{
			str[n] = 0;
			store(str);
			break;
		}
		if (c == 0x0D)
		{
			str[n] = 0;
			store(str);
			n = 0;
		}
		if (c > 0x20)
		{
			str[n] = c;
			++n;
		}
	}

	fclose(in);
	return 0;
}

int record = 0;
void solution(void)
{
	int i,j;
	int sum;
	char *p;
	FILE *out;

	sum = 0;
	for (i = 0;i < N*N;++i)
	{
		sum += value[tableau[i]];
	}
	if (sum < record)
	{
		return;
	}
	record = sum;

	out = fopen("SOL","at");
	printf("Somme=%d\n",sum);
	fprintf(out,"Somme=%d\n",sum);
	p = tableau;
	for (i = 0;i < N;++i)
	{
		for (j = 0;j < N;++j)
		{
			if (*p)
			{
				putchar(*p);
				fputc(*p,out);
			}
			else
			{
				putchar(' ');
				fputc(' ',out);
			}
			++p;
		}
		fprintf(out,"\n");
		printf("\n");
	}
	fclose(out);
}

unsigned int pattern[MAX_LEN+1][MAX_LEN+1];

void initmots(void)
{
	MOT *m;
	int length,count;
	for (length = 0;length <= MAX_LEN; ++length)
	{
		m = Mots[length];
		count = NbMots[length];
		while(count)
		{
			int i;
			if (strlen(m->mot) != length)
			{
				printf("Bad length\n");
				exit(1);
			}
			for (i = 0;i < length;++i)
			{
				pattern[length][i] |= 1<<(m->mot[i] - 'A');
			}
			++m;
			--count;
		}
	}
}

int VerifyWord(int niveau)
{
	int length,dir;
	char *pos,*p;
	int flag,j;
	MOT *m;
	int count;

	if (niveau < 0 || niveau >= NBMOTS)
	{
		printf("Bug\n");
		exit(1);
	}
	length = ordre[niveau].len;
	pos = &tableau[ordre[niveau].pos];
	dir = ordre[niveau].dir;

// test rapide si le mot rentre ou non
	// jamais exécuté ???
	p = pos;
	for (j = 0;j < length;++j)
	{
		if (*p)
		{
			if ((pattern[length][j] & (1<<(*p-'A'))) == 0)
			{
				return 0;
			}
		}
		p += dir;
	}
	
	m = Mots[length];
	count = NbMots[length];
	while(count)
	{
		if (m->used == 0)
		{
			// bonne longueur ?
			flag = 0;
			p = pos;
			for (j = 0;j < length;++j)
			{
				if (*p)
				{
					if (*p != m->mot[j])
					{
						flag = 1;
						break;
					}
				}
				p += dir;
			}
			if (flag == 0)
			{
				// un mot rentre !!!!
				return 1;
			}
		}
		++m;
		--count;
	}
	return 0;
}


void croise(int niveau)
{
	int length,dir;
	char *pos,*p;
	int flag,j;
	MOT *m;
	int count;

	if (niveau >= NBMOTS)
	{
		solution();
		return;
	}
	length = ordre[niveau].len;
	pos = &tableau[ordre[niveau].pos];
	dir = ordre[niveau].dir;

	//printf("%d %d %d\n",length,ordre[niveau].pos,dir);

	p = pos;
	for (j = 0;j < length;++j)
	{
		memo[niveau][j] = *p;
		p += dir;
	}
		
	m = Mots[length];
	count = NbMots[length];

#if 0
	if (niveau >= 2 && length > 5)
	{
#define MAJORE 50
		// on majore le nombre de mots, pour éviter trop de calculs...
		if (count > MAJORE)
		{
			count = MAJORE;
		}
	}
#endif

	while(count)
	{
		if (m->used == 0)
		{
			// bonne longueur ?
			flag = 0;
			p = pos;
			for (j = 0;j < length;++j)
			{
				if (*p)
				{
					if (*p != m->mot[j])
					{
						flag = 1;
						break;
					}
				}
				p += dir;
			}
			if (flag == 0)
			{
				// le mot rentre
				p = pos;
				for (j = 0;j < length;++j)
				{
					*p = m->mot[j];
					p += dir;
				}
				m->used = 1;

				if (niveau == 0)
				{
					printf("%s\n", m->mot);
				}
				// avant d'aller plus loin, on vérifie qu'on peut rentrer d'autres mots
				flag = 1;
				for (j = 0;j < 5;++j)
				{
					if (ordre[niveau].croise[j] >= 0)
					{
						if (VerifyWord(ordre[niveau].croise[j]) == 0)
						{
							flag = 0;
							break;
						}
					}
				}
				if (flag)
				{
					croise(niveau+1);
				}
				m->used = 0;
				p = pos;
				for (j = 0;j < length;++j)
				{
					*p = memo[niveau][j];
					p += dir;
				}
				//solution();
			}
		}
		++m;
		--count;
	}

}

int main(void)
{
	int i;
	if (parse("LISTE4"))
	{
		return 1;
	}
	for (i = 0;i < 256;++i)
	{
		value[i] = 0;
	}
	value['N'] = 5;
	value['O'] = 6;
	value['C'] = 4;
	value['T'] = 6;
	value['A'] = 4;
	value['M'] = 2;
	value['B'] = 1;
	value['U'] = 3;
	value['L'] = 1;
	value['E'] = 2;

	initmots();

	croise(0);
	return 0;
}