Eternity II
UFABC - MCZA020-13 - Programação Paralela

1 O Jogo¹

Eternity II é um quebra-cabeça ² que foi lançado em 2007. Naquela época havia um prêmio de US$ 2 milhões para a primeira pessoa que apresentasse uma solução completa. Contudo, até hoje nenhuma solução completa foi encontrara e o prêmio continua em aberto.

Eternity II é um quebra-cabeça clássico de casamento de bordas que envolve a colocação de $256$ peças em um tabuleiro de $16x16$. Cada peça tem as suas bordas com diferentes combinações de formas e cores (que neste texto simplificamos para apenas cores). As peças devem ser colocadas no tabuleiro de maneira que todas as cores de suas bordas sejam uma correspondência às bordas das peças adjacentes. As bordas do tabuleiro são um caso com tratamento especial que apenas podem receber peças com bordas cinzas. Cada uma das peças pode ser rotacionada e tem, portanto, $4$ possíveis colocações para cada posição do tabuleiro. Há $22$ cores no total, sem incluir as bordas cinzas. No jogo original a peça do centro do tabuleiro é pré-determinada e algumas dicas sobre o posicionamento de algumas peças são dadas.

Figura 1: Na esquerda um conjunto de peças para um quebra-cabeça $4 x 4$. Na direita o quebra cabeça resolvido. Note como nesta solução algumas das peças foram rotacionadas.

Este jogo foi criado especificamente para ser dificílimo de resolver por força bruta. De fato, ele permanece até hoje intratável em sua forma original. O número total de configurações possíveis (assumindo que todas as peças são distintas e ignorando as peças com posicionamento pré-determinado e as dicas de posicionamento) é de $256! \times 4^{256}$ ou, aproximadamente, $1.15 \times 10^{661}$. Um limite superior mais justo pode ser obtido levando em consideração essas restrições e dicas o que acaba nos levando a um espaço de busca de $3.11 \times 10^{545}$.

O código abaixo só funciona para pequenas instâncias do problema. A versão paralela também é útil apenas para fins de instrução. O seu desempenho poderia ser melhorado por uma divisão mais inteligente do trabalho.

Nestas implementações não se leva em consideração as peças com posições iniciais pré-determinadas nem as dicas de colocação. O tamanho do tabuleiro, o número de cores e peças são recebidos pela entrada padrão e a solução é impressa na saída padrão.

Tanto a versão sequencial quanto a versão paralela usam a mesma abordagem de força bruta baseada em backtracking. É um bom exercício pensar em estratégias alternativas e heurísticas para melhorar os códigos abaixo. Note, contudo, que um único quebra-cabeças pode ter mais de uma solução correta.

2 Entrada

Cada entrada contém um quebra-cabeça. Ela consiste de uma lista de inteiros separada por espaços e quebras de linha. A primeira linha contém $2$ inteiros: o tamanho do tabuleiro $g$ e o número de cores $c$. As $g^2$ linhas seguintes contém cada uma das peças. A ordem de apresentação das peças é importante pois será utilizada na saída (contagem a partir do 0, logo as peças são numeradas de $0$ to $g^2 - 1$. Cada peça é descrita por $4$ inteiros entre $0$ e $c - 1$ descrevendo as cores de suas bordas no sentido horário iniciando pela borda superior. A cor $0$ (cinza) é considerada como especial: as únicas posições válidas no tabuleiro para essas bordas são nos limites do tabuleiro. Como exemplo, a entrada abaixo representa a figura acima. É razoável assumir que $c \le g$.

A entrada é recebida pela entrada padrão.

3 Saída

A saída esperada deve possuir $g^2$ linhas, cada uma representando cada uma das casas do tabuleiro. A ordem das linhas segue o tabuleiro, da esquerda para a direita, de cima para baixo. Cada linha é composta por $2$ inteiros. O primeiro indica o número da peça e o segundo indica o número de rotações em sentido horário. A saída esperada (representada na figura (b) para a entrada descrita acima pode ser vista abaixo.

4 Exemplo

*Input	*Output
4 5	0 0
0 1 2 0	9 1
0 0 2 1	11 1
1 0 0 1	3 3
2 0 0 2	8 0
3 4 3 3	5 2
4 4 4 3	4 3
4 4 3 3	12 2
4 4 3 3	14 0
2 4 2 0	6 0
1 4 1 0	7 2
1 4 2 0	15 2
2 4 1 0	2 1
2 3 2 0	13 3
1 3 1 0	10 3
2 3 1 0	1 1
1 3 2 0

Para verificar a saída utilize o programa checker.c Esta e outras entradas de exemplo: entradas.zip

5 Código sequencial

Você pode baixar o código aqui: eternity.c.

/*
 * Emilio Francesquini <e.francesquini@ufabc.edu.br>
 * 2019-04-08
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct {
    int colors[4];
    char rotation;
    int id;
    int used;
} tile;

#define X_COLOR(t, s) (t->colors[(s + 4 - t->rotation) % 4])
#define N_COLOR(t) (X_COLOR(t, 0))
#define E_COLOR(t) (X_COLOR(t, 1))
#define S_COLOR(t) (X_COLOR(t, 2))
#define W_COLOR(t) (X_COLOR(t, 3))

typedef struct {
    int size;
    int tile_count; //==size^2
    tile ***board;
    tile *tiles;
} game;


game *initialize (FILE *input) {
    int bsize;
    int ncolors;
    int r = fscanf (input, "%u", &bsize);
    assert (r == 1);
    r = fscanf (input, "%u", &ncolors);
    assert (r == 1);
    assert (ncolors < 256);

    //creates an empty board
    game *g = malloc (sizeof(game));
    g->size = bsize;
    g->board = malloc (sizeof (tile**) * bsize);
    for(int i = 0; i < bsize; i++)
        g->board[i] = calloc(bsize, sizeof(tile*));
    g->tile_count = bsize * bsize;

    //loads tiles
    g->tiles = malloc(g->tile_count * sizeof(tile));
    for (int i = 0; i < g->tile_count; i++) {
        g->tiles[i].rotation = 0;
        g->tiles[i].id = i;
        g->tiles[i].used = 0;
        for (int c = 0; c < 4; c++) {
            r = fscanf(input, "%u", &g->tiles[i].colors[c]);
            assert(r == 1);
        }
    }

    return g;
}

void free_resources(game *game) {
    free(game->tiles);
    for(int i = 0; i < game->size; i++)
        free(game->board[i]);
    free(game->board);
    free(game);
}

int valid_move (game *game, int x, int y, tile *tile) {
    //The borders must be 0-colored
    if (x == 0 && W_COLOR(tile) != 0) return 0;
    if (y == 0 && N_COLOR(tile) != 0) return 0;
    if (x == game->size - 1 && E_COLOR(tile) != 0) return 0;
    if (y == game->size - 1 && S_COLOR(tile) != 0) return 0;

    //The tile must also be compatible with its existing neighbours
    if (x > 0 && game->board[x - 1][y] != NULL &&
        E_COLOR(game->board[x - 1][y]) != W_COLOR(tile))
        return 0;
    if (x < game->size - 1 && game->board[x + 1][y] != NULL &&
        W_COLOR(game->board[x + 1][y]) != E_COLOR(tile))
        return 0;
    if (y > 0 && game->board[x][y - 1] != NULL &&
        S_COLOR(game->board[x][y - 1]) != N_COLOR(tile))
        return 0;
    if (y < game->size - 1 && game->board[x][y + 1] != NULL &&
        N_COLOR(game->board[x][y + 1]) != S_COLOR(tile))
        return 0;

    return 1;
}


void print_solution (game *game) {
    for(int j = 0; j < game->size; j++)
        for(int i = 0; i < game->size; i++) {
            tile *t = game->board[i][j];
            printf("%u %u\n", t->id, t->rotation);
        }
}

int play (game *game, int x, int y) {
    for (int i = 0; i < game->tile_count; i++) {
        if (game->tiles[i].used) continue;
        tile *tile = &game->tiles[i];
        tile->used = 1;
        for (int rot = 0; rot < 4; rot++) {//tries each side
            tile->rotation = rot;
            if (valid_move(game, x, y, tile)) {
                game->board[x][y] = tile;
                int nx, ny;
                ny = nx = game->size;
                if (x < game->size - 1) {
                    nx = x + 1;
                    ny = y;
                } else if (y < game->size - 1) {
                    nx = 0;
                    ny = y + 1;
                }
                if (ny == game->size || play(game, nx, ny)) {
                    return 1;
                }
                game->board[x][y] = NULL;
            }
        }
        tile->used = 0;
    }
    //no solution was found
    return 0;
}


int main (int argc, char **argv) {
    game *g = initialize(stdin);
    if (play(g, 0, 0))
        print_solution(g);
    else
        printf("SOLUTION NOT FOUND");
    free_resources(g);
}

6 Código paralelo

Você pode baixar o código aqui: eternity_par.c.

/*
 * Emilio Francesquini <e.francesquini@ufabc.edu.br>
 * 2019-04-08
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <pthread.h>


int done;
pthread_mutex_t lock;

typedef struct {
    int colors[4];
    char rotation;
    int id;
    int used;
} tile;

#define X_COLOR(t, s) (t->colors[(s + 4 - t->rotation) % 4])
#define N_COLOR(t) (X_COLOR(t, 0))
#define E_COLOR(t) (X_COLOR(t, 1))
#define S_COLOR(t) (X_COLOR(t, 2))
#define W_COLOR(t) (X_COLOR(t, 3))

typedef struct {
    int size;
    int tile_count; //==size^2
    tile ***board;
    tile *tiles;
} game;


game *initialize (FILE *input, int copies) {
    int bsize;
    int ncolors;
    assert(copies >= 1);
    int r = fscanf (input, "%u", &bsize);
    assert (r == 1);
    r = fscanf (input, "%u", &ncolors);
    assert (r == 1);
    assert (ncolors < 256);

    int tile_count = bsize * bsize;

    //creates empty boards
    game *games = malloc (sizeof(game) * copies);
    for (int index = 0; index < copies; ++index) {
        game *g = games + index;
        g->size = bsize;
        g->board = malloc (sizeof (tile**) * bsize);
        for(int j = 0; j < bsize; j++)
            g->board[j] = calloc(bsize, sizeof(tile*));
        g->tile_count = tile_count;

        //loads tiles
        g->tiles = malloc(tile_count * sizeof(tile));
    }


    for (int i = 0; i < tile_count; i++)
        for (int c = 0; c < 4; c++) {
            int color;
            r = fscanf(input, "%u", &color);
            assert(r == 1);
            for (int j = 0; j < copies; j++) {
                game *g = games + j;
                g->tiles[i].colors[c] = color;
                g->tiles[i].rotation = 0;
                g->tiles[i].id = i;
                g->tiles[i].used = 0;
            }
        }

    return games;
}

void free_resources(game *game, int copies) {
    for (int g = 0; g < copies; g++) {
        free(game[g].tiles);
        for(int i = 0; i < game[g].size; i++)
            free(game[g].board[i]);
        free(game[g].board);
    }
    free(game);
}

int valid_move (game *game, int x, int y, tile *tile) {
    //The borders must be 0-colored
    if (x == 0 && W_COLOR(tile) != 0) return 0;
    if (y == 0 && N_COLOR(tile) != 0) return 0;
    if (x == game->size - 1 && E_COLOR(tile) != 0) return 0;
    if (y == game->size - 1 && S_COLOR(tile) != 0) return 0;

    //The tile must also be compatible with its existing neighbours
    if (x > 0 && game->board[x - 1][y] != NULL &&
        E_COLOR(game->board[x - 1][y]) != W_COLOR(tile))
        return 0;
    if (x < game->size - 1 && game->board[x + 1][y] != NULL &&
        W_COLOR(game->board[x + 1][y]) != E_COLOR(tile))
        return 0;
    if (y > 0 && game->board[x][y - 1] != NULL &&
        S_COLOR(game->board[x][y - 1]) != N_COLOR(tile))
        return 0;
    if (y < game->size - 1 && game->board[x][y + 1] != NULL &&
        N_COLOR(game->board[x][y + 1]) != S_COLOR(tile))
        return 0;

    return 1;
}


void print_solution (game *game) {
    for(int j = 0; j < game->size; j++)
        for(int i = 0; i < game->size; i++) {
            tile *t = game->board[i][j];
            printf("%u %u\n", t->id, t->rotation);
        }
}



int play (game *game, int x, int y, int tile_start, int tile_step) {
    if (done != -1)
        return 0;
    for (int i = tile_start; i < game->tile_count; i += tile_step) {
        if (game->tiles[i].used) continue;
        tile *tile = &game->tiles[i];
        tile->used = 1;
        for (int rot = 0; rot < 4; rot++) {//tries each side
            tile->rotation = rot;
            if (valid_move(game, x, y, tile)) {
                game->board[x][y] = tile;
                int nx, ny;
                ny = nx = game->size;
                if (x < game->size - 1) {
                    nx = x + 1;
                    ny = y;
                } else if (y < game->size - 1) {
                    nx = 0;
                    ny = y + 1;
                }
                if (ny == game->size || play(game, nx, ny, 0, 1)) {
                    return 1;
                }
                game->board[x][y] = NULL;
            }
        }
        tile->used = 0;
    }
    //no solution was found
    return 0;
}

struct thread_init_param {
    game *game;
    int x, y, tile_start, tile_step;
};

void *init_thread (void* param) {
    struct thread_init_param *p = (struct thread_init_param*)param;
    if (play(p->game, p->x, p->y, p->tile_start, p->tile_step)) {
        pthread_mutex_lock(&lock);
        if (done == -1)
            done = p->tile_start;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main (int argc, char *argv[]) {

    int nthreads = atoi(argv[1]);
    pthread_t threads[nthreads];
    struct thread_init_param tparams[nthreads];

    done = -1;
    pthread_mutex_init(&lock, NULL);

    game *g = initialize(stdin, nthreads);
    for (int t = 0; t < nthreads; t++) {
        tparams[t].game = &g[t];
        tparams[t].x = 0;
        tparams[t].y = 0;
        tparams[t].tile_start = t;
        tparams[t].tile_step = nthreads;
        pthread_create(&threads[t], NULL, init_thread, &tparams[t]);
    }

    for (int t = 0; t < nthreads; t++)
        pthread_join(threads[t], NULL);

    if (done != -1)
        print_solution(&g[done]);
    else
        printf("SOLUTION NOT FOUND");
    free_resources(g, nthreads);
}

Notas de Rodapé:

Perdi

A descrição foi adaptada da Wikipedia

Eternity II UFABC - MCZA020-13 - Programação Paralela

1 O Jogo1