Atualizado em: 15/04/2008

Problema desafio: o quebra-cabeça dos 12 pentaminós

Dicas do Prof. Machado:

Introdução:

Para n=2, há duas figuras possíveis, correspondentes a uma única peça: é o dominó (consideramos aqui dominós sem marcas). As duas figuras são: o retângu- lo 1x2:vertical e o retângulo 2x1:horizontal. Obviamente, uma única peça (retângulo de 2x1) é capaz de gerar as duas figuras, através de rotação de 90º.

No caso mais geral, uma única peça pode gerar 8 figuras: frente com rotação de 0º, 90º, 180º e 270º e verso (imagem espelho) com rotação de 0º, 90º, 180º e 270º. Dependendo da simetria da peça, algumas destas figuras coincidem e menos de 8 figuras distintas são geradas: 1, 2 ou 4.

Consideremos agora o nosso problema: n=5, ie: peças planas constituídas por 5 quadrados unidos por arestas comuns. Há 12 peças diferentes, denominadas pentaminós. Estas 12 peças são tradicionalmente designadas pelas letras: F,I,L,N,P,T,U,V,W,X,Y e Z, que lembram, às vezes vagamente, sua forma (vide Fig. 1)

Das 12x8=96 figuras possíveis geradas pelas 12 peças, apenas 63 são distintas: a peça X gera uma figura (X1); a peça I gera 2 figuras (I1 e I2); as 5 peças: T,U,V,W e Z geram 4 figuras cada (T1-T4 etc)e as 5 peças restantes geram 8 figuras cada (F1-F8 etc). A Fig. 2 mostra as 63 figuras, com as respectivas designações e a numeração que adotamos.

Os "quebra-cabeças" tradicionais usando pentaminós consistem em considerar uma dada área plana (o tabuleiro) e preenchê-la com os 12 pentaminós, que podem ser colocados frente ou verso e em qualquer das quatro orientações. Logo, trata-se de preencher o tabuleiro com 12 das 63 figuras, de forma que cada figura pertença a uma peça diferente.

Os tabuleiros mais tradicionais são os retângulos com área de 60 unidades: 3x20, 4x15, 5x12 e 6x10 (este é talvez o mais clássico). É ainda possivel considerar áreas maiores, com alguns quadrados bloqueados de forma a restarem apenas 60 disponíveis; particularmente popular é o tabuleiro de 8x8 com os 4 quadrados centrais bloqueados, ou com os 4 cantos bloqueados, veja, por exemplo, aqui. É também possível incluir restrições adicionais, como por exemplo: área de 6x10 mas preenchida de forma a poder ser separada em dois retângulos de 6x5 cada sem quebrar nenhuma peça em duas.

Surpreendentemente, todos os quebra-cabeças descritos acima têm solução e, na maioria dos casos, milhares de soluções "diferentes": o menor número de soluções corresponde ao tabuleiro de 3x20: há 8 soluções que, eliminando as simetrias decorrentes de rotações e reflexões, correspondem a apenas 2 configurações distintas (cada configuração gera 4 soluções "diferentes": frente e verso, 0º e 180º). A Fig. 3 dá exemplos de soluções para tabuleiros de 3x20, 4x15, 5x12 e 6x10.

O desafio

Dicas e sugestões

• Forma de apresentação das soluções
  Quando seu programa "parar" com uma solução, esta deve estar representada em um vetor de 62 bytes, a partir da posição de SRAM $100. O conteúdo de cada um dos primeiros 60 bytes é o número da figura que ocupa o respectivo quadrado no tabuleiro, de acordo com a numeração estabelecida na Fig. 2. O primeiro byte corresponde ao quadrado superior esquerdo do tabuleiro e este vai sendo varrido linha a linha, da esquerda para a direita e de cima para baixo, de modo que o 60º byte corresponde ao quadrado inferior direito. Os dois bytes finais contém o número de quadrados em cada linha e o número de linhas. Assim sendo, no caso do tabuleiro exigido, os dois últimos bytes conterão 4 e 15 ou 15 e 4 dependendo de como você decidiu orientar seu tabuleiro.
  Após a parada ao encontrar uma solução, deve ser possível prosseguir com a execução do programa que deve parar novamente ao encontrar mais uma solução (ou parar em outro breakpoint para indicar que não há mais soluções).

• A maior dificuldade consiste em projetar as estruturas de dados nesessárias para representar as figuras, as peças, o tabuleiro e a lista das figuras e peças já colocadas e aonde e das ainda disponíveis. As estruturas não devem ocupar muita memória (recurso escasso em um microcontrolador), mas devem permitir que as operações necessárias sejam eficientes: tentar colocar uma figura, colocá-la, retirá-la, encontrar a próxima figura ainda não testada e disponível, encontrar o próximo quadrado do tabuleiro a preecher, marcar quais são ( e como) os quadrados já preenchidos, quais as figuras e peças já utilizadas e aonde, nada que V. já não tenha aprendido em MC102/202.

• O recurso mais escasso no AVR é a SRAM (além dos registradores). Logo, é conveniente alocar na memória Flash os dados fixos (como o formato das diferentes figuras) e deixar na SRAM apenas os dados que vão ser manipulados pelo programa (como o tabuleiro).

• A maneira tradicional de construir o programa é utilizar uma busca exaustiva, recursiva, em que:
  • tenta-se achar uma figura ainda disponível e que se encaixe no próximo quadrado do tabuleiro ainda não preenchido (percorrendo o tabuleiro da esquerda para a direita e de cima para baixo, por exemplo).
  • se a figura encaixa, todas as figuras correspondentes àquela peça são marcadas como usadas, encontra-se o próximo quadrado livre e repete-se o processo (recursão)
  • se se encaixa a 12ª peça, uma solução foi encontrada.
  • se uma figura não encaixa, tentam-se todas as demais figuras ainda disponíveis
  • se nenhuma das figuras disponíveis encaixa, estamos em um caminho errado (beco-sem-saída) e é necesário RETROCEDER. Para tanto, volta-se atrás e retira-se a última figura colocada - todas as figuras da respectiva peça voltam a ser disponíveis, mas para este nível(*) é necessário continuar a tentar apenas as figuras disponíveis após a que foi retirada;
  • se, ao retroceder, não há mais figuras a tentar naquele nível, continua-se retrocedendo para os níveis anteriores, talvez voltando ao primeiro nível;
  • se tentarmos retroceder do primeiro nível, isto indica que não há mais soluções e o processo chegou ao fim;
  • após encontrar uma solução, para ncontrar a próxima, retrocede-se retirando a última peça do 12º nível, como se ela não tivesse servido e continua-se a busca que eventualmente vai encontrar a próxima solução ou, se não houver mais soluções, parar como descrito acima.

• Não nos preocuparemos em analisar se uma solução é realmente "nova" ou se trata de uma rotação ou inversão de uma solução já encontrada (ou seja, no caso de 3x20, encontraríamos 8 "soluções")

• O número de tentativas necessárias para encontrar a primeira solução pode variar dramàticamente dependendo da orientação que você adotar para o tabuleiro (dimensão maior na vertical ou na horizontal) e da ordem em que você tenta as figuras (primeiro as mais largas ou primeiro as mais altas). Em outras palavras, quanto mais cedo V. chegar a um beco sem saída, melhor.

• Um programa bem feito, em um ATMega88 a 20MHz (que é a máxima freqüência que este "chip" aceita), encontra soluções em questão de segundos. Porém, estaremos usando um emulador, que é centenas ou milhares de vezes mais lento que o "chip" real. Logo, dependendo do seu programa e da velocidade do PC em que estiver correndo o AVRStudio, prepare-se para esperar minutos por uma solução. Logo, depure seu programa passo a passo, colocando "breakpoints" ao fim de cada etapa para certificar-se que está havendo progresso e que Você nao está esperando horas por uma solução que nunca vai aparecer porque há um bug em seu programa.

  ---

  (*)no que se segue leia nível como nível de recursão; ele deve ser mantido numa pilha