Next: Palavras Cruzadas Up: Enunciados Previous: Espiral

Dominó

Considere um conjunto de pedras de dominó. Estas pedras têm 2 números no mesmo lado, um na parte esquerda, outro na parte direita, do género do seguinte exemplo:

2 6
3 3

No jogo usual, cada participante recebe um certo número de pedras e uma pedra é colocada na mesa. Cada jogador, à vez, deve adicionar uma pedra às pedras já colocadas na mesa, ou passar. Ganha quem despachar todas as suas pedras em primeiro lugar. Para adicionar, de acordo com as regras, uma pedra na mesa, devemos encontrar uma pedra na mesa com uma parte livre contendo o número x e colocar uma pedra com lado x em contacto com o lado x livre na mesa. As pedras com dois números diferentes têm, inicialmente, dois lados livres -- um para cada número. As pedras com dois números iguais têm 3 lados livres. Quando uma pedra é colocada com um lado livre em contacto com o lado livre de outra pedra, ambos os lados livres ficam ocupados.
Aqui consideramos uma variante do jogo, chamada dominó solitário: é-lhe facultado um conjunto de pedras e o seu objectivo é terminar o jogo (todo) sozinho. Assim, deve começar por colocar uma das suas pedras na mesa (escolhe qual), e continuar a adicionar pedras, até não ter mais. Este processo pode falhar: pode não ser possível livrarmo-nos de todas as pedras.
Segue-se um exemplo. Para os factos

         pedra(2,2).
         pedra(4,6).
         pedra(1,2).
         pedra(2,4).
         pedra(6,2).

o predicado domino/1 que irá escrever, retorna, por exemplo, a lista:

         ?- domino(L).
            L = [pedra(1,2),pedra(2,2),pedra(2,4),pedra(4,6),pedra(6,2)]

Esta lista pode representar mais do que uma configuração final na mesa (veja-se a figura), mas a ordem na lista dá-nos uma ordem correcta pela qual as pedras podem ser incrementalmente adicionadas a uma configuração que é sempre correcta de acordo com as regras do jogo.

  2 6  
  2  
1 2 2  
  2 4 4 6
1 2 2 2 2 4 4 6 6 2

Next: Palavras Cruzadas Up: Enunciados Previous: Espiral


1999-04-01