// See http://www.iwriteiam.nl/D1802.html#10 for explaination

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

void generateExactCover()
{
    for (int p = 0; p < 16; p++)
    {
        bool tl = (p & 8) != 0;
        bool tr = (p & 4) != 0;
        bool bl = (p & 2) != 0;
        bool br = (p & 1) != 0;
        for (int y = 0; y < 4; y++)
            for (int x = 0; x < 4; x++)
                if (p != 0 || (x == 0 && y == 0))
                {
                    for (int i = 0; i < 16; i++)
                        printf("%c", p == i ? '1' : '0');
                    for (int i = 0; i < 16; i++)
                        printf("%c", x + 4*y == i ? '1' : '0');
                    for (int y1 = 0; y1 < 4; y1++)
                        for (int x1 = 1; x1 < 4; x1++)
                            if (x1 == x + 1 && y1 == y)
                                printf("%c%c", tr ? '0' : '1', br ? '0' : '1');
                            else if (x1 == x && y1 == y)
                                printf("%c%c", tl ? '1' : '0', bl ? '1' : '0');
                            else
                                printf("00");
                    for (int y1 = 1; y1 < 4; y1++)
                        for (int x1 = 0; x1 < 4; x1++)
                            if (x1 == x && y1 == y + 1)
                                printf("%c%c", bl ? '0' : '1', br ? '0' : '1');
                            else if (x1 == x && y1 == y)
                                printf("%c%c", tl ? '1' : '0', tr ? '1' : '0');
                            else
                                printf("00");
                        
                    printf(" %d at %d,%d\n", p, x, y);
                }
    }
}

#define ELEM(V,I) (((V) & (1 << (I))) != 0 ? 1 : 0)

void tryAll(bool output_json)
{
    int matching[17];
    for (int i = 0; i < 17; i++)
        matching[i] = 0;
    int extra[16];
    for (int i = 0; i < 16; i++)
        extra[i] = 0;
    
    for (int s = 0; s < (1 << 25); s++)
        if (ELEM(s,0) == 0 && ELEM(s,1) == 0 && ELEM(s,5) == 0 && ELEM(s,6) == 0)
        {
            int count[16];
            for (int i = 0; i < 16; i++)
                count[i] = 0;
            
            for (int x = 0; x < 4; x++)
                for (int y = 0; y < 4; y++)
                {
                    int p = x + 5*y;
                    int v = (ELEM(s,p)   ? 8 : 0) 
                          | (ELEM(s,p+1) ? 4 : 0) 
                          | (ELEM(s,p+5) ? 2 : 0) 
                          | (ELEM(s,p+6) ? 1 : 0);
                    count[v]++;
                }
            int m = 0;
            for (int i = 0; i < 16; i++)
                if (count[i] > 0)
                    m++;
            matching[m]++;
            if (m == 16)
            {
                if (output_json)
                {
                    for (int y = 0; y < 4; y++)
                        for (int x = 0; x < 4; x++)
                        {
                            int p = x + 5*y;
                            if (p > 0)
                            {
                                int v = (ELEM(s,p)   ? 8 : 0) 
                                      | (ELEM(s,p+1) ? 4 : 0) 
                                      | (ELEM(s,p+5) ? 2 : 0) 
                                      | (ELEM(s,p+6) ? 1 : 0);
                                printf("%s%d", p == 1 ? "\t[" : ",",v);
                            }
                        }
                    printf("],");
                }
                else
                {
                    for (int y = 0; y < 5; y++)
                    {
                        for (int x = 0; x < 5; x++)
                            printf("%d", ELEM(s, x + 5*y));
                        printf("\n");
                    }
                    printf("\n");
                    for (int y = 0; y < 4; y++)
                    {
                        for (int x = 0; x < 4; x++)
                        {
                            int p = x + 5*y;
                            int v = (ELEM(s,p)   ? 8 : 0) 
                                  | (ELEM(s,p+1) ? 4 : 0) 
                                  | (ELEM(s,p+5) ? 2 : 0) 
                                  | (ELEM(s,p+6) ? 1 : 0);
                            printf("%x", v);
                        }
                        printf("\n");
                    }
                }
                printf("\n");
            }    
        }
    
    if (!output_json)
        for (int i = 1; i <= 16; i++)
            printf("%2d: %6d\n", i, matching[i]);
}

int main(int argc, char *argv[])
{
    if (argc >= 2 && strcmp(argv[1], "EC") == 0)
        generateExactCover();
    else
        tryAll(argc >= 2 && strcmp(argv[1], "js") == 0);
    
    return 0;
}