// Function: To determine the number of equivalence classes of ways of placing k square tiles with side length s in an A X B rectangle, B <= A, // under all symmetry operations of the rectangle. // // Developed by Chris Gribble in 2014 as a console project under Microsoft Visual Studio Express 2013. // // The version of the program uploaded to the OEIS compiles with g++ (gcc 4.5.2). using namespace std; #include #include #include #include #include #include #include #include static const int MaxA = 30; // Maximum value of A. static const int MaxB = 30; // Maximum value of B. static const int MaxS = 8000000; // Maximum number of boundary rectangles in tree. static const int MinA = 0; // Minimum value of A. static const int MinB = 0; // Minimum value of B. static __int64 NumMatchIdentity[MaxA]; // Number of partially tiled boundary rectangles generated that match others in the tree. static __int64 NumMatchless[MaxA]; // Number of partially tiled boundary rectangles in tree. static __int64 NumMatchReflectHoriz[MaxA]; // Number of partially tiled boundary rectangles generated that, when reflected about the horizontal axis, match others in the tree. static __int64 NumMatchReflectVert[MaxA]; // Number of partially tiled boundary rectangles generated that, when reflected about the vertical axis, match others in the tree. static __int64 NumMatchRotate180[MaxA]; // Number of partially tiled boundary rectangles generated that, when rotated by 180 degs, match others in the tree. static int LevelFirstIndex[MaxA * MaxB]; // Index of first boundary rectangle at each level in tree. static int LevelLastIndex[MaxA * MaxB]; // Index of last boundary rectangle at each level in tree. static int RectangleIndex; // Index of boundary rectangle in the list of partially tiled boundary rectangles. static short int A; // User-specified boundary rectangle side length. static short int AB; // A * B. static short int B; // User-specified boundary rectangle side length. static short int Level; // Current level in tree = number of square tiles placed in boundary rectangle. static short int MaxNumTiles; // Maximum number of tiles to be placed in boundary rectangle to limit computation. static short int MinTileSideSize; // Minimum tile side size to reduce excessive computation. static short int NumTreesBuilt; // Number of trees built. static short int Rectangle[MaxA][MaxB]; // Boundary rectangle. static short int ***ListOfRectangles; // List of all partially tiled boundary rectangles with symmetries removed. fstream OpFile; // Output file. bool matchTransformations() { // Indicates whether transform of the boundary rectangle 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 rectangle and previously generated boundary rectangles at the same level. short int match_reflect_horiz; // Count of cell value matches between a new boundary rectangle reflected about the horizontal axis and previously generated boundary rectangles at the same level. short int match_reflect_vert; // Count of cell value matches between a new boundary rectangle reflected about the vertical axis and previously generated boundary rectangles at the same level. short int match_rotate_180; // Count of cell value matches between a new boundary rectangle rotated by 180 degs and previously generated boundary rectangles at the same level. bool transformExists = false; // Indicates whether a transform of a new boundary rectangle already exists at the same level or not. // Check that a transformation of this rectangle does not already exist at the same level. for (n = LevelFirstIndex[Level]; n < RectangleIndex; n++) { match_identity = 0; match_reflect_horiz = 0; match_reflect_vert = 0; match_rotate_180 = 0; for (l = 0; l < B; l++) { for (k = 0; k < A; k++) { // Identity transformation. if (Rectangle[k][l] == ListOfRectangles[n][k][l]) { match_identity++; } // Reflect horizontally. if (Rectangle[A - k - 1][l] == ListOfRectangles[n][k][l]) { match_reflect_horiz++; } // Reflect vertically. if (Rectangle[k][B - l - 1] == ListOfRectangles[n][k][l]) { match_reflect_vert++; } // Rotate left by 180 degs. if (Rectangle[A - k - 1][B - l - 1] == ListOfRectangles[n][k][l]) { match_rotate_180++; } } } if (match_identity == AB) { NumMatchIdentity[NumTreesBuilt]++; transformExists = true; // OpFile << "NumMatchIdentity = " << NumMatchIdentity[NumTreesBuilt] << endl << endl; break; } else if (match_reflect_horiz == AB) { NumMatchReflectHoriz[NumTreesBuilt]++; transformExists = true; // OpFile << "NumMatchReflectHoriz = " << NumMatchReflectHoriz[NumTreesBuilt] << endl << endl; break; } else if (match_reflect_vert == AB) { NumMatchReflectVert[NumTreesBuilt]++; transformExists = true; // OpFile << "NumMatchReflectVert = " << NumMatchReflectVert[NumTreesBuilt] << endl << endl; break; } else if (match_rotate_180 == AB) { NumMatchRotate180[NumTreesBuilt]++; transformExists = true; // OpFile << "NumMatchRotate180 = " << NumMatchRotate180[NumTreesBuilt] << endl << endl; break; } } if (transformExists == false) { NumMatchless[NumTreesBuilt]++; // OpFile << "NumMatchless = " << NumMatchless[NumTreesBuilt] << endl << endl; } return transformExists; } void buildTree() { int m; // Loop counter. short int empty; short int flagRectangle[MaxA][MaxB]; // 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 numTiles; short int s, t; short int tileSize; short int x, y; bool emptyCell; // Indicates whether an empty cell has been found in the boundary rectangle 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 rectangle already exists at the same level or not. for (tileSize = MinTileSideSize; tileSize <= B; tileSize++) { // Increment number of trees built. NumTreesBuilt++; // OpFile << endl << "Number of trees built = " << NumTreesBuilt << endl; OpFile << endl << "Tile side length = " << NumTreesBuilt + MinTileSideSize - 1 << endl; // Construct tree. // Initialisations. for (i = 0; i <= AB; i++) { LevelFirstIndex[i] = 0; LevelLastIndex[i] = 0; } // Form boundary rectangle at Level 0. Level = 0; RectangleIndex = 0; LevelFirstIndex[Level] = RectangleIndex; LevelLastIndex[Level] = RectangleIndex; for (j = 0; j < B; j++) { for (i = 0; i < A; i++) { ListOfRectangles[RectangleIndex][i][j] = 0; } } // Form boundary rectangles at Level 1. // Place the top left hand corner of the largest square tile in each of the positions within the top left hand quarter of the boundary rectangle. s = (A - tileSize) / 2 + 1; t = (B - tileSize) / 2 + 1; Level++; for (y = 0; y < t; y++) { for (x = 0; x < s; x++) { // Initialise rectangle. for (j = 0; j < B; j++) { for (i = 0; i < A; i++) { Rectangle[i][j] = ListOfRectangles[LevelFirstIndex[Level - 1]][i][j]; } } for (j = y; j < y + tileSize; j++) { for (i = x; i < x + tileSize; i++) { Rectangle[i][j] = tileSize; } } /* for (j = 0; j < B; j++) { for (i = 0; i < A; i++) { OpFile << " " << Rectangle[i][j]; } OpFile << endl; } OpFile << endl; */ // Record square. RectangleIndex++; if ((x == 0) && (y == 0)) { LevelFirstIndex[Level] = RectangleIndex; } for (j = 0; j < B; j++) { for (i = 0; i < A; i++) { ListOfRectangles[RectangleIndex][i][j] = Rectangle[i][j]; } } LevelLastIndex[Level] = RectangleIndex; } } // Form rectangles at other levels. numTiles = (A / tileSize) * (B / tileSize); if (numTiles > MaxNumTiles) numTiles = MaxNumTiles; for (i = 2; i <= numTiles; 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 < B; l++) { for (k = 0; k < A; k++) { flagRectangle[k][l] = ListOfRectangles[m][k][l]; } } // Find the next empty cell in the rectangle. findNextEmptyCell: emptyCell = false; for (l = 0; l < B; l++) { for (k = 0; k < A; k++) { if (flagRectangle[k][l] == 0) { emptyCell = true; x = l; y = k; break; } } if (emptyCell == true) break; } if (emptyCell == true) { // Try to fit part into rectangle with the empty cell corresponding to the top left-hand corner of the part. if ((y + tileSize <= A) && (x + tileSize <= B)) { empty = 0; for (l = x; l < x + tileSize; l++) { for (k = y; k < y + tileSize; k++) { if (flagRectangle[k][l] == 0) { empty++; } } } if (empty == tileSize * tileSize) { // Part fits, so fit it. RectangleIndex++; if (firstTile == false) { LevelFirstIndex[Level] = RectangleIndex; firstTile = true; } for (l = 0; l < B; l++) { for (k = 0; k < A; k++) { Rectangle[k][l] = ListOfRectangles[m][k][l]; } } for (l = x; l < x + tileSize; l++) { for (k = y; k < y + tileSize; k++) { Rectangle[k][l] = tileSize; } } /* for (l = 0; l < B; l++) { for (k = 0; k < A; k++) { OpFile << " " << Rectangle[k][l]; } OpFile << endl; } OpFile << endl; */ // Check that a transformation of this rectangle does not already exist at this level. transformExists = matchTransformations(); if (transformExists == true) { flagRectangle[y][x] = -4; // Set flag to indicate that a fit was successful at this cell, but do not put boundary rectangle in list. RectangleIndex--; goto findNextEmptyCell; } for (l = 0; l < B; l++) { for (k = 0; k < A; k++) { ListOfRectangles[RectangleIndex][k][l] = Rectangle[k][l]; } } flagRectangle[y][x] = -2; // Flag fit successful at this cell. LevelLastIndex[Level] = RectangleIndex; cout << NumTreesBuilt << " " << Level << " " << RectangleIndex << " " << m << " " << LevelLastIndex[Level - 1] << endl; /* for (l = 0; l < B; l++) { for (k = 0; k < A; k++) { OpFile << " " << Rectangle[k][l]; } OpFile << " "; for (k = 0; k < A; k++) { OpFile << " " << flagRectangle[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. flagRectangle[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. flagRectangle[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("SquarePlacementsInRectangle.txt", ios_base::out | ios_base::trunc); // Get dimensions of rectangle. cout << "Enter A "; cin >> A; if ((A < MinA) || (A > MaxA)) { OpFile << "Value of A " << A << " out of range." << endl; return 1; } OpFile << "A = " << A << endl; cout << "Enter B "; cin >> B; if ((B < MinB) || (B > MaxB) || (B > A)) { OpFile << "Value of B " << B << " out of range." << endl; return 1; } OpFile << "B = " << B << endl; AB = A * B; cout << "Enter minimum tile side size "; cin >> MinTileSideSize; if ((MinTileSideSize < 1) || (MinTileSideSize > B)) { OpFile << "Value of MinTileSideSize " << MinTileSideSize << " out of range." << endl; return 1; } cout << "Enter maximum number of tiles to be placed "; cin >> MaxNumTiles; if (MaxNumTiles < 1) { OpFile << "Value of MaxNumTiles " << MaxNumTiles << " out of range." << endl; return 1; } else if (MaxNumTiles > (A / MinTileSideSize) * (B / MinTileSideSize)) { MaxNumTiles = (A / MinTileSideSize) * (B / MinTileSideSize); } // Allocate memory for list of squares for use in buildTree. ListOfRectangles = (short int ***)malloc(MaxS * sizeof(short int **)); for (i = 0; i < MaxS; i++) { ListOfRectangles[i] = (short int **)malloc(A * sizeof(short int *)); } for (j = 0; j < A; j++) { for (i = 0; i < MaxS; i++) { ListOfRectangles[i][j] = (short int *)malloc(B * sizeof(short int)); } } buildTree(); // Release memory. for (j = 0; j < A; j++) { for (i = 0; i < MaxS; i++) { free(ListOfRectangles[i][j]); } } for (i = 0; i < MaxS; i++) { free(ListOfRectangles[i]); } free(ListOfRectangles); // Output stats. OpFile << endl; OpFile << "Tile side length = "; for (i = 1; i <= NumTreesBuilt; i++) { OpFile << i + MinTileSideSize - 1 << " "; } OpFile << endl << endl; OpFile << "NumMatchIdentity = "; for (i = 1; i <= NumTreesBuilt; i++) { OpFile << NumMatchIdentity[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 << "NumMatchRotate180 = "; for (i = 1; i <= NumTreesBuilt; i++) { OpFile << NumMatchRotate180[i] << " "; } OpFile << endl; OpFile << "NumMatchless = "; for (i = 1; i <= NumTreesBuilt; i++) { OpFile << NumMatchless[i] << " "; } OpFile << endl << endl; OpFile << "Program complete" << endl; return 0; }