Concurso/Encontro Nacional de Programação Lógica CeNPL'02

Universidade de Coimbra / Instituto Politécnico de Coimbra

11--13 de Abril de 2002


Problema no 2

Palavras Cruzadas

Introdução

Todos sabem, de certeza, o que é um jogo de palavras cruzadas. Nem vale a pena estar com grandes explicações. Aqui vamos jogar um jogo, também solitário, parecido com o das palavras cruzadas. Tal como nas palavras cruzadas clássicas, há um quadro que inicialmente tem uma série de quadrados em branco e outros preenchidos a negro. Só que, ao contrário do jogo clássico, aqui sabemos à partida quais as palavras que temos de colocar no quadro (nas palavras cruzadas só temos dicas sobre que palavras poderão ser). Não sabemos é em que posição colocar essas palavras (no jogo clássico, neste aspecto a coisa é mais facilitada, pois sabe-se sempre em que linha ou coluna deve ser colocada cada palavra). O objectivo do jogo é colocar no quadro todas as palavras dadas inicialmente , seguindo as regras usuais das palavras cruzadas (um caracter apenas por quadrado; não podem haver duas palavras consecutivas, na mesma linha ou coluna, sem que pelo meio haja pelo menos um quadrado a preto, etc).

Por exemplo, se forem dadas as palavras CENPL, PROLOG, UPA, PAI, POOP, GATO, CAO, PATITO, ANIZ, PIGET, ZIG, TPTI e o quadro da figura 1, uma solução possivel é a que se apresenta na figura 2.
                             
           
           
           
           
           
U   P O O P
P A I            R 
A      G A T O
     C E N P L
P A T I T O
  O      Z I G
Figura 1 Figura 2
O que se pretende é que faça um programa Prolog que, dados um quadro não preenchido de palavras cruzadas e uma lista de palavras a colocar, preencha o quadro com essas palavras.

Os Dados

O programa deverá ser chamado através do predicado cruzadas/0 e afixar os resultados no terminal conforme explicado abaixo.

A descrição do quadro inicial e da lista de palavras a colocar é feita, respectivamente, através dos factos quadro/1 e palavras/1, que serão adicionados ao seu programa.

O argumento do facto palavras/1 será uma lista de palavras, sendo que cada palavra (para lhe simplificar a tarefa) é dada como uma lista de caracteres. Por exemplo, se se pretender colocar a lista de palavras do exemplo acima, adiciona-se o facto: 
palavras([[c,e,n,p,l],[p,r,o,l,o,g],[u,p,a],[p,a,i],[p,o,o,p],[g,a,t,o],
          [c,a,o],[p,a,t,i,t,o],[a,n,i,z],[p,i,g,e,t],[z,i,g],[t,p,t,i]]).
O argumento do facto quadro/1 é uma matriz, representada como uma lista de listas (onde cada lista elemento corresponde a uma linha). Nessa matriz as posições correspondentes a quadrados em branco têm variáveis livres, e as correspondentes a quadrados a preto têm o símbolo `+'. Por exemplo, o quadro da figura 1 é representado por: 
quadro([[_,+,_,_,_,_],
        [_,_,_,+,+,_],
        [_,+,_,_,_,_],
        [+,_,_,_,_,_],
        [_,_,_,_,_,_],
        [+,_,+,_,_,_]]).

Os Resultados

Caso não seja possivel colocar todas as palavras no quadro, o predicado cruzadas/0 deve falhar. Se for possivel, deve escrever no ecrã o quadro preenchido com as palavras (uma linha do ecrã por linha do quadro; os quadrados preenchidos a preto devem ter o símbolo `+'; se houverem casas por preencher após a colocação de todas as palavras, no seu lugar deverá estar o símbolo `_').

Por exemplo, se chamado com os dois factos acima, o resultado deverá ser o que se apresenta à esquerda. Se, para o mesmo quadro, a lista de palavras for a acima, mas sem as duas últimas palavras (tpti e zig) o resultado será o que apresenta à direita (note o `_' na penúltima posição da última linha): 
 | ?- cruzadas.             | ?- cruzadas.

 u+poop                     u+poop
 pai++r                     pai++r
 a+gato                     a+gato
 +cenpl                     +cenpl
 patito                     patito
 +o+zig                     +o+z_g
This document was translated from LATEX by HEVEA.