colour.c

/*
 * Imagine a 5x5 grid. We begin coloring in some of the squares on that
 * grid. What is the minimum number of squares we must color in, such
 * that in every row, in every column, and in every 2x2 square grid,
 * there is at least one colored square?
 */
#include <stdio.h>

typedef unsigned grid;

static const grid constraints[26] = {
	/* rows */
	0174000000,	/* 1 111 1/00 000/ 000 00/0 000 0/00 000 */
	0003700000,	/* 0 000 0/11 111/ 000 00/0 000 0/00 000 */
	0000076000,	/* 0 000 0/00 000/ 111 11/0 000 0/00 000 */
	0000001740,	/* 0 000 0/00 000/ 000 00/1 111 1/00 000 */
	0000000037,	/* 0 000 0/00 000/ 000 00/0 000 0/11 111 */
	/* columns */
	0102041020,	/* 1 000 0/10 000/ 100 00/1 000 0/10 000 */
	0041020410,	/* 0 100 0/01 000/ 010 00/0 100 0/01 000 */
	0020410204,	/* 0 010 0/00 100/ 001 00/0 010 0/00 100 */
	0010204102,	/* 0 001 0/00 010/ 000 10/0 001 0/00 010 */
	0004102041,	/* 0 000 1/00 001/ 000 01/0 000 1/00 001 */
	/* boxes */
	0143000000,	/* 1 100 0/11 000/ 000 00/0 000 0/00 000 */
	0061400000,	/* 0 110 0/01 100/ 000 00/0 000 0/00 000 */
	0030600000,	/* 0 011 0/00 110/ 000 00/0 000 0/00 000 */
	0014300000,	/* 0 001 1/00 011/ 000 00/0 000 0/00 000 */
	0003060000,	/* 0 000 0/11 000/ 110 00/0 000 0/00 000 */
	0001430000,	/* 0 000 0/01 100/ 011 00/0 000 0/00 000 */
	0000614000,	/* 0 000 0/00 110/ 001 10/0 000 0/00 000 */
	0000306000,	/* 0 000 0/00 011/ 000 11/0 000 0/00 000 */
	0000061400,	/* 0 000 0/00 000/ 110 00/1 100 0/00 000 */
	0000030600,	/* 0 000 0/00 000/ 011 00/0 110 0/00 000 */
	0000014300,	/* 0 000 0/00 000/ 001 10/0 011 0/00 000 */
	0000006140,	/* 0 000 0/00 000/ 000 11/0 001 1/00 000 */
	0000001430,	/* 0 000 0/00 000/ 000 00/1 100 0/11 000 */
	0000000614,	/* 0 000 0/00 000/ 000 00/0 110 0/01 100 */
	0000000306,	/* 0 000 0/00 000/ 000 00/0 011 0/00 110 */
	0000000143,	/* 0 000 0/00 000/ 000 00/0 001 1/00 011 */
};

static int check(unsigned grid)
{
	int i;

	for (i = 0; i < 26; i++)
		if ((grid & constraints[i]) == 0)
			return (0);

	return (1);
}

static int popcount(unsigned grid)
{
	int i = 0;
	while (grid != 0) {
		grid &= grid - 1;
		i++;
	}

	return (i);
}

extern int main(void)
{
	grid g;
	int pop, best_pop = 26;

	for (g = 0; g < 0200000000; g++) {
		if (!check(g))
			continue;

		pop = popcount(g);
		if (pop <= best_pop) {
			printf("%09o: %2d\n", g, pop);
			best_pop = pop;
		}
	}

	return (0);
}