​Challenge #326 [Hard] Multifaceted alphabet blocks

blocks.c

/* [2017-08-11] Challenge #326 [Hard] Multifaceted alphabet blocks
 * https://redd.it/6t0zua
 */
#include <stdio.h>
#include <string.h>

#define N (1024ul * 1024ul)

static int
find(char blocks[][33], int n, unsigned long used, const char *word)
{
    if (*word < 'a' || *word > 'z')
        return 1;
    else
        for (int i = 0; i < n; i++)
            if (!((used >> i) & 1) && strchr(blocks[i], *word))
                if (find(blocks, n, used | (1ul << i), word + 1))
                    return 1;
    return 0;
}

int
main(void)
{
    size_t nhist = 0;
    static char hist[N][26];
    static char words[N][32];

    /* Read words into a histogram */
    for (; fgets(words[nhist], sizeof(words[nhist]), stdin); nhist++)
        for (char *p = words[nhist]; *p; p++)
            if (*p >= 'a' && *p <= 'z')
                hist[nhist][*p - 'a']++;

    static char blocks[32][33];

    for (int n = 1; ; n++) {
        char used[26] = {0};  // fast set-membership on sides
        static char mark[N];  // mark word as participating in this block
        memset(mark, 0, sizeof(mark));

        for (int s = 0; s < n; s++) {
            /* Gather up current total histogram */
            int alphabet[26] = {0};
            for (size_t i = 0; i < nhist; i++)
                if (!mark[i])
                    for (int j = 0; j < 26; j++)
                        alphabet[j] += hist[i][j];

            /* Greedy search for most common letter */
            int best = 0;
            for (int i = 1; i < 26; i++)
                if (!used[i] && alphabet[i] > alphabet[best])
                    best = i;

            if (!alphabet[best]) {
                /* Nothing left to do */
                blocks[n - 1][s] = 0;
                break;
            } else {
                /* Add letter to block and remove from histograms */
                blocks[n - 1][s] = best + 'a';
                used[best] = 1;
                for (size_t i = 0; i < nhist; i++) {
                    if (!mark[i] && hist[i][best]) {
                        hist[i][best]--;
                        mark[i] = 1;
                    }
                }

                /* Remove words currently solvable. */
                for (size_t i = 0; i < nhist; i++)
                    if (find(blocks, n, 0, words[i]))
                        memset(hist[i], 0, sizeof(hist[i]));
            }
        }

        if (!blocks[n - 1][0])
            break;
        blocks[n - 1][n] = 0;
        puts(blocks[n - 1]);
    }
}