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

/* Pack squares of size 1..SQUARES into another square of size SIZE.
   This is egregiously inefficient, but the display is quite pretty.
   A better representation would be just a list of the top corners... */

#define SIZE 80
#define SQUARES 28

char buf[SIZE * SIZE * (SQUARES + 1)];
#define at(s, x, y) (s[(x) + (y) * SIZE])

void show(char *s, int hx, int hy) {
	const char *l = ".1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int i, j;
	for (i = 0; i < SIZE; i++) {
		for (j = 0; j < SIZE; j++) {
			printf("%c", (hx == j && hy == i) ? '*' : l[(int) at(s, j, i)]);
		}
		printf("\n");
	}
	printf("\n");
}

void try(char *s, int size) {
	int i, j;
	int r, c;

	printf("\033[H");
	printf("placing size %d...\n", size);
	show(s, -1, -1);

	if (size == 0) {
		printf("done\n");
		show(s, -1, -1);
		exit(0);
	}

	for (i = 0; i < SIZE - size; i++) {
		for (j = 0; j < SIZE - size; j++) {
			int sn = size - 1;
			if (at(s, i, j) != 0
			    || at(s, i + sn, j) != 0
			    || at(s, i, j + sn) != 0
			    || at(s, i + sn, j + sn) != 0)
				goto nothere;
			for (r = 0; r < size; r++) {
				for (c = 0; c < size; c++) {
					if (at(s, i + r, j + c) != 0)
						goto nothere;
				}
			}

			char *n = s - (SIZE * SIZE);
			memcpy(n, s, SIZE * SIZE);
			for (r = 0; r < size; r++) {
				for (c = 0; c < size; c++) {
					at(n, i + r, j + c) = size;
				}
			}
			try(n, size - 1);

			nothere: ;
		}
	}
}

int main(int argc, char **argv) {
	char *s = buf + SIZE * SIZE * SQUARES;
	memset(s, 0, SIZE * SIZE);
	try(s, SQUARES);
	return 0;
}