Next: Ciclos Up: Enunciados Previous: Dominó

Palavras Cruzadas

Considere um puzzle de palavras cruzadas vazio. Um exemplo pode ser o especificado pelos factos

         dimensao(5). % trata-se sempre de um puzzle quadrado
preto(1,3). % significa que o quadrado 1,3 e' preto
preto(2,3).
         preto(3,2).
         preto(4,3).
         preto(5,1).
         preto(5,5).

que representam o puzzle vazio:

& & & & & & & &
Considere depois uma lista de palavras. Por exemplo

&  &  &  & 
                  &  &  &  &                   


Considere depois uma lista de palavras. Por exemplo



         palavras([do,ore,ma,lis,ur,as,po,so,pirus,oker,al,adam,ik]).

                  &  &  &  &                   


Considere depois uma lista de palavras. Por exemplo



         palavras([do,ore,ma,lis,ur,as,po,so,pirus,oker,al,adam,ik]).

& & & &
Considere depois uma lista de palavras. Por exemplo palavras([do,ore,ma,lis,ur,as,po,so,pirus,oker,al,adam,ik]). odas as palavras têm pelo menos dois caracteres. O objectivo é preencher o puzzle usando todas as palavras exactamente uma vez. Se isso for impossí
& & & &
Considere depois uma lista de palavras. Por exemplo palavras([do,ore,ma,lis,ur,as,po,so,pirus,oker,al,adam,ik]). odas as palavras têm pelo menos dois caracteres. O objectivo é preencher o puzzle usando todas as palavras exactamente uma vez. Se isso for impossvel, o predicado palavrasCruzadas/1 que irá desenvolver deve falhar. O seu programa deve dar a solução no argumento de saída do predicado palavrasCruzadas/1 e na forma de uma lista de palavras na seguinte ordem: primeiro todas as palavras na horizontal, linha por linha, conforme elas ocorrem da esquerda para a direita; depois todas as palavras na vertical, coluna por coluna.
Para o exemplo dado acima, teremos

         ?- palavrasCruzadas(L).
            L = [as,po,do,ik,ore,ma,ur,lis,adam,so,al,pirus,oker]

significando que o puzzle é preenchido da seguinte maneira:

& & & & & L & I & S &
Se existir mais do que uma solução, o seu programa deve ser capaz de as produzir por backtracking. Cada quadrado não preto pertence a uma palavra de 2 ou mais caracteres.

Next: Ciclos Up: Enunciados Previous: Dominó