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

CeNPL’02

Universidade de Coimbra / Instituto Politécnico de Coimbra

11-13 de Abril de 2002

Problema nº 3

EMPILHAR CUBOS COLORIDOS

Introdução

Suponha que tem quatro cubos. As faces destes cubos podem ser amarelas, beiges, castanhas ou douradas, sendo que cada cubo tem pelo menos uma face de cada côr. O problema consiste em empilhar os cubos de forma a que cada côr apareça nas quatro faces da pilha.

Exemplo

Note que

• é irrelevante a ordem pela qual os cubos são empilhados (e portanto pode ser considerada fixa);

• a escolha da face frontal de um cubo apenas determina a face de trás (ou vice-versa);

• a escolha da face lateral direita determina a da face lateral esquerda (ou vice-versa).

O problema pode portanto ser resolvido escolhendo primeiro as faces frente/trás e depois, face a esta escolha, escolhendo as faces laterais.

Tarefa

A tarefa é escrever um programa que solucione o problema. Para isso considere que os dados do problema (os quatro cubos) são representados pelo seguinte grafo não orientado e etiquetado:

• os nós do grafo são as quatro cores — a,b,c,d;

• para i=1,2,3,4 e para todo o par de cores (cor,cor’), existe uma aresta entre cor e cor’ etiquetada com o número i sse esse par de cores se encontra em faces opostas no cubo i.

Esta forma de representar os dados reflecte o facto da escolha de uma face de cada cubo determinar a face oposta e permite portanto restringir o espaço de pesquisa da solução.

Dados

O programa será invocado através do predicado empilha_cubos/1 com o argumento instanciado com uma lista de triplos

representando, como explicado no ponto anterior, os dados do problema.

Resultados

O seu programa deve indicar uma solução do problema mostrando no ecrã as faces frente/trás e as faces esquerda/direita dos 4 cubos.

Exemplo:

?- empilha_cubos([(a,1,b),(c,1,b),(d,1,a),
             (d,2,a),(a,2,b),(c,2,c),
             (a,3,c),(b,3,d),(d,3,c),
             (a,4,b),(d,4,d),(c,4,d)]).

        Frt/Tras Esq/Dir

Cubo 1 : d / a    c / b
Cubo 2 : c / c    b / a
Cubo 3 : b / d    a / c
Cubo 4 : a / b    d / d