Considere os tetrominoes. É possível cobrir um tabuleiro 8×8 com eles?

Question

Implemente uma solucão computacional para esse problema. Use e abuse de figuras que você gerará computacionalmente (e apresente os códigos usados para isso).

Answer 1

Tetramino L

l = TetraminoL();
l.inserirTabuleiro(tabuleiro);
plt.savefig('TetraminoL')

Tetramino Z

O tetramino Z foi único que não foi possível completar o tabuleiro.

z = TetraminoZ();
z.inserirTabuleiro(tabuleiro);
plt.savefig('TetraminoZ1')

Girar a figura gerou a mesma situação.

Sei que o programa não é o melhor possível, pois a tentativa de encaixar a figura vai tentando as posições no sentido horário mas não necessariamente escolhe a melhor opção para cada situação.

Quanto ao Tetramino Z, realmente não é possível completar o tabuleiro como ele. (testei na mão e procurei na internet.)

Comments

A pergunta está bem respondida ao meu ver,  sugeriria a resposta estar concentrada em apenas um texto, desta forma facilitaria o comentário em todo o texto ao invés de partes. Além disso, seria interessante se o código contemplasse as três formas de objetos em um mesmo codigo (tetramino T1, Tetraminó L e Tetraminó Z1), assim sendo seria possível encontrar soluções ótimas, para um certo conjunto de figuras dispostas no Tabuleiro.

Answer 2

Resolvi esse problema usando orientação a objetos. Criei a classe Quadrado que possui as coordenadas do vértice inicial do quadrado e a função de girar a figura para a direita. A classe Tetramino é uma lista com 4 quadrados que possui funções como girar a peça (loop que gira cada quadrado da lista) e encaixar no tabuleiro (verifica se a peça entra naquela espaço. Caso não entre, a peça é gira e é feita a verificação novamente) como funções principais.
Algumas funções servem de apoio à rotação do tetramino, como atualizar suas coordenadas para que o quadrado mais baixo da lista(menor y e menor x) sempre fique na posição que está sendo verificada no tabuleiro. Com isso, criei as classes tetramino específicas que herdam da classe tetramino. Nessas classes apenas atualizei as coordenadas dos quadrados para formar a figura. Acredito que a solução tenha ficado um pouco longa e por isso disponibilizo aqui o link para download do arquivo .py.

Solução do problema.

Answer 3

Segue o código.

import matplotlib.pyplot as plt;
import numpy as np;

cores = ['b', 'g', 'r', 'c', 'm','y']

rotMatriz = np.array([[0,-1], [1,0]]);

class Tabuleiro(object):
    #essa classe cria um plot em forma de tabuleiro para facilitar a visão do problema
    def __init__(self, n):

        plt.axis([0, n , 0, n]);
        self.lado = n;
        for i in range(1, n):
            plt.plot([i , i], [0, n], c = 'black');
            plt.plot([0, n], [i , i], c = 'black');

        self.spaces = np.ones((n,n), dtype=bool);
        #aqui eu crio uma matriz de 1s com valor booleano (1 = True no python) e aqui eu guardo se a célula foi ocupada ou não

    def ocuparSpace(self, i,j,z):
        #essa função muda o status da matriz para dizer que a célula está ocupada e pinta a célula olhando a lista de cores com o índice z
        self.spaces[j][i] = False;
        plt.fill_between([j,j+1], i,i+1, facecolor = cores[z]);


    def spaceStatus(self, i,j):
        #retorna se a célula está vazia ou não
        if i > self.lado - 1 or j > self.lado - 1 or i < 0 or j < 0:
            return False;
        else:
            return self.spaces[j][i];

class Quadrado(object):

    def __init__(self):
        self.x = 0;
        self.y = 0;

    def girarDireita(self):

        tempx = self.x;
        tempy = self.y;
        self.x = tempx*rotMatriz[0][0] + tempy*rotMatriz[1][0];
        self.y = tempx*rotMatriz[0][1] + tempy*rotMatriz[1][1];

    def inserirTabuleiro(self, tabuleiro):
        z = 0;
        for i in range(0, tabuleiro.lado):
            for j in range(0, tabuleiro.lado):
                if tabuleiro.spaceStatus(i ,j):
                    tabuleiro.ocuparSpace(i,j,z);
                    if z > 5:
                        z = 0;

Utilizo as biblioteca numpy e matplotlib. A lista de cores serve para cada figura inserida no tabuleiro ficar com um cor diferentes das próximas e facilitar a visão do problema. A matriz de rotação serve de auxílio para rotacionar as figuras.
A classe tabuleiro quando iniciado criar uma grade no gráfico com o tamanho dado como parâmetro e cria uma matriz nxn de True que indica que a célula está vazia.
As outras funções estão explicadas nos comentários do código. A função que muda o status da célula é mesma que a colore.

A classe quadrado é bem simples. Ela possui coordenadas x e y no plano indicando onde começa o quadrado. A função inserir tabuleiro faz um loop por todas as coordenadas do tabuleiro e verifica se a figura entra ou não naquela espaço.

Answer 4

Classe dos Tetraminos

class Tetramino(object):

    #classe pai que todas as figuras vão herdar

    def __init__(self):
        quadrado1 = Quadrado();
        quadrado2 = Quadrado();
        quadrado3 = Quadrado();
        quadrado4 = Quadrado();
        self.figura = [quadrado1, quadrado2, quadrado3, quadrado4]

    def girarDireita(self,i,j):
        for k in self.figura:
            k.girarDireita();

        self.regularCoordenadas(i,j);

    def regularCoordenadas(self,i,j):
        #manter as coordenadas sempre positivas após uma rotação
        i = i;
        j = j;
        minx = self.figura[self.acharPrimeiroQuadrado()].x;
        miny = self.figura[self.acharPrimeiroQuadrado()].y;

        if minx < j:
            for k in self.figura:
                k.x += j - minx;

        if minx > j:
            for k in self.figura:
                k.x -= minx - j;

        if miny < i:
            for k in self.figura:
                k.y += i - miny;

        if miny > i:
            for k in self.figura:
                k.y -= miny - i;

    def regular(self, i,j):
        #coloca o quadrado mais abaixo da lista na posição verificado
        for a in self.figura:
            a.x += j;
            a.y += i;

    def deregular(self,i,j):
        #retorna a peça para a posição original
        for a in self.figura:
            a.x -= j;
            a.y -= i;

        self.regularCoordenadas(0,0)

    def acharPrimeiroQuadrado(self):
        minx = 10;
        miny = 10;
        indice = 0;

        for i in range(0, len(self.figura)):
            if self.figura[i].y < miny:
                miny = self.figura[i].y;

        for i in range(0, len(self.figura)):
            if self.figura[i].y == miny:
                if self.figura[i].x < minx:
                    minx = self.figura[i].x;
                    indice = i;
        return indice;


    def inserirTabuleiro(self, tabuleiro):
        z = 0;
        giradas = 0;
        for i in range(0, tabuleiro.lado):
            for j in range(0, tabuleiro.lado):
                if tabuleiro.spaceStatus(i,j):
                    #se o próximo espaço é vázio, o programa testa se a peça cabe, se não roda e testa novamente até esgotar as opções.

                    self.regular(i,j);
                    if (tabuleiro.spaceStatus(self.figura[0].y, self.figura[0].x) and tabuleiro.spaceStatus(self.figura[1].y, self.figura[1].x) and
                     tabuleiro.spaceStatus(self.figura[2].y, self.figura[2].x) and tabuleiro.spaceStatus(self.figura[3].y, self.figura[3].x)):

                        tabuleiro.ocuparSpace(self.figura[0].y, self.figura[0].x, z);
                        tabuleiro.ocuparSpace(self.figura[1].y, self.figura[1].x, z);
                        tabuleiro.ocuparSpace(self.figura[2].y, self.figura[2].x, z);
                        tabuleiro.ocuparSpace(self.figura[3].y, self.figura[3].x, z);
                        z += 1;

                    else:

                        self.girarDireita(i,j);
                        giradas +=1;

                        if (tabuleiro.spaceStatus(self.figura[0].y, self.figura[0].x) and tabuleiro.spaceStatus(self.figura[1].y, self.figura[1].x) and
                        tabuleiro.spaceStatus(self.figura[2].y, self.figura[2].x) and tabuleiro.spaceStatus(self.figura[3].y, self.figura[3].x)):


                            tabuleiro.ocuparSpace(self.figura[0].y, self.figura[0].x, z);
                            tabuleiro.ocuparSpace(self.figura[1].y, self.figura[1].x, z);
                            tabuleiro.ocuparSpace(self.figura[2].y, self.figura[2].x, z);
                            tabuleiro.ocuparSpace(self.figura[3].y, self.figura[3].x, z);
                            z += 1;
                        else:
                            self.girarDireita(i,j);
                            giradas +=1;

                            if (tabuleiro.spaceStatus(self.figura[0].y, self.figura[0].x) and tabuleiro.spaceStatus(self.figura[1].y, self.figura[1].x) and
                            tabuleiro.spaceStatus(self.figura[2].y, self.figura[2].x) and tabuleiro.spaceStatus(self.figura[3].y, self.figura[3].x)):

                                tabuleiro.ocuparSpace(self.figura[0].y, self.figura[0].x, z);
                                tabuleiro.ocuparSpace(self.figura[1].y, self.figura[1].x, z);
                                tabuleiro.ocuparSpace(self.figura[2].y, self.figura[2].x, z);
                                tabuleiro.ocuparSpace(self.figura[3].y, self.figura[3].x, z);
                                z += 1;


                            else:

                                self.girarDireita(i,j);
                                giradas +=1;

                                if (tabuleiro.spaceStatus(self.figura[0].y, self.figura[0].x) and tabuleiro.spaceStatus(self.figura[1].y, self.figura[1].x) and
                                tabuleiro.spaceStatus(self.figura[2].y, self.figura[2].x) and tabuleiro.spaceStatus(self.figura[3].y, self.figura[3].x)):


                                    tabuleiro.ocuparSpace(self.figura[0].y, self.figura[0].x, z);
                                    tabuleiro.ocuparSpace(self.figura[1].y, self.figura[1].x, z);
                                    tabuleiro.ocuparSpace(self.figura[2].y, self.figura[2].x, z);
                                    tabuleiro.ocuparSpace(self.figura[3].y, self.figura[3].x, z);
                                    z += 1;


                                else:

                                    self.girarDireita(i,j);
                                    giradas+=1;

                while giradas < 4:
                    self.girarDireita(i,j);
                    giradas +=1;

                giradas = 0;

                self.deregular(i,j);
                if z > 5:
                    z = 0;

A classe Tetramino cria uma lista com 4 objetos do tipo Quadrado. A inserção do tabuleiro é feita da seguinte forma.
Nested Loop por i e j e se a célula está vazia ele verifica se a figura entra no tabuleiro. Se não, a figura gira. O programa gira a figura 3 vezes para verificar e depois gira mais uma para que a figura sempre comece a próxima iteração do loop na sua posição original. A variável giradas foi criada para voltar a figura para a posição original caso ela não complete o ciclo nos Ifs.

Answer 5

Em seguida crio as classes dos Tetraminos específicos.

class TetraminoQ(Tetramino):
    #tetramino quadrado
    def __init__(self):
        super(TetraminoQ, self).__init__();
        #cria o formato da figura
        self.figura[0].x = 0;
        self.figura[0].y = 0;

        self.figura[1].x = 1;
        self.figura[1].y = 0;

        self.figura[2].x = 0;
        self.figura[2].y = 1;

        self.figura[3].x = 1;
        self.figura[3].y = 1;

class TetraminoI(Tetramino):
    #tetramino barra
    def __init__(self):
        super(TetraminoI, self).__init__();
        self.figura[0].x = 0;
        self.figura[0].y = 0;

        self.figura[1].x = 0;
        self.figura[1].y = 1;

        self.figura[2].x = 0;
        self.figura[2].y = 2;

        self.figura[3].x = 0;
        self.figura[3].y = 3;

class TetraminoT(Tetramino):
    #tetramino T
    def __init__(self):
        super(TetraminoT, self).__init__();
        self.figura[0].x = 0;
        self.figura[0].y = 0;

        self.figura[1].x = 1;
        self.figura[1].y = 0;

        self.figura[2].x = 2;
        self.figura[2].y = 0;

        self.figura[3].x = 1;
        self.figura[3].y = 1;

class TetraminoL(Tetramino):
    #tetramino L
    def __init__(self):
        super(TetraminoL, self).__init__();
        self.figura[0].x = 0;
        self.figura[0].y = 0;

        self.figura[1].x = 0;
        self.figura[1].y = 1;

        self.figura[2].x = 0;
        self.figura[2].y = 2;

        self.figura[3].x = 1;
        self.figura[3].y = 0;

class TetraminoZ(Tetramino):
    #tetramino Z
    def __init__(self):
        super(TetraminoZ, self).__init__();
        self.figura[0].x = 0;
        self.figura[0].y = 0;

        self.figura[1].x = 1;
        self.figura[1].y = 0;

        self.figura[2].x = 1;
        self.figura[2].y = 1;

        self.figura[3].x = 2;
        self.figura[3].y = 1;

Answer 6

Teste.

if __name__ == '__main__':

    plt.figure(num=None, figsize=(5, 5), dpi=80, facecolor='w', edgecolor='k')
    n = 8
    tabuleiro = Tabuleiro(n)
    t = TetraminoT()
    q = TetraminoQ()
    i = tetraminoI();
    l = TetraminoL();
    z = TetraminoZ();

Tetramino Quadrado.

q.inserirTabuleiro(tabuleiro);
plt.savefig('TetraminoQ')

i.inserirTabuleiro(tabuleiro);
plt.savefig('TetraminoI')

O tetramino T entrando na sua posição inicial não consegue completar o tabuleiro com o código.

t.inserirTabuleiro(tabuleiro);
plt.savefig('TetraminoT1')

Porém se ele entrar na posição cabeça para baixo, ele completa.

t = TetraminoT();
t.girarDireita(0,0);
t.girarDireita(0,0);
t.inserirTabuleiro(tabuleiro);
plt.savefig('TetraminoT2')