// Pentomino Solution using Dancing links, Donald E. Knuth
// Code by Andrew Stuart, 2011, 2023
#include "stdafx.h"
#include "string.h"
#include "stdlib.h"
#include "conio.h"

struct dlx // Dancing Links node
{
	struct dlx *L; // Left
	struct dlx *R; // Right
	struct dlx *U; // Up
	struct dlx *D; // Down
	struct dlx *C;
	char N;
	int S;
	int id;
	int row_num;
};

#undef VERSION_CHESSBOARD
#define VERSION_SIX_BY_TEN
#undef VERSION_FOUR_BY_FIFTEEN
#undef VERSION_THREE_BY_TWENTY

#ifdef VERSION_CHESSBOARD

#define XSIZE 8
#define YSIZE 8
#define NROWS 1569
#define NCOLS 73
#define FILE_POSSIBLES "pent1568.txt"

#endif

#ifdef VERSION_SIX_BY_TEN

#define XSIZE 10
#define YSIZE 6
#define NROWS 1901
#define NCOLS 73
#define FILE_POSSIBLES "pent1900.txt"

#endif

#ifdef VERSION_FOUR_BY_FIFTEEN

#define XSIZE 15
#define YSIZE 4
#define NROWS 1243
#define NCOLS 73
#define FILE_POSSIBLES "pent1242.txt"

#endif

#ifdef VERSION_THREE_BY_TWENTY

#define XSIZE 20
#define YSIZE 3
#define NROWS 793
#define NCOLS 73
#define FILE_POSSIBLES "pent792.txt"

#endif

struct dlx *web[NROWS][NCOLS], *h;
struct dlx net[NROWS][NCOLS];
struct dlx *bigO[1000];
int target[NROWS][NCOLS];

FILE *res;
int sols = 0;
int int_solution[8*8];
int outfiles = 1;

struct pent_definition {
	char pClass;		// Name of Pentomino and class for HTML output
	char *pColour;		// Bright colours for HTML output
	char *pPastel;		// Pastel colours for HTML output
	int shape_x[5];		// Offsets that define the shape
	int shape_y[5];
} pentset[13] = {
	{ 'F',"bb8957","bb8957",{2,0,1,2,1},{0,1,1,1,2} },
	{ 'L',"f7ae64","EDA09F",{0,1,1,1,1},{0,0,1,2,3} },
	{ 'I',"f7f74f","C67BC7",{0,1,2,3,4},{0,0,0,0,0} },
	{ 'P',"e03c3c","B2D98B",{0,1,2,1,2},{0,0,0,1,1} },
	{ 'N',"d42a78","8DB2DA",{0,0,1,1,1},{0,1,1,2,3} },
	{ 'T',"6666FF","C5C679",{0,0,1,2,0},{0,1,1,1,2} },
	{ 'U',"c63fd5","B38CDA",{0,1,0,0,1},{0,0,1,2,2} },
	{ 'V',"54dcd8","D9B38C",{2,2,0,1,2},{0,1,2,2,2} },
	{ 'W',"218721","DA8DB3",{0,1,1,2,2},{0,0,1,1,2} },
	{ 'X',"ee7db6","9EED9E",{1,0,1,2,1},{0,1,1,1,2} },
	{ 'Y',"86fb86","A09FEE",{2,0,1,2,3},{0,1,1,1,1} },
	{ 'Z',"CCCC33","7AC5C6",{1,2,1,0,1},{0,0,1,2,2} },
	{ 'O',"FFFFFF","FFFFFF",{0,0,0,0,0},{0,0,0,0,0} } // Hole - for gaps in board
};

// To save run time when generating solutions the matrix is pre-generated here
int CreatePentominoSet( void )
{
	int x,y,px[5],py[5],i,j,max,lmax,s,r,c[12],ct=0;
	bool outside;
	FILE *fid;

	fid = fopen("pent.txt","w");

	for(s=0;s<12;s++)
	{
		c[s]=0;
		for(y=0;y<YSIZE;y++)
			for(x=0;x<XSIZE;x++)
				for(r=0;r<8;r++)
				{
					outside = false;
					for(i=0;i<5;i++)
					{
						switch( r ) {
						case 0 :
							px[i] = pentset[s].shape_x[i]+x;
							py[i] = pentset[s].shape_y[i]+y;
							break;
						case 1 :
							px[i] = (XSIZE-1) - (pentset[s].shape_x[i]+x);
							py[i] = pentset[s].shape_y[i]+y;
							break;
						case 2 :
							px[i] = pentset[s].shape_x[i]+x;
							py[i] = (YSIZE-1) - (pentset[s].shape_y[i]+y);
							break;
						case 3 :
							px[i] = (XSIZE-1) - (pentset[s].shape_x[i]+x);
							py[i] = (YSIZE-1) - (pentset[s].shape_y[i]+y);
							break;
						case 4 :
							py[i] = pentset[s].shape_x[i]+x;
							px[i] = pentset[s].shape_y[i]+y;
							break;
						case 5 :
							py[i] = (YSIZE-1) - (pentset[s].shape_x[i]+x);
							px[i] = pentset[s].shape_y[i]+y;
							break;
						case 6 :
							py[i] = pentset[s].shape_x[i]+x;
							px[i] = (XSIZE-1) - (pentset[s].shape_y[i]+y);
							break;
						case 7 :
							py[i] = (YSIZE-1) - (pentset[s].shape_x[i]+x);
							px[i] = (XSIZE-1) - (pentset[s].shape_y[i]+y);
							break;
						}
#ifdef VERSION_CHESSBOARD
						if( px[i] < 0 || px[i] > XSIZE-1 || py[i] < 0 || py[i] > YSIZE-1 )
							outside = true;
						if( (px[i] == 3 || px[i] == 4) && (py[i] == 3 || py[i] == 4) )
							outside = true;
#else
						if( px[i] < 0 || px[i] > XSIZE-1 || py[i] < 0 || py[i] > YSIZE-1 )
							outside = true;
#endif
					}
					if( outside == false )
					{
						fprintf(fid,"%c,%d,",pentset[s].pClass,s);

						lmax = -1;
						for(j=0;j<5;j++)
						{
							max = 999;
							for(i=0;i<5;i++)
								if( (py[i])*XSIZE+px[i] > lmax && (py[i])*XSIZE+px[i] < max )
									max = (py[i])*XSIZE+px[i];
							fprintf(fid,"%d,",max);
							lmax = max;
						}
						fprintf(fid,"\n");
						ct++;
						c[s]++;
					}
				}
		printf("%c: %d\n",pentset[s].pClass,c[s]);
	}
	fclose(fid);
	printf("Total: %d\n",ct);

	return 0;
}
void initialise( struct dlx *obj, char name, int size, int num, int row_num )
{
	obj->L = NULL;
	obj->R = NULL;
	obj->U = NULL;
	obj->D = NULL;
	obj->C = NULL;
	obj->N = name;
	obj->S = size;
	obj->id = num;
	obj->row_num = row_num;
}
void take_out_node( struct dlx *x )
{
	if( x->L->id >= NROWS*NCOLS
	 || x->R->id >= NROWS*NCOLS
	 || x->R->id >= NROWS*NCOLS
	 || x->R->id >= NROWS*NCOLS )
	{
		printf("error\n");
		return;
	}
	x->L->R = x->R;
	x->R->L = x->L;
	x->D->U = x->U;
	x->U->D = x->D;
	x->C->S--;
}

void put_back_node( struct dlx *x )
{
	x->L->R = x;
	x->R->L = x;
	x->D->U = x;
	x->U->D = x;
	x->C->S++;
}

void Cover_Column( struct dlx *c )
{
	struct dlx *i, *j;

	for(i=c->D;i!=c;i=i->D)
		for(j=i->R;j!=i;j=j->R)
		{
			j->D->U = j->U;
			j->U->D = j->D;
			j->C->S--;
		}
	c->R->L = c->L;	// Remove itself from the header list
	c->L->R = c->R;
}

void UnCover_Column( struct dlx *c )
{
	struct dlx *i, *j;

	for(i=c->U;i!=c;i=i->U)
		for(j=i->L;j!=i;j=j->L)
		{
			j->C->S++;
			j->D->U = j;
			j->U->D = j;
		}
	c->R->L = c;
	c->L->R = c;
}

void PrintSolution( void )
{
	int i,j,p;
	char outfile[1000];
	sols++;

	if( (sols % 500) == 1 ) // Create more files if too many
	{
		sprintf(outfile,"pentominos%d.htm",outfiles++);
		res = fopen(outfile,"w");
		fprintf(res,"<html><head><title>Pentominos</title>\n<style>\n* { box-sizing:border-box;}\nbody {background: linear-gradient(#d4e9e3, #5390D9);}\n");
		for(i=0;i<13;i++)
			fprintf(res,".%c { background-color:#%s;}\n",pentset[i].pClass,pentset[i].pColour);
		fprintf(res,"table { background-color:black;\nborder-spacing:1px; }\ntd { width:25px; height:25px; }\nh2 { margin: 5px 0 3px 0; }\n");
		fprintf(res,"#capsule { float:left; margin-right:10px; }</style></head>\n<body>\n");
	}
	fprintf(res,"<div id=\"capsule\"><h2>%d</h2>\n",sols);
	fprintf(res,"<table>\n");
	for(i=0;i<YSIZE;i++)
	{
		fprintf(res,"<tr>\n");
		for(j=0;j<XSIZE;j++)
		{
			p = int_solution[i*XSIZE+j];
			fprintf(res,"<td class=\"%c\"></td>\n",pentset[p].pClass);
		}
		fprintf(res,"</tr>\n");
	}
	fprintf(res,"</table></div>\n");

	if( (sols % 500) == 0 )
	{
		fprintf(res,"</body></html>\n");
		fclose(res);
	}
}

bool search( int k )
{
	struct dlx *c,*r,*j,*saver;
	int n,minc,p;
	char solution[XSIZE*YSIZE];

	if( h->R == h )
	{
		printf("Print solution %d at k= %d\r",sols,k);
		int_solution[0] = 0;

		for(n=0;n<XSIZE*YSIZE;n++) solution[n] = '.';
		for(n=0;n<k;n++)
		{
			minc = bigO[n]->row_num;
			saver = bigO[n];
			for(r=bigO[n]->R;r!=bigO[n];r=r->R)
				if( r->row_num < minc )
				{
					minc = r->row_num;
					saver = r;
				}

			if( bigO[n] != saver )
			{
				p = bigO[n]->row_num-13;
#ifdef VERSION_CHESSBOARD
				if( p > 26 ) p+=2;
				if( p > 34 ) p+=2;
#endif
				solution[p] = saver->N;
				int_solution[p] = saver->row_num;
			}
			for(r=bigO[n]->R;r!=bigO[n];r=r->R)
				if( r != saver )
				{
					p = r->row_num-13;
#ifdef VERSION_CHESSBOARD
					if( p > 26 ) p+=2;
					if( p > 34 ) p+=2;
#endif
					solution[p] = saver->N;
					int_solution[p] = saver->row_num;
				}
		}
		PrintSolution();
		return true;
	}

	minc = 9999;
	for(r=h->R;r!=h;r=r->R)
	{
		if( r->S < minc )
		{
			c = r;
			minc = r->S;
		}
	}
	Cover_Column(c);

	for(r=c->D;r!=c;r=r->D)
	{
		bigO[k] = r;
		for(j=r->R;j!=r;j=j->R)
			Cover_Column(j->C);
		search( k+1 );
		r = bigO[k];
		c = r->C;
		for(j=r->L;j!=r;j=j->L)
			UnCover_Column(j->C);
	}
	UnCover_Column(c);
	return false;
}

int main(int argc, char* argv[])
{
	FILE *fid;
	char line[1000], *ptr, ch;
	int sq[5],pent,i,j;
	int sqt[NCOLS];

	//---------------------------------------------------------
	// To save run time when generating solutions the node data is pre-generated
	//---------------------------------------------------------
	//	CreatePentominoSet();
	//	return 0;

	fid = fopen(FILE_POSSIBLES,"r");
	if( !fid )
	{
		printf("Cannot open %s for reading\n",FILE_POSSIBLES);
		return 1;
	}

	//---------------------------------------------------------
	// create the node data
	//---------------------------------------------------------
	for(j=0;j<NROWS;j++)
		for(i=0;i<NCOLS;i++)
			target[j][i] = (j)?0:1;

	for(i=0;i<NCOLS;i++) sqt[i] = 0;

	for(j=0;j<NROWS;j++)
		for(i=0;i<NCOLS;i++)
		{
			if( i == 0 )
				initialise(&net[j][i],'h',       NROWS-1,j*NCOLS+i,i);
			else if( i < 13 )
				initialise(&net[j][i],pentset[i-1].pClass,NROWS-1,j*NCOLS+i,i);
			else initialise(&net[j][i],'p',       NROWS-1,j*NCOLS+i,i);
		}

	//---------------------------------------------------------
	// Create the links between the nodes
	//---------------------------------------------------------
	for(j=0;j<NROWS;j++)
		for(i=0;i<NCOLS;i++)
		{
			web[j][i] = &net[j][i];
			net[j][i].L = &net[j][(i)?i-1:NCOLS-1];
			net[j][i].R = &net[j][(i<NCOLS-1)?i+1:0];
			net[j][i].U = &net[(j)?j-1:NROWS-1][i];
			net[j][i].D = &net[(j<NROWS-1)?j+1:0][i];
			net[j][i].C = &net[0][i];
		}
	h = &net[0][0];

	j=1;
	while(1)
	{
		ptr = fgets(line,900,fid);
		if( !ptr ) break;

		sscanf(line,"%c,%d,%d,%d,%d,%d,%d\n",&ch,&pent,&sq[0],&sq[1],&sq[2],&sq[3],&sq[4]);
		target[j][pent+1] = 1;
		sqt[pent+1]++;
		for(i=0;i<5;i++)
		{
#ifdef VERSION_CHESSBOARD
			if( sq[i] > 26 ) sq[i]-=2;
			if( sq[i] > 32 ) sq[i]-=2;
#endif
			target[j][sq[i]+13] = 1;
			sqt[sq[i]+13]++;
		}
		j++;
	}
	printf("j=%d\n",j);

	//---------------------------------------------------------
	// Set up target matrix
	//---------------------------------------------------------
	FILE *fod = fopen("targetmatrix.txt","w"); // Not necessary to print, just for look-see
	for(j=0;j<NROWS;j++)  // each file
	{
		for(i=0;i<NCOLS;i++)  // each rank
		{
			fprintf(fod,"%c",".*"[target[j][i]]);
			if( target[j][i] == 0 )
				take_out_node(web[j][i]);
			if( h->row_num != 0 )
			{
				fclose(fod);
				printf("stop %d\n",target[j][i]);
				return 0;
			}
		}
		fprintf(fod,"\n");
	}
	fclose(fod);

	//---------------------------------------------------------
	// Find All Solutions
	//---------------------------------------------------------
	search(0);

	return 0;
}