Solutions by Lance Gay, Erich Friedman, and Antony Boucher.

1 {{1}}
2 {{1,1},{1,1}}
3 {{2,1},{1},{1,1,1}}
4 {{2,2},{2,1,1},{1,1}}
5 {{3,2},{1,1},{2,1,2},{1}}
6 {{3,3},{3,2,1},{1},{1,1,1}}
7 {{4,3},{1,2},{3,1,1},{2,2}}
8 {{4,4},{4,2,2},{2,1,1},{1,1}}
9 {{5,4},{1,1,2},{4,2,1},{3},{2}}
10 {{5,5},{5,3,2},{1,1},{2,1,2},{1}}
11 {{6,5},{1,1,3},{5,1,2},{1},{3,3}}
12 {{7,5},{2,3},{5,2,1,1},{1,4},{3}}
13 {{7,6},{2,4},{6,1},{3},{1,3},{2,2}}
14 {{7,7},{7,4,3},{1,2},{3,1,1},{2,2}}
15 {{8,7},{1,3,3},{7,2},{2,1,5},{1},{3}}
16 {{9,7},{2,5},{7,4},{1,4},{3,1,1},{2}}
17 {{9,8},{1,3,4},{8,2},{2,2,1},{5},{4}}
18 {{9,9},{9,5,4},{1,1,2},{4,2,1},{3},{2}}
19 {{10,9},{1,1,2,5},{9,2,1},{3},{2},{5,5}}
20 {{11,9},{2,7},{9,4},{2,1,1},{1},{4,4},{3}}
21 {{11,10},{1,3,6},{10,2},{5},{1,5},{1},{3,3}}
22 {{12,10},{3,7},{10,1,1},{5},{2,5},{4,1},{3}}
23 {{12,11},{1,3,7},{11,2},{5},{2,5},{4,1},{3}}
24 {{12,12},{12,7,5},{2,3},{5,2,1,1},{1,4},{3}}
25 {{14,11},{3,8},{11,6},{1,1,6},{5,2,1},{1},{3}}
26 {{13,13},{13,7,6},{2,4},{6,1},{3},{1,3},{2,2}}
27 {{14,13},{2,4,7},{13,1},{3},{1,3},{2,2},{7,7}}
28 {{15,13},{1,5,7},{1},{13,3},{3,3,2},{1,8},{7}}
29 {{15,14},{1,3,3,7},{14,2},{5,3},{2,1},{8},{7}}
30 {{15,15},{15,8,7},{1,3,3},{7,2},{2,1,5},{1},{3}}
31 {{16,15},{2,5,8},{15,1},{3},{3,3,2},{1,1},{8,8}}
32 {{16,16},{16,9,7},{2,5},{7,4},{1,4},{3,1,1},{2}}
33 {{18,15},{2,4,9},{2},{15,2,1},{1,1,5},{4},{9,9}}
34 {{17,17},{17,9,8},{1,3,4},{8,2},{2,2,1},{5},{4}}
35 {{15,10,10},{8,12},{12,3},{7,4},{3,13},{10},{4,8},{4}}
36 {{19,17},{4,7,6},{17,2},{6},{3,3},{3,2,2},{10},{9}}
37 {{19,18},{2,5,11},{18,1},{3},{8},{3,8},{6,1,1},{5}}
38 {{21,17},{8,9},{17,4},{6,5,1},{4,6},{1,8},{7},{6}}
39 {{20,8,11},{5,3},{2,12},{7},{19,8},{5,7},{11,2},{9}}
40 {{20,20},{20,11,9},{2,7},{9,4},{2,1,1},{1},{4,4},{3}}
41 {{23,18},{7,11},{18,3,2},{1,5,3},{4},{2,1},{12},{11}}
42 {{21,21},{21,11,10},{1,3,6},{10,2},{5},{1,5},{1},{3,3}}
43 {{22,21},{2,5,7,7},{21,1},{3},{3,3,2},{1,15},{7},{7}}
44 {{22,22},{22,12,10},{3,7},{10,1,1},{5},{2,5},{4,1},{3}}
45 {{24,21},{5,4,12},{21,2,1},{1},{1,3},{7,2},{5},{12,12}}
46 {{23,23},{23,12,11},{1,3,7},{11,2},{5},{2,5},{4,1},{3}}
47 {{24,23},{1,3,7,12},{23,2},{5},{2,5},{4,1},{3},{12,12}}
48 {{28,20},{7,5,8},{2,3},{9},{20,8},{11},{12,5},{2,9},{7}}
49 {{26,23},{2,2,6,13},{1,3},{23,4},{2,1},{7},{6},{13,13}}
50 {{28,22},{4,5,13},{1,2,1},{1,6},{22,9},{4,2},{15},{13}}
51 {{22,14,15},{13,1},{16},{13,9},{9,4},{4,5},{20},{16,1},{15}}
52 {{28,24},{7,9,8},{24,4},{1,6},{5},{1,7},{4,6},{15},{13}}
53 {{29,24},{6,5,13},{24,4,1},{5},{3,4},{7},{6,3},{16},{13}}
54 {{27,27},{27,14,13},{2,4,7},{13,1},{3},{1,3},{2,2},{7,7}}
55 {{28,27},{2,4,7,14},{27,1},{3},{1,3},{2,2},{7,7},{14,14}}
56 {{28,28},{28,15,13},{1,5,7},{1},{13,3},{3,3,2},{1,8},{7}}
57 {{30,27},{5,7,15},{27,2,1},{1},{3,3,2},{1,8},{7},{15,15}}
58 {{29,29},{29,15,14},{1,3,3,7},{14,2},{5,3},{2,1},{8},{7}}
59 {{30,29},{2,5,7,15},{29,1},{3},{3,3,2},{1,8},{7},{15,15}}
60 {{32,28},{2,3,7,16},{1,1},{1,4},{28,5},{2,9},{7},{16,16}}
61 {{32,29},{1,1,8,7,12},{2},{29,5},{2,5},{12,1},{3},{20},{12}}
62 {{33,29},{4,5,20},{29,7,1},{6},{13},{7,13},{9,4},{1,6},{5}}
63 {{34,29},{4,8,17},{2,2},{29,4,1},{3,2},{1,9},{8},{17,17}}
64 {{36,28},{9,8,11},{28,8},{3,5},{7,2},{5},{2,9},{7},{20},{16}}
65 {{33,32},{1,3,8,20},{32,2},{5},{13},{2,5,13},{12,1},{3},{8}}
66 {{35,31},{8,10,13},{31,4},{12},{7,3},{4,12},{3,8},{15},{10,10}}
67 {{39,28},{12,7,9},{5,2},{11},{28,8,3},{2,7,8},{5},{20},{19}}
68 {{36,32},{8,9,15},{32,4},{11,1},{10},{4,11},{17,8},{1,10},{9}}
69 {{39,30},{7,12,11},{2,5},{30,11},{3,8},{8,7,2},{5},{20},{19}}
70 {{38,32},{6,9,17},{32,8,4},{1,8},{5},{7,1},{6},{4,21},{17}}
71 {{36,35},{1,3,4,9,18},{35,2},{2,2,1},{5},{4},{9,9},{18,18}}
72 {{36,36},{36,19,17},{4,7,6},{17,2},{6},{3,3},{3,2,2},{10},{9}}
73 {{42,31},{10,21},{1,3,6},{31,10,2},{5},{1,5},{1},{3,3},{21,21}}
74 {{37,37},{37,19,18},{2,5,11},{18,1},{3},{8},{3,8},{6,1,1},{5}}
75 {{39,36},{3,3,7,7,16},{36,9},{5,9},{11,3},{3},{2,23},{5},{16}}
76 {{40,36},{4,3,9,20},{1,2},{36,7,1,1},{4},{2,11},{9},{20,20}}
77 {{40,37},{3,6,10,18},{37,3,3},{8,4},{6,8},{8},{6},{4,22},{18}}
78 {{39,39},{39,20,8,11},{5,3},{2,12},{7},{19,8},{5,7},{11,2},{9}}
79 {{42,37},{3,3,10,21},{1,5},{1},{37,6},{3,2},{1,11},{10},{21,21}}
80 {{44,36},{8,28},{36,16},{9,7},{5,7,16},{2,5},{11},{3,2},{9},{8}}
81 {{46,35},{12,23},{35,7,3,1},{2,11},{5},{5,2},{1,4},{3},{23,23}}
82 {{47,35},{12,23},{35,12,5,7},{3,2},{1,5,3},{4},{2,1},{24},{23}}
83 {{44,39},{3,4,10,22},{2,1},{5},{39,7},{3,1,1},{12},{10},{22,22}}
84 {{44,40},{7,13,20},{40,4},{1,6},{5},{11,6,7},{5,1},{4,24},{20}}
85 {{46,39},{9,11,19},{39,7},{7,2},{5,8},{5,2},{3,11},{8},{27},{19}}
86 {{47,39},{7,5,8,19},{2,3},{9},{39,8},{11},{12,5},{2,28},{7},{19}}
87 {{48,39},{7,12,20},{2,5},{39,11},{9,8},{8,3},{28},{2,7},{5},{20}}
88 {{50,38},{15,23},{38,8,4},{1,6,8},{5},{7,1},{6,6},{4,27},{23}}
89 {{48,41},{5,5,11,20},{2,8},{41,9},{2,9},{3,7},{12},{8,28},{20}}
90 {{49,41},{8,12,21},{41,9,7},{3,9},{2,8},{11},{2,28},{5,5},{21}}
91 {{52,39},{15,24},{39,7,6},{4,6,5},{1,9},{8},{1,4},{7},{28},{24}}
92 {{46,46},{46,23,23},{23,12,11},{1,3,7},{11,2},{5},{2,5},{4,1},{3}}
93 {{48,45},{5,4,12,24},{45,2,1},{1},{1,3},{7,2},{5},{12,12},{24,24}}
94 {{47,47},{47,24,23},{1,3,7,12},{23,2},{5},{2,5},{4,1},{3},{12,12}}
95 {{48,47},{2,5,4,12,24},{47,1},{3},{1,3},{7,2},{5},{12,12},{24,24}}
96 {{48,48},{48,28,20},{7,5,8},{2,3},{9},{20,8},{11},{12,5},{2,9},{7}}
97 {{52,45},{6,13,26},{2,4},{45,6,1},{3},{1,3},{2,2},{13,13},{26,26}}
98 {{49,49},{49,26,23},{2,2,6,13},{1,3},{23,4},{2,1},{7},{6},{13,13}}
99 {{56,43},{7,8,28},{3,3,1},{2,7},{3,5},{43,15,1},{1},{13},{28,28}}
100 {{58,42},{5,5,11,21},{7,3},{3},{4,10},{4,3},{1,6},{42,21},{37},{21}}
126 {{68,58},{11,15,32},{58,9,1},{8,4},{10,9},{17},{1,8},{11},{4,36},{32}}
216 {{126,90},{32,58},{4,11,17},{90,32,8},{1,10},{9},{8,9},{15,4},{11,1},{68},{58}}
265 {{93,86,86},{28,51,93},{72,21},{25,24},{1,1,49},{1,25},{26},{2,23},{100},{7,86},{79}}

Code by Antony Boucher

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>


#define NMAX 100
#define LMAX 1000


int n;                          /* grid size */
int cell[NMAX][NMAX];           /* grid */

int nbSquareN[NMAX+1];          /* number of squares for each size */
int maxDups;                    /* maximum authorized number of identical squares */

int square[LMAX];               /* list of squares in the grid */
int prm;                        /* number of squares in the grid */
int prmGoal;                    /* number of squares to reach */

int currSol[LMAX];              /* list of squares of current solution */
int prmCurrSol;                 /* number of squares of current solution */

int bestSol[NMAX+1][LMAX];      /* list of solutions */
int prmBestSol[NMAX+1];         /* list of solutions' sizes */

int relPrime[NMAX+1][NMAX+1];   /* pre-computed table for relatively-prime tests */
int order[NMAX+1][NMAX+1];      /* pre-computed ordered square size tests */


clock_t chrono;
char strChrono[20];


void compOrder () {
	int i,j;
	memset(order,0,sizeof(order));
	for (i=1; i<=NMAX; i++) {
		order[i][0] = i;
		for (j=1; j<i; j++) {
			order[i][j] = ((i+j)%2?(i-j+1)/2:(i+j)/2);
		}
	}
}

void compRelPrime () {
	int i,j,k;
	for (j=1; j<=NMAX; j++) {
		for (i=1; i<=j; i++) {
			relPrime[i][j] = 1;
			for (k=2; k<=j; k++) {
				if (!(i%k) && !(j%k)) {
					relPrime[i][j] = 0;
					break;
				}
			}
		}
	}
}

void timeReset () {
	chrono = clock();
}

char* timeCheck () {
	double temps = (double)(clock() - chrono) / (double)(CLOCKS_PER_SEC);
	sprintf(strChrono, "%02.0lf:%02.0lf:%02.0lf.%02.0lf",
		floor(temps/3600),
		floor(temps/60) - 60 * floor(temps/3600),
		floor(temps) - 60 * floor(temps/60),
		floor(temps*100) - 100*floor(temps));
	return strChrono;
}

void print (int n, int liste[], int prm) {
	int i;
	printf("n=%2d t=%s nb=%2d: ", n, timeCheck(), prm);
	for (i=0; i<prm; i++)
		printf("%2d ", liste[i]);
	printf("\n");
}

void complete (int x, int y) {
	/* x,y : coordinates of next empty cell */

	int i, j;       /* loops */
	int x2, y2;     /* next empty cell after new square insertion */
	int z;          /* new square size */
	int room = 1;   /* room available for new squares */
	int found;      /* next empty cell found? */
	int zmin;       /* smallest square size of the candidate solution */
	int *p, *pz;

	if (    prm<=3
	     && (    prm==1
	          && (    square[0]<=n/3         /* Heuristic : first square is bigger than 1/3 */
	               || square[0]>2*n/3        /* Heuristic : first square is smaller than 2/3 */
	             )
	          || prm==2
	          && (    y==0                   /* Heuristic : no more than 2 squares on first row */
	               || square[0]+square[1]==n /* we don't process symetrical cases */
	               && square[0]<square[1]
	             )
	          || prm==3                      /* Note: only useful when prm==2 heuristics are disabled */
	          && (    y==0                   /* Heuristic : no more than 3 squares on first row */
	               || square[0]+square[1]<n  /* we don't process symetrical cases */
	               && square[0]<square[2]
	             )
	        )
	   )
		return;

	/* compute room available */
	z = n - (x>y?x:y);
	p = &cell[y][x+1];
	while ((room < z) && (!(*(p++))))
		room++;

	/* we try all valid-sized squares in (x,y), in pre-computed order */
	for (pz=&order[room][0]; (z=*(pz++))>0; ) {

		if (   nbSquareN[z]>=maxDups    /* Heuristic : no more than 3 identical squares (for N>10) */
		    || x==0 && y!=0             /* Heuristic : if 2 squares on first row, then 2 squares on first column */
		    && square[0]+square[1]==n
		    && z!=square[1]             
		   )
			continue;

		/* add new square to the list */
		square[prm] = z;
		nbSquareN[z]++;
		prm++;

		/* add new square to the grid */
		for (j=y+z-1; j>y; j--) {
			cell[j][x] = z;
		}

		/* look up for next empty cell, in 2 steps */
		/* row y */
		found = 0;
		for (x2=x+z; x2<n; ) {
			if (!(i=cell[y][x2])) {
				y2 = y;
				found = 1;
				break;
			} else {
				x2 += i;
			}
		}
		/* next rows */
		if (!found) {
			for (y2=y+1; y2<n; y2++) {
				for (x2=0; x2<n; ) {
					if (!(i=cell[y2][x2])) {
						found = 1;
						break;
					} else {
						x2 += i;
					}
				}
				if (found) break;
			}
		}

		/* if grid is full, check and save solution, else recurse */
		if (y2==n) {
			/* we will save only if solution is relatively prime */
			/* find smallest square size */
			zmin = square[0];
			for (i=1; i<prm; i++) {
				if (square[i]<zmin) {
					zmin = square[i];
				}
			}
			/* is it relatively prime to all square sizes? */
			found = 0;
			for (i=0; i<prm; i++) {
				if (relPrime[zmin][square[i]]) {
					found = 1;
					break;
				}
			}
			/* save the solution */
			if (found) {
				memcpy(currSol, square, sizeof(square));
				prmCurrSol = prm;
			}
		} else if (prm+1<prmCurrSol && prmCurrSol>prmGoal) {
				complete(x2, y2);
		}

		/* remove square from list */
		nbSquareN[z]--;
		prm--;

		/* remove square from grid */
		for (j=y+z-1; j>y; j--) {
			cell[j][x] = 0;
		}
	}
}

int main () {
	int i, n1, o1;

	compRelPrime();
	compOrder();
	memset(prmBestSol, 0, sizeof(prmBestSol));

	/* size-1 solution */
	bestSol[1][0] = 1;
	prmBestSol[1] = 1;

	/* size-2 solution */
	bestSol[2][0] = 1; bestSol[2][1] = 1;
	bestSol[2][2] = 1; bestSol[2][3] = 1;
	prmBestSol[2] = 4;

	/* size-3 solution */
	bestSol[3][0] = 2; bestSol[3][1] = 1; bestSol[3][2] = 1;
	bestSol[3][3] = 1; bestSol[3][4] = 1; bestSol[3][5] = 1;
	prmBestSol[3] = 6;

	/* ask for starting values */
	printf("Size: ");
	scanf("%d",&n1);
	printf("\n");
	if (n1<=30 || n1>200) {
		n1=4;
	} else {
		printf("Order: ");
		scanf("%d",&o1);
		printf("\n");
		if (o1<14) o1=14;
		for (i=n1-3; i<n1; i++) {
			prmBestSol[i] = o1;
		}
	}
	
	/* next solutions */
	for (n=n1; n<=NMAX; n++) {

		/* empty the grid */
		memset(cell,0,sizeof(cell));
		memset(nbSquareN, 0, sizeof(nbSquareN));
		maxDups = (n>10 ? 3 : 50);

		/* Heuristic : solution size should be median size of 3 previous ones, or +1 */
		/* Note : this is because the list of orders is 'almost' increasing (size-41 case) */
		prmGoal = (prmBestSol[n-3]+prmBestSol[n-2]+prmBestSol[n-1]+1)/3;
		prmCurrSol = (n>10 ? prmGoal+2 : 50);

		/* fill the grid */
		timeReset();
		complete(0, 0);
		print(n, currSol, prmCurrSol);

		/* save the solution */
		memcpy(bestSol[n], currSol, sizeof(currSol));
		prmBestSol[n] = prmCurrSol;
	}
	return 0;
}