How many draws are there in Quarto? Introduction
This challenge is similar to Project Euler problems. I came up with it because I was playing a deceivingly simple board game and couldn't come up with an efficient solution to answer a simple question about its mechanics.
Quarto is a fun variant of 4 in a row. It is played on a 4 by 4 board with 16 unique pieces (no pieces are duplicated). Every turn each player places 1 piece on the board. Each piece has 4 binary characteristics (short/tall, black/white, square/circular, hollow/solid). The goal is to make four in a row, either horizontally, vertically or along the 2 diagonals, for any of the four characteristics! So 4 black pieces, 4 white pieces, 4 tall pieces, 4 short pieces, 4 square pieces, 4 circular pieces, 4 hollow pieces or 4 solid pieces.

The picture above shows a finished game, there is a four in a row because of 4 square pieces.
Challenge
In Quarto, some games may end in a draw.
The total number of possible end positions is 16!, about 20 trillion.
How many of those end positions are draws?
Rules

The solution must be a program that calculates and outputs the total number of end positions that are draws. The correct answer is 414298141056

You may only use information of the rules of the game that have been deduced manually (no computer assisted proof).

Mathematical simplifications of the problem are allowed, but must be explained and proven (manually) in your solution.

The winner is the one with the most optimal solution in terms of CPU running time.

To determine the winner, I will run every single solution with a reported running time of less than 30m on a MacBook Pro 2,5 GHz Intel Core i7 with 16 GB RAM.

No bonus points for coming up with a solution that also works with other board sizes. Even though that would be nice.

If applicable, your program must compile within 1 minute on the hardware mentioned above (to avoid compiler optimization abuse)

Default loopholes are not allowed


Submissions
Please post:

The code or a github/bitbucket link to the code.
The output of the code.
Your locally measured running time
An explanation of your approach.

Deadline
The deadline for submissions is March 1st, so still plenty of time.
C: 414298141056 draws found in about 5 2.5 minutes.
Just simple depth-first search with a symmetry-aware transposition table. We use the symmetry of attributes under permutation and the 8-fold dihedral symmetry of the board.
#include &lt;stdint.h&gt;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;stdbool.h&gt;
#include &lt;string.h&gt;

typedef uint16_t u8;
typedef uint16_t u16;
typedef uint64_t u64;

#define P(i, j) (1 &lt;&lt; (4 * (i) + (j)))

#define DIAG0 (P(0, 0) | P(1, 1) | P(2, 2) | P(3, 3))
#define DIAG1 (P(3, 0) | P(2, 1) | P(1, 2) | P(0, 3))

u64 rand_state;

u64 mix(u64 x) {
    u64 a = x &gt;&gt; 32;
    u64 b = x &gt;&gt; 60;
    x ^= (a &gt;&gt; b);
    return x * 7993060983890856527ULL;
}

u64 rand_u64() {
    u64 x = rand_state;
    rand_state = x * 6364136223846793005ULL + 1442695040888963407ULL;
    return mix(x);
}

u64 ZOBRIST_TABLE[(1 &lt;&lt; 16)][8];

u16 transpose(u16 x) {
    u16 t = 0;
    for (int i = 0; i &lt; 4; i++) {
        for (int j = 0; j &lt; 4; j++) {
            if (x &amp; P(j, i)) {
                t |= P(i, j);
            }
        }
    }
    return t;
}

u16 rotate(u16 x) {
   u16 r = 0;
   for (int i = 0; i &lt; 4; i++) {
       for (int j = 0; j &lt; 4; j++) {
           if (x &amp; P(3 - j, i)) {
                r |= P(i, j);
            }
       }
   } 
   return r;
}

void initialize_zobrist_table(void) {
    for (int i = 0; i &lt; 1 &lt;&lt; 16; i++) {
        ZOBRIST_TABLE[i][0] = rand_u64();
    }
    for (int i = 0; i &lt; 1 &lt;&lt; 16; i++) {
        int j = i;
        for (int r = 1; r &lt; 8; r++) {
            j = rotate(j);
            if (r == 4) {
                j = transpose(i);
            }
            ZOBRIST_TABLE[i][r] = ZOBRIST_TABLE[j][0];
        }
    }
}

u64 hash_board(u16* x) {
    u64 hash = 0;
    for (int r = 0; r &lt; 8; r++) {
        u64 h = 0;
        for (int i = 0; i &lt; 8; i++) {
            h += ZOBRIST_TABLE[x[i]][r];
        }
        hash ^= mix(h);
    }
    return mix(hash);
}

u8 IS_WON[(1 &lt;&lt; 16) / 8];

void initialize_is_won(void) {
    for (int x = 0; x &lt; 1 &lt;&lt; 16; x++) {
        bool is_won = false;
        for (int i = 0; i &lt; 4; i++) {
            u16 stride = 0xF &lt;&lt; (4 * i);
            if ((x &amp; stride) == stride) {
                is_won = true;
                break;
            }
            stride = 0x1111 &lt;&lt; i;
            if ((x &amp; stride) == stride) {
                is_won = true;
                break;
            }
        }
        if (is_won == false) {
            if (((x &amp; DIAG0) == DIAG0) || ((x &amp; DIAG1) == DIAG1)) {
                is_won = true;
            }
        }
        if (is_won) {
            IS_WON[x / 8] |= (1 &lt;&lt; (x % 8));
        }
    }
}

bool is_won(u16 x) {
    return (IS_WON[x / 8] &gt;&gt; (x % 8)) &amp; 1;
}

bool make_move(u16* board, u8 piece, u8 position) {
    u16 p = 1 &lt;&lt; position;
    for (int i = 0; i &lt; 4; i++) {
        bool a = (piece &gt;&gt; i) &amp; 1;
        int j = 2 * i + a;
        u16 x = board[j] | p;
        if (is_won(x)) {
            return false;
        }
        board[j] = x;
    }
    return true;
}

typedef struct {
    u64 hash;
    u64 count;
} Entry;

typedef struct {
    u64 mask;
    Entry* entries;
} TTable;

Entry* lookup(TTable* table, u64 hash, u64 count) {
    Entry* to_replace;
    u64 min_count = count + 1;
    for (int d = 0; d &lt; 8; d++) {
        u64 i = (hash + d) &amp; table-&gt;mask;
        Entry* entry = &amp;table-&gt;entries[i];
        if (entry-&gt;hash == 0 || entry-&gt;hash == hash) {
            return entry;
        }
        if (entry-&gt;count &lt; min_count) {
            min_count = entry-&gt;count;
            to_replace = entry;
        }
    }
    if (to_replace) {
        to_replace-&gt;hash = 0;
        to_replace-&gt;count = 0;
        return to_replace;
    }
    return NULL;
}

u64 count_solutions(TTable* ttable, u16* board, u8* pieces, u8 position) {
    u64 hash = 0;
    if (position &lt;= 10) {
        hash = hash_board(board);
        Entry* entry = lookup(ttable, hash, 0);
        if (entry &amp;&amp; entry-&gt;hash) {
            return entry-&gt;count;        
        }
    }
    u64 n = 0;
    for (int i = position; i &lt; 16; i++) {
        u8 piece = pieces[i];
        u16 board1[8];
        memcpy(board1, board, sizeof(board1));
        u8 variable_ordering[16] = {0, 1, 2, 3, 4, 8, 12, 6, 9, 5, 7, 13, 10, 11, 15, 14};
        if (!make_move(board1, piece, variable_ordering[position])) {
            continue;
        }
        if (position == 15) {
            n += 1;
        } else {
            pieces[i] = pieces[position];
            n += count_solutions(ttable, board1, pieces, position + 1); 
            pieces[i] = piece;
        }
    }
    if (hash) {
        Entry* entry = lookup(ttable, hash, n);
        if (entry) {
            entry-&gt;hash = hash;
            entry-&gt;count = n;
        }
    }
    return n;
}

int main(void) {
    TTable ttable;
    int ttable_size = 1 &lt;&lt; 28;
    ttable.mask = ttable_size - 1;
    ttable.entries = calloc(ttable_size, sizeof(Entry));
    initialize_zobrist_table();
    initialize_is_won();
    u8 pieces[16];
    for (int i = 0; i &lt; 16; i++) {pieces[i] = i;}
    u16 board[8] = {0};
    printf(&quot;count: %lu\n&quot;, count_solutions(&amp;ttable, board, pieces, 0));
}

Measured score (@wvdz):
$ clang -O3 -march=native quarto_user1502040.c
$ time ./a.out
count: 414298141056

real    1m37.299s
user    1m32.797s
sys     0m2.930s

Score (user+sys): 1m35.727s