Concurso/Encontro Nacional de Programação em Lógica

CeNPL'03

Universidade de Évora

9 - 11 Maio de 2003

Discos Pintados

O Problema

Pretende-se pintar um disco com n coroas circulares e 2ⁿ sectores, usando para tal apenas duas cores (preto e branco). Para que haja alguma diversidade na pintura do discos, mas que as diferenças sejam esbatidas, a pintura deverá obedecer às seguintes regras:

• cada sector em cada coroa tem apenas uma das cores
• não podem haver dois sectores exactamente com a mesma configuração de cores
• dois sectores adjacentes só podem diferir na cor de uma das suas coroas

Dos discos abaixo, ambos com n = 3, apenas o da esquerda está pintado de acordo com as regras. Quanto ao da direita, não só o padrão "preto-branco-preto" se repete (sectores indicados com setas) como existem sectores adjacentes que diferem na cor de mais do que uma coroa (o sector mais acima difere de ambos os seus adjacentes na cor das coroas mais externa e mais interna.

Tarefa

Deverá implementar o predicado pintar(N,L) que, quando chamado com N instanciado com um número inteiro positivo, devolve em L uma forma de pintar um disco com N coroas e 2^N sectores.

Os Resultados

A forma de pintar um disco é devolvida no segundo argumento do predicado pintar/2 como uma lista L. Cada elemento de L corresponde à forma de pintar cada um dos sectores do disco, sendo que elementos consecutivos correspondem a sectores adjacentes. Note que o primeiro e último elementos de L também correspondem a sectores adjacentes. Cada elemento da lista L é ele próprio uma lista de valores preto e branco, correspondendo à pintura de cada uma das coras desse sector, do seu interior para o exterior.

Por exemplo, o resultado abaixo corresponde à forma de pintar o disco da esquerda.

| ?- pintar(3,L).
L = [     [branco,branco,branco],
            [branco,branco,preto],
            [branco,preto,preto],
            [branco,preto,branco],
            [preto,preto,branco],
            [preto,preto,preto],
            [preto,branco,preto],
            [preto,branco,branco]    ];

no
| ?-