Introdução

Esse desafio é semelhante aos problemas do Project Euler . Eu o criei porque estava jogando um jogo de tabuleiro enganosamente simples e não consegui encontrar uma solução eficiente para responder a uma pergunta simples sobre sua mecânica.

Quarto é uma variante divertida de 4 em uma fileira. É jogado em um tabuleiro 4 por 4 com 16 peças únicas (nenhuma peça é duplicada). A cada turno, cada jogador coloca 1 peça no tabuleiro. Cada peça possui 4 características binárias (baixa / alta, preta / branca, quadrada / circular, oca / sólida). O objetivo é fazer quatro em linha, horizontalmente, verticalmente ou ao longo das 2 diagonais, para qualquer uma das quatro características! Então, 4 peças pretas, 4 peças brancas, 4 peças altas, 4 peças curtas, 4 peças quadradas, 4 peças circulares, 4 peças ocas ou 4 peças sólidas.

A imagem acima mostra um jogo terminado, há quatro em sequência por causa de quatro peças quadradas.

Desafio

No Quarto, alguns jogos podem terminar empatados.

O número total de posições finais possíveis é de 16!cerca de 20 trilhões.

Quantas dessas posições finais são empates?

Regras

1. A solução deve ser um programa que calcule e produz o número total de posições finais que são desenhadas. A resposta correta é414298141056

2. Você só pode usar informações das regras do jogo que foram deduzidas manualmente (nenhuma prova assistida por computador).

3. Simplificações matemáticas do problema são permitidas, mas devem ser explicadas e comprovadas (manualmente) na sua solução.

4. O vencedor é aquele com a solução mais ideal em termos de tempo de execução da CPU.

5. Para determinar o vencedor, executarei todas as soluções com um tempo de execução relatado menor que 30m em um MacBook Pro 2,5 GHz Intel Core i7 com 16 GB de RAM .

6. Não há pontos de bônus por encontrar uma solução que também funcione com outros tamanhos de tabuleiro. Mesmo que isso seria legal.

7. Se aplicável, seu programa deve compilar dentro de 1 minuto no hardware mencionado acima (para evitar abuso de otimização do compilador)

8. As brechas padrão não são permitidas

Submissões

Por favor, poste:

1. O código ou um link do github / bitbucket para o código.
2. A saída do código.
3. Seu tempo de execução medido localmente
4. Uma explicação da sua abordagem.

Data limite

O prazo final para as inscrições é 1 de março, portanto, ainda há bastante tempo.

C: 414298141056 empates encontrados em cerca de 5 2,5 minutos.

Pesquisa simples e profunda com uma tabela de transposição com reconhecimento de simetria. Utilizamos a simetria dos atributos sob permutação e a simetria diédrica de 8 vezes do quadro.

#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));
}

Pontuação medida (@wvdz):

$ clang -O3 -march=native quarto_user1502040.c
$ time ./a.out
count: 414298141056

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

Pontuação (usuário + sistema): 1m35.727s

Java, 414298141056 empates, 23m42.272s

Espero que não seja desagradável postar uma solução para o próprio desafio, mas a razão pela qual eu publiquei esse desafio foi que me enlouqueceu por não ter conseguido encontrar uma solução eficiente. Minha melhor tentativa levaria dias para ser concluída.

Depois de estudar a resposta do usuário1502040 , consegui modificar meu código para rodar dentro de um prazo razoável. Minha solução ainda é significativamente diferente, mas roubei algumas idéias:

• Em vez de me concentrar nas posições finais, eu me concentro em realmente jogar o jogo, colocando uma peça após a outra no tabuleiro. Isso me permite criar uma tabela de posições semanticamente idênticas com a contagem correta.
• Perceber a ordem em que as peças são colocadas é importante: elas devem ser colocadas de modo a maximizar a chance de uma vitória antecipada.

A principal diferença entre essa solução e a de user1502040 é que não uso uma tabela Zobrist, mas uma representação canônica de uma placa, na qual considero que cada placa possui 48 transposições possíveis sobre as características (2 * 4!). Não giro ou transpo o tabuleiro inteiro, mas apenas as características das peças.

Este é o melhor que eu poderia inventar. Idéias para otimizações óbvias ou menos óbvias são bem-vindas!

public class Q {

    public static void main(String[] args) {
        System.out.println(countDraws(getStartBoard(), 0));
    }

    /** Order of squares being filled, chosen to maximize the chance of an early win */
    private static int[] indexShuffle = {0, 5, 10, 15, 14, 13, 12, 9, 1, 6, 3, 2, 7, 11, 4, 8};

    /** Highest depth for using the lookup */
    private static final int MAX_LOOKUP_INDEX = 10;

    public static long countDraws(long board, int turn) {
        long signature = 0;
        if (turn < MAX_LOOKUP_INDEX) {
            signature = getSignature(board, turn);
            if (cache.get(turn).containsKey(signature))
                return cache.get(turn).get(signature);
        }
        int indexShuffled = indexShuffle[turn];
        long count = 0;
        for (int n = turn; n < 16; n++) {
            long newBoard = swap(board, indexShuffled, indexShuffle[n]);
            if (partialEvaluate(newBoard, indexShuffled))
                continue;
            if (turn == 15)
                count++;
            else
                count += countDraws(newBoard, turn + 1);
        }
        if (turn < MAX_LOOKUP_INDEX)
            cache.get(turn).put(signature, count);
        return count;
    }

    /** Get the canonical representation for this board and turn */
    private static long getSignature(long board, int turn) {
        int firstPiece = getPiece(board, indexShuffle[0]);
        long signature = minTranspositionValues[firstPiece];
        List<Integer> ts = minTranspositions.get(firstPiece);
        for (int n = 1; n < turn; n++) {
            int min = 16;
            List<Integer> ts2 = new ArrayList<>();
            for (int t : ts) {
                int piece = getPiece(board, indexShuffle[n]);
                int posId = transpositions[piece][t];
                if (posId == min) {
                    ts2.add(t);
                } else if (posId < min) {
                    min = posId;
                    ts2.clear();
                    ts2.add(t);
                }
            }
            ts = ts2;
            signature = signature << 4 | min;
        }
        return signature;
    }

    private static int getPiece(long board, int position) {
        return (int) (board >>> (position << 2)) & 0xf;
    }

    /** Only evaluate the relevant winning possibilities for a certain turn */
    private static boolean partialEvaluate(long board, int turn) {
        switch (turn) {
            case 15:
                return evaluate(board, masks[8]);
            case 12:
                return evaluate(board, masks[3]);
            case 1:
                return evaluate(board, masks[5]);
            case 3:
                return evaluate(board, masks[9]);
            case 2:
                return evaluate(board, masks[0]) || evaluate(board, masks[6]);
            case 11:
                return evaluate(board, masks[7]);
            case 4:
                return evaluate(board, masks[1]);
            case 8:
                return evaluate(board, masks[4]) || evaluate(board, masks[2]);
        }
        return false;
    }

    private static List<Map<Long, Long>> cache = new ArrayList<>();
    static {
        for (int i = 0; i < 16; i++)
            cache.add(new HashMap<>());
    }

    private static boolean evaluate(long board, long[] masks) {
        return _evaluate(board, masks) || _evaluate(~board, masks);
    }

    private static boolean _evaluate(long board, long[] masks) {
        for (long mask : masks)
            if ((board & mask) == mask)
                return true;
        return false;
    }

    private static long swap(long board, int x, int y) {
        if (x == y)
            return board;
        if (x > y)
            return swap(board, y, x);
        long xValue = (board & swapMasks[1][x]) << ((y - x) * 4);
        long yValue = (board & swapMasks[1][y]) >>> ((y - x) * 4);
        return board & swapMasks[0][x] & swapMasks[0][y] | xValue | yValue;
    }

    private static long getStartBoard() {
        long board = 0;
        for (long n = 0; n < 16; n++)
            board |= n << (n * 4);
        return board;
    }

    private static List<Integer> allPermutations(int input, int size, int idx, List<Integer> permutations) {
        for (int n = idx; n < size; n++) {
            if (idx == 3)
                permutations.add(input);
            allPermutations(swapBit(input, idx, n), size, idx + 1, permutations);
        }
        return permutations;
    }

    private static int swapBit(int in, int x, int y) {
        if (x == y)
            return in;
        int xMask = 1 << x;
        int yMask = 1 << y;
        int xValue = (in & xMask) << (y - x);
        int yValue = (in & yMask) >>> (y - x);
        return in & ~xMask & ~yMask | xValue | yValue;
    }

    private static int[][] transpositions = new int[16][48];
    static {
        for (int piece = 0; piece < 16; piece++) {
            transpositions[piece][0] = piece;
            List<Integer> permutations = allPermutations(piece, 4, 0, new ArrayList<>());
            for (int n = 1; n < 24; n++)
                transpositions[piece][n] = permutations.get(n);
            permutations = allPermutations(~piece & 0xf, 4, 0, new ArrayList<>());
            for (int n = 24; n < 48; n++)
                transpositions[piece][n] = permutations.get(n - 24);
        }
    }

    private static int[] minTranspositionValues = new int[16];
    private static List<List<Integer>> minTranspositions = new ArrayList<>();
    static {
        for (int n = 0; n < 16; n++) {
            int min = 16;
            List<Integer> elems = new ArrayList<>();
            for (int t = 0; t < 48; t++) {
                int elem = transpositions[n][t];
                if (elem < min) {
                    min = elem;
                    elems.clear();
                    elems.add(t);
                } else if (elem == min)
                    elems.add(t);
            }
            minTranspositionValues[n] = min;
            minTranspositions.add(elems);
        }
    }

    private static final long ROW_MASK = 1L | 1L << 4 | 1L << 8 | 1L << 12;
    private static final long COL_MASK = 1L | 1L << 16 | 1L << 32 | 1L << 48;
    private static final long FIRST_DIAG_MASK = 1L | 1L << 20 | 1L << 40 | 1L << 60;
    private static final long SECOND_DIAG_MASK = 1L << 12 | 1L << 24 | 1L << 36 | 1L << 48;

    private static long[][] masks = new long[10][4];
    static {
        for (int m = 0; m < 4; m++) {
            long row = ROW_MASK << (16 * m);
            for (int n = 0; n < 4; n++)
                masks[m][n] = row << n;
        }
        for (int m = 0; m < 4; m++) {
            long row = COL_MASK << (4 * m);
            for (int n = 0; n < 4; n++)
                masks[m + 4][n] = row << n;
        }
        for (int n = 0; n < 4; n++)
            masks[8][n] = FIRST_DIAG_MASK << n;
        for (int n = 0; n < 4; n++)
            masks[9][n] = SECOND_DIAG_MASK << n;
    }

    private static long[][] swapMasks;
    static {
        swapMasks = new long[2][16];
        for (int n = 0; n < 16; n++)
            swapMasks[1][n] = 0xfL << (n * 4);
        for (int n = 0; n < 16; n++)
            swapMasks[0][n] = ~swapMasks[1][n];
    }
}

Pontuação medida:

$ time java -jar quarto.jar 
414298141056

real    20m51.492s
user    23m32.289s
sys     0m9.983s

Pontuação (usuário + sistema): 23m42.272s