// Function: To determine the number of distinct arrangements of square tiles of different sizes within a boundary square with specified side length ignoring symmetries.
//
// Developed by Chris Gribble in 2014.

#pragma once

#include <SDKDDKVer.h>

#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <fstream>
#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <tchar.h>

using namespace std;

static const int MaxN        = 20;					// Maximum value of N.
static const int MaxS        = 2000000;				// Maximum number of boundary squares in tree.
static const int MinN        = 0;					// Minimum value of N.
static const int MinTileSize = 2;					// Places restriction on the smallest tile size to reduce excessive computation.

static __int64 NumMatchIdentity[MaxN];				// Number of partially tiled boundary squares generated that match others in the tree.
static __int64 NumMatchless[MaxN];					// Number of partially tiled boundary squares in tree.
static __int64 NumMatchReflectAnti[MaxN];			// Number of partially tiled boundary squares generated that, when reflected about the antidiagonal, match others in the tree.
static __int64 NumMatchReflectDiag[MaxN];			// Number of partially tiled boundary squares generated that, when reflected about the leading diagonal, match others in the tree.
static __int64 NumMatchReflectHoriz[MaxN];			// Number of partially tiled boundary squares generated that, when reflected about the horizontal axis, match others in the tree.
static __int64 NumMatchReflectVert[MaxN];			// Number of partially tiled boundary squares generated that, when reflected about the vertical axis, match others in the tree.
static __int64 NumMatchRotate90[MaxN];				// Number of partially tiled boundary squares generated that, when rotated by 90 degs, match others in the tree.
static __int64 NumMatchRotate180[MaxN];				// Number of partially tiled boundary squares generated that, when rotated by 180 degs, match others in the tree.
static __int64 NumMatchRotate270[MaxN];				// Number of partially tiled boundary squares generated that, when rotated by 270 degs, match others in the tree.

static int LevelFirstIndex[MaxN * MaxN];			// Index of first boundary square at each level in tree.
static int LevelLastIndex[MaxN * MaxN];				// Index of last boundary square at each level in tree.
static int SquareIndex;								// Index of boundary square in the list of partially tiled boundary squares.

static short int Level;								// Current level in tree = number of square tiles placed in boundary square.
static short int N;									// User-specified boundary square side length.
static short int NSquared;							// N * N.
static short int NumTreesBuilt;						// Number of trees built.
static short int Square[MaxN][MaxN];				// Boundary square.

static short int ***ListOfSquares;					// List of all partially tiled boundary squares with symmetries removed.

fstream OpFile;										// Output file.


bool matchTransformations()
{
	// Indicates whether transform of the boundary square pre-exists or not.

	int n;										// Loop counter.

	short int k, l;								// Loop counters.
	short int match_identity;					// Count of cell value matches between a new boundary square and previously generated boundary squares at the same level.
	short int match_reflect_anti;				// Count of cell value matches between a new boundary square reflected about the antidiagonal and previously generated boundary squares at the same level.
	short int match_reflect_diag;				// Count of cell value matches between a new boundary square reflected about the leading diagonal and previously generated boundary squares at the same level.
	short int match_reflect_horiz;				// Count of cell value matches between a new boundary square reflected about the horizontal axis and previously generated boundary squares at the same level.
	short int match_reflect_vert;				// Count of cell value matches between a new boundary square reflected about the vertical axis and previously generated boundary squares at the same level.
	short int match_rotate_90;					// Count of cell value matches between a new boundary square rotated by 90 degs and previously generated boundary squares at the same level.
	short int match_rotate_180;					// Count of cell value matches between a new boundary square rotated by 180 degs and previously generated boundary squares at the same level.
	short int match_rotate_270;					// Count of cell value matches between a new boundary square rotated by 270 degs and previously generated boundary squares at the same level.

	bool transformExists = false;				// Indicates whether a transform of a new boundary square already exists at the same level or not.

	// Check that a transformation of this square does not already exist at the same level.

	for (n = LevelFirstIndex[Level]; n < SquareIndex; n++)
	{
		match_identity      = 0;
		match_reflect_diag  = 0;
		match_reflect_anti  = 0;
		match_reflect_horiz = 0;
		match_reflect_vert  = 0;
		match_rotate_90     = 0;
		match_rotate_180    = 0;
		match_rotate_270    = 0;

		for (l = 0; l < N; l++)
		{
			for (k = 0; k < N; k++)
			{
				// Identity transformation.

				if (Square[k][l] == ListOfSquares[n][k][l])
				{
					match_identity++;
				}

				// Reflect antidiagonally.

				if (Square[N - l - 1][N - k - 1] == ListOfSquares[n][k][l])
				{
					match_reflect_anti++;
				}

				// Reflect diagonally.

				if (Square[l][k] == ListOfSquares[n][k][l])
				{
					match_reflect_diag++;
				}

				// Reflect horizontally.

				if (Square[N - k - 1][l] == ListOfSquares[n][k][l])
				{
					match_reflect_horiz++;
				}

				// Reflect vertically.

				if (Square[k][N - l - 1] == ListOfSquares[n][k][l])
				{
					match_reflect_vert++;
				}

				// Rotate left by 90 degs.

				if (Square[N - l - 1][k] == ListOfSquares[n][k][l])
				{
					match_rotate_90++;
				}

				// Rotate left by 180 degs.

				if (Square[N - k - 1][N - l - 1] == ListOfSquares[n][k][l])
				{
					match_rotate_180++;
				}

				// Rotate left by 270 degs.

				if (Square[l][N - k - 1] == ListOfSquares[n][k][l])
				{
					match_rotate_270++;
				}
			}
		}
/*
		OpFile << "match_identity      = " << match_identity      << endl;
		OpFile << "match_reflect_anti  = " << match_reflect_anti  << endl;
		OpFile << "match_reflect_diag  = " << match_reflect_diag  << endl;
		OpFile << "match_reflect_horiz = " << match_reflect_horiz << endl;
		OpFile << "match_reflect_vert  = " << match_reflect_vert  << endl;
		OpFile << "match_rotate_90     = " << match_rotate_90     << endl;
		OpFile << "match_rotate_180    = " << match_rotate_180    << endl;
		OpFile << "match_rotate_270    = " << match_rotate_270    << endl;
*/
		if (match_identity == NSquared)
		{
			NumMatchIdentity[NumTreesBuilt]++;
			transformExists = true;
			//			OpFile << "NumMatchIdentity = " << NumMatchIdentity << endl << endl;
			break;
		}
		else if (match_reflect_anti == NSquared)
		{
			NumMatchReflectAnti[NumTreesBuilt]++;
			transformExists = true;
			//			OpFile << "NumMatchReflectAnti = " << NumMatchReflectAnti << endl << endl;
			break;
		}
		else if (match_reflect_diag == NSquared)
		{
			NumMatchReflectDiag[NumTreesBuilt]++;
			transformExists = true;
			//			OpFile << "NumMatchReflectDiag = " << NumMatchReflectDiag << endl << endl;
			break;
		}
		else if (match_reflect_horiz == NSquared)
		{
			NumMatchReflectHoriz[NumTreesBuilt]++;
			transformExists = true;
			//			OpFile << "NumMatchReflectHoriz = " << NumMatchReflectHoriz << endl << endl;
			break;
		}
		else if (match_reflect_vert == NSquared)
		{
			NumMatchReflectVert[NumTreesBuilt]++;
			transformExists = true;
			//			OpFile << "NumMatchReflectVert = " << NumMatchReflectVert << endl << endl;
			break;
		}
		else if (match_rotate_90 == NSquared)
		{
			NumMatchRotate90[NumTreesBuilt]++;
			transformExists = true;
			//			OpFile << "NumMatchRotate90 = " << NumMatchRotate90 << endl << endl;
			break;
		}
		else if (match_rotate_180 == NSquared)
		{
			NumMatchRotate180[NumTreesBuilt]++;
			transformExists = true;
			//			OpFile << "NumMatchRotate180 = " << NumMatchRotate180 << endl << endl;
			break;
		}
		else if (match_rotate_270 == NSquared)
		{
			NumMatchRotate270[NumTreesBuilt]++;
			transformExists = true;
			//			OpFile << "NumMatchRotate270 = " << NumMatchRotate270 << endl << endl;
			break;
		}
	}

	if (transformExists == false)
	{
		NumMatchless[NumTreesBuilt]++;
		//		OpFile << "NumMatchless = " << NumMatchless << endl << endl;
	}

	return transformExists;
}

void buildTree()
{
	int m;										// Loop counter.

	short int empty;
	short int flagSquare[MaxN][MaxN];			// Records which cells have been used when trying to place the top left hand corner of a square tile other than the first.
	short int i, j, k, l;						// Loop counters.
	short int numPartsFitted = 0;
	short int t;
	short int tileSize;
	short int x, y;

	bool emptyCell;								// Indicates whether an empty cell has been found in the boundary square or not.
	bool firstTile;								// Indicates whether the first tile at a particular level has been placed or not.
	bool transformExists;						// Indicates whether a transform of a new boundary square already exists at the same level or not.

	for (tileSize = MinTileSize; tileSize <= N; tileSize++)
	{
		// Increment number of trees built.

		NumTreesBuilt++;
		OpFile << endl << "NumTreesBuilt = " << NumTreesBuilt << endl;

		// Construct tree.

		// Initialisations.

		for (i = 0; i <= NSquared; i++)
		{
			LevelFirstIndex[i] = 0;
			LevelLastIndex[i]  = 0;
		}

		// Form boundary square at Level 0.

		Level = 0;
		SquareIndex = 0;
		LevelFirstIndex[Level] = SquareIndex;
		LevelLastIndex[Level]  = SquareIndex;

		for (j = 0; j < N; j++)
		{
			for (i = 0; i < N; i++)
			{
				ListOfSquares[SquareIndex][i][j] = 0;
			}
		}

		// Form boundary squares at Level 1.
		// Place the top left hand corner of the largest square tile in each of the positions within a wedge of the boundary square as illustrated below:
		//		...
		//		 ..
		//		  .
		// In this case, t = 3.

		t = (N - tileSize) / 2 + 1;

		Level++;

		for (y = 0; y < t; y++)
		{
			for (x = y; x < t; x++)
			{
				// Initialise square.

				for (j = 0; j < N; j++)
				{
					for (i = 0; i < N; i++)
					{
						Square[i][j] = ListOfSquares[LevelFirstIndex[Level - 1]][i][j];
					}
				}

				for (j = y; j < y + tileSize; j++)
				{
					for (i = x; i < x + tileSize; i++)
					{
						Square[i][j] = tileSize;
					}
				}
/*
				for (j = 0; j < N; j++)
				{
					for (i = 0; i < N; i++)
					{
						OpFile << " " << Square[i][j];
					}

					OpFile << endl;
				}

				OpFile << endl;
*/
				// Record square.

				SquareIndex++;

				if ((x == 0) &&
					(y == 0))
				{
					LevelFirstIndex[Level] = SquareIndex;
				}

				for (j = 0; j < N; j++)
				{
					for (i = 0; i < N; i++)
					{
						ListOfSquares[SquareIndex][i][j] = Square[i][j];
					}
				}

				LevelLastIndex[Level] = SquareIndex;
			}
		}

		// Form squares at other levels.

		for (i = 2; i <= (N / tileSize) * (N / tileSize); i++)
		{
			Level++;
			firstTile = false;

			for (m = LevelFirstIndex[Level - 1]; m <= LevelLastIndex[Level - 1]; m++)
			{
				// Record which cells cannot be used to place new part.

				for (l = 0; l < N; l++)
				{
					for (k = 0; k < N; k++)
					{
						flagSquare[k][l] = ListOfSquares[m][k][l];
					}
				}

				// Find the next empty cell in the square.

findNextEmptyCell:

				emptyCell = false;

				for (l = 0; l < N; l++)
				{
					for (k = 0; k < N; k++)
					{
						if (flagSquare[k][l] == 0)
						{
							emptyCell = true;
							x = l;
							y = k;
							break;
						}
					}

					if (emptyCell == true) break;
				}

				if (emptyCell == true)
				{
					// Try to fit part into square with the empty cell corresponding to the top left-hand corner of the part.

					if ((x + tileSize <= N) &&
						(y + tileSize <= N))
					{
						empty = 0;

						for (l = x; l < x + tileSize; l++)
						{
							for (k = y; k < y + tileSize; k++)
							{
								if (flagSquare[k][l] == 0)
								{
									empty++;
								}
							}
						}

						if (empty == tileSize * tileSize)
						{
							// Part fits, so fit it.

							SquareIndex++;

							if (firstTile == false)
							{
								LevelFirstIndex[Level] = SquareIndex;
								firstTile = true;
							}

							for (l = 0; l < N; l++)
							{
								for (k = 0; k < N; k++)
								{
									Square[k][l] = ListOfSquares[m][k][l];
								}
							}

							for (l = x; l < x + tileSize; l++)
							{
								for (k = y; k < y + tileSize; k++)
								{
									Square[k][l] = tileSize;
								}
							}
/*
							for (l = 0; l < N; l++)
							{
								for (k = 0; k < N; k++)
								{
									OpFile << " " << Square[k][l];
								}

								OpFile << endl;
							}

							OpFile << endl;
*/
							// Check that a transformation of this square does not already exist at this level.

							transformExists = matchTransformations();

							if (transformExists == true)
							{
								flagSquare[y][x] = -4;				// Set flag to indicate that a fit was successful at this cell, but do not put boundary square in list.
								SquareIndex--;
								goto findNextEmptyCell;
							}

							for (l = 0; l < N; l++)
							{
								for (k = 0; k < N; k++)
								{
									ListOfSquares[SquareIndex][k][l] = Square[k][l];
								}
							}

							flagSquare[y][x] = -2;						// Flag fit successful at this cell.
							LevelLastIndex[Level] = SquareIndex;
							cout << NumTreesBuilt << "    " << Level << "    " << SquareIndex << endl;
/*
							for (l = 0; l < N; l++)
							{
								for (k = 0; k < N; k++)
								{
									OpFile << " " << Square[k][l];
								}

								OpFile << "    ";

								for (k = 0; k < N; k++)
								{
									OpFile << " " << flagSquare[k][l];
								}

								OpFile << endl;
							}

							OpFile << endl;
*/
							// Find where the square tile can fit next.

							goto findNextEmptyCell;
						}
						else
						{
							// Part doesn't fit, so find the next empty cell if there is one.

							flagSquare[y][x] = -1;						// Set flag to indicate that a fit was unsuccessful at this cell.
							goto findNextEmptyCell;
						}
					}
					else
					{
						// Part doesn't fit, so find the next empty cell if there is one.

						flagSquare[y][x] = -1;							// Set flag to indicate that a fit was unsuccessful at this cell.
						goto findNextEmptyCell;
					}
				}		// End of if.
			}		// End of m loop.

			if (LevelLastIndex[Level] == 0)
			{
				// No part could be fitted at the current level.

				break;
			}
		}		// End of i loop.

		// Output level data.

		for (l = 0; l <= Level; l++)
		{
			OpFile << l << "    " << LevelLastIndex[l] - LevelFirstIndex[l] + 1 << endl;
		}
	}		// 	End of for (tileSize = 1; tileSize <= N; tileSize++)

	return;
}


int main()
{
	int  i, j;							// Loop counters.

	// Create output file.

	OpFile.open("SquarePlacements.txt", ios_base::out | ios_base::trunc);

	// Get dimensions of square.

	cout << "Enter N ";
	cin >> N;

	if ((N < MinN) ||
		(N > MaxN))
	{
		OpFile << "Value of N " << N << " out of range." << endl;
		return 1;
	}

	OpFile << "N = " << N << endl;

	NSquared = N * N;

	// Allocate memory for list of squares for use in buildTree.

	ListOfSquares = (short int ***)malloc(MaxS * sizeof(short int **));

	for (i = 0; i < MaxS; i++)
	{
		ListOfSquares[i] = (short int **)malloc(N * sizeof(short int *));
	}

	for (j = 0; j < N; j++)
	{
		for (i = 0; i < MaxS; i++)
		{
			ListOfSquares[i][j] = (short int *)malloc(N * sizeof(short int));
		}
	}

	buildTree();

	// Release memory.

	for (j = 0; j < N; j++)
	{
		for (i = 0; i < MaxS; i++)
		{
			free(ListOfSquares[i][j]);
		}
	}

	for (i = 0; i < MaxS; i++)
	{
		free(ListOfSquares[i]);
	}

	free(ListOfSquares);

	//	Output stats.

	OpFile << endl;
	OpFile << "Number of trees built = " << NumTreesBuilt        << endl << endl;

	OpFile << "NumMatchIdentity      = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchIdentity[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchRotate90      = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchRotate90[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchRotate180     = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchRotate180[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchRotate270     = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchRotate270[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchReflectHoriz  = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchReflectHoriz[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchReflectVert   = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchReflectVert[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchReflectDiag   = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchReflectDiag[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchReflectAnti   = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchReflectAnti[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchless          = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchless[i] << "  ";
	}

	OpFile << endl << endl;

	OpFile << "Program complete" << endl;

	return 0;
}