#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef uint16_t u8;
typedef uint16_t u16;
typedef uint64_t u64;
#define P(i, j) (1 << (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 >> 32;
u64 b = x >> 60;
x ^= (a >> b);
return x * 7993060983890856527ULL;
}
u64 rand_u64() {
u64 x = rand_state;
rand_state = x * 6364136223846793005ULL + 1442695040888963407ULL;
return mix(x);
}
u64 ZOBRIST_TABLE[(1 << 16)][8];
u16 transpose(u16 x) {
u16 t = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (x & P(j, i)) {
t |= P(i, j);
}
}
}
return t;
}
u16 rotate(u16 x) {
u16 r = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (x & P(3 - j, i)) {
r |= P(i, j);
}
}
}
return r;
}
void initialize_zobrist_table(void) {
for (int i = 0; i < 1 << 16; i++) {
ZOBRIST_TABLE[i][0] = rand_u64();
}
for (int i = 0; i < 1 << 16; i++) {
int j = i;
for (int r = 1; r < 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 < 8; r++) {
u64 h = 0;
for (int i = 0; i < 8; i++) {
h += ZOBRIST_TABLE[x[i]][r];
}
hash ^= mix(h);
}
return mix(hash);
}
u8 IS_WON[(1 << 16) / 8];
void initialize_is_won(void) {
for (int x = 0; x < 1 << 16; x++) {
bool is_won = false;
for (int i = 0; i < 4; i++) {
u16 stride = 0xF << (4 * i);
if ((x & stride) == stride) {
is_won = true;
break;
}
stride = 0x1111 << i;
if ((x & stride) == stride) {
is_won = true;
break;
}
}
if (is_won == false) {
if (((x & DIAG0) == DIAG0) || ((x & DIAG1) == DIAG1)) {
is_won = true;
}
}
if (is_won) {
IS_WON[x / 8] |= (1 << (x % 8));
}
}
}
bool is_won(u16 x) {
return (IS_WON[x / 8] >> (x % 8)) & 1;
}
bool make_move(u16* board, u8 piece, u8 position) {
u16 p = 1 << position;
for (int i = 0; i < 4; i++) {
bool a = (piece >> i) & 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 < 8; d++) {
u64 i = (hash + d) & table->mask;
Entry* entry = &table->entries[i];
if (entry->hash == 0 || entry->hash == hash) {
return entry;
}
if (entry->count < min_count) {
min_count = entry->count;
to_replace = entry;
}
}
if (to_replace) {
to_replace->hash = 0;
to_replace->count = 0;
return to_replace;
}
return NULL;
}
u64 count_solutions(TTable* ttable, u16* board, u8* pieces, u8 position) {
u64 hash = 0;
if (position <= 10) {
hash = hash_board(board);
Entry* entry = lookup(ttable, hash, 0);
if (entry && entry->hash) {
return entry->count;
}
}
u64 n = 0;
for (int i = position; i < 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->hash = hash;
entry->count = n;
}
}
return n;
}
int main(void) {
TTable ttable;
int ttable_size = 1 << 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 < 16; i++) {pieces[i] = i;}
u16 board[8] = {0};
printf("count: %lu\n", count_solutions(&ttable, board, pieces, 0));
}
