99_programas_PROLOG

Prévia do material em texto

PROGRAMAS PROLOG
COLETÂNEA DE PROBLEMAS E SOLUÇÕES
Extraído, traduzido e adaptado do original disponível em:
https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/
Noventa e nove problemas e soluções em PROLOG – Prof. Joelson Nogueira de Carvalho
O objetivo desta coleção de problemas é dar a você a oportunidade de praticar suas habilidades em programação lógica. Seu objetivo deve ser encontrar a solução mais elegante dos problemas dados. A eficiência é importante, mas a clareza lógica é ainda mais crucial. Alguns dos problemas (fáceis) podem ser resolvidos trivialmente usando predicados integrados. No entanto, nesses casos, você aprende mais se tentar encontrar sua própria solução.
Cada predicado que você escreve deve começar com um comentário que descreva o predicado em uma instrução declarativa. Não descreva processualmente, o que o predicado faz, mas anote uma declaração lógica que inclua os argumentos do predicado. Você também deve indicar os tipos de dados pretendidos dos argumentos e os padrões de fluxo permitidos.
Os problemas têm diferentes níveis de dificuldade. Aqueles marcados com um único asterisco (*) são fáceis. Se você resolveu com sucesso os problemas anteriores, você deve ser capaz de resolvê-los dentro de alguns minutos (15 em média). Problemas marcados com dois asteriscos (**) são de dificuldade intermediária. Se você é um programador de Prolog habilidoso, não deve demorar mais de 30 a 90 minutos para resolvê-los. Problemas marcados com três asteriscos (***) são mais difíceis. Você pode precisar de mais tempo (por exemplo, algumas horas ou mais) para encontrar uma boa solução.
	Trabalhando com listas de Prolog
Uma lista está vazia ou é composta por um primeiro elemento (head) e uma cauda, ​​que é uma lista em si. Em Prolog, representamos a lista vazia pelo átomo [] e uma lista não vazia por um termo [H|T], onde H denota a cabeça e T denota a cauda.
	#
	Descrição
	Predicado - Examplo
	P01 (*)
	Encontrar o penúltimo elemento de uma lista.
	?- penultimo(X,[a,b,c,d]).
X = c
	P02 (*)
	Encontrar os dois últimos elementos de uma lista.
	
	P03 (*)
	Encontrar o k-ésimo elemento de uma lista.
	?-elemento_k(X,[a,b,c,d,e],3).
X = c
	P04 (*)
	Encontre o número de elementos de uma lista.
	
	P05 (*)
	Inverter uma lista.
	
	P06 (*)
	Descubra se uma lista é um palíndromo.
Um palíndromo pode ser lido para frente ou para trás; por exemplo. [x, a, m, a, x].
	
	P07 (**)
	Nivelar uma estrutura de lista aninhada.
Transforme uma lista, possivelmente mantendo listas como elementos em uma lista "linear", substituindo cada lista por seus elementos (recursivamente).
Dica: Use os predicados predefinidos is_list / 1 e append / 3
	? - nivelar ([a, [b, [c, d], e]], X).
X = [a, b, c, d, e]
	P08 (**)
	Elimina as duplicatas consecutivas dos elementos da lista. 
Se uma lista contiver elementos repetidos, eles devem ser substituídos por uma única cópia do elemento. A ordem dos elementos não deve ser alterada.
	? - comprime ([a, a, a, a, b, c, c, a, a, d, e, e, e, e], X).
X = [a, b, c, a, d, e]
	P09 (**)
	Empacotar duplicatas consecutivas de elementos da lista em sublistas.
Se uma lista contiver elementos repetidos, eles devem ser colocados em sublistas separadas.
	Exemplo:
?- pacote ([a, a, a, a, b, c, c, a, a, d, e, e, e, e], X).
X = [[a, a, a, a], [b], [c, c], [a, a], [d], [e, e, e, e]]
	P10 (*)
	Codificação de comprimento de execução de uma lista.
Use o resultado do problema P09 para implementar o método de compactação de dados de codificação de comprimento de execução. Duplicatas consecutivas de elementos são codificadas como termos [N, E] onde N é o número de duplicatas do elemento E.
	? - codifica ([a, a, a, a, b, c, c, a, a, d, e, e, e, e], X).
X = [[4, a], [1, b], [2, c], [2, a], [1, d] [4, e]]
	P11 (*)
	Codificação de comprimento de execução modificada.
Modifique o resultado do problema P10 de forma que, se um elemento não tiver duplicatas, ele seja simplesmente copiado para a lista de resultados. Apenas elementos com duplicatas são transferidos como termos [N, E].
	? - codificar_modificado ([a, a, a, a, b, c, c, a, a, d, e, e, e, e], X).
X = [[4, a], b, [2, c], [2, a], d, [4, e]]
	P12 (**)
	Decodifica uma lista codificada por comprimento de execução.
Dada uma lista de códigos de comprimento gerado conforme especificado no problema P11. Construa sua versão não compactada (inverso do problema).
	
	P13 (**)
	Codificação por comprimento de execução de uma lista (solução direta).
Implemente o método de compactação de dados de codificação de comprimento de execução diretamente. Ou seja não crie explicitamente as sublistas contendo as duplicatas, como no problema P09, mas apenas conte-as. Como no problema P11, simplifique a lista de resultados substituindo os termos com ocorrência única [1, X] por X.
	? – codificar_compr ([a, a, a, a, b, c, c, a, a, d, e, e, e, e], X).
X = [[4, a], b, [2, c], [2, a], d, [4, e]]
	P14 (*)
	Duplique os elementos de uma lista.
	? - dupli ([a, b, c, c, d], X).
X = [a, a, b, b, c, c, c, c, d, d]
	P15(**)
	Duplique os elementos de uma lista um determinado número de vezes. 
	? - dupli ([a, b, c], 3, X).
X = [a, a, a, b, b, c, c, c]
Quais são os resultados da inferência: dupli (X, 3, Y).?
	P16(**)
	Expurgar todos os n-ésimos elementos seguintes de uma lista.
	- expurgar ([a, b, c, d, e, f, g, h, i, k], 3, X).
X = [a, b, d, e, g, h, k]
	P17 (*)
	Divida uma lista em duas partes; o comprimento da primeira parte é dado. Não use predicados predefinidos.
	? - divide ([a, b, c, d, e, f, g, h, i, k], 3, L1, L2).
L1 = [a, b, c]
L2 = [d, e, f, g, h, i, k]
	P18(**)
	Extrai uma fatia de uma lista. Dados dois índices, I e K, a fatia é a lista que contém os elementos entre os elementos I'th e K'th da lista original (ambos os limites incluídos). Comece a contar os elementos a partir de 1.
	? - fatia ([a, b, c, d, e, f, g, h, i, k], 3,7, L).
X = [c, d, e, f, g]
	P19(**) 
	Gire uma lista N lugares à esquerda ou à direita(-).
Dica: Use os predicados predefinidos length / 2 e append / 3, assim como o resultado do problema P17.
	- gire ([a, b, c, d, e, f, g, h], 3, x).
X = [d, e, f, g, h, a, b, c]
- gire ([a, b, c, d, e, f, g, h], - 2, X).
X = [g, h, a, b, c, d, e, f]
	P20(*)
	Remova o elemento K'th de uma lista.
	? - remover (X, [a, b, c, d], 2, R).
X = b
R = [a, c, d]
	P21(*)
	Insere um elemento em uma determinada posição em uma lista.
	? - inserir (alfa, [a, b, c, d], 2, L).
L = [a, alfa, b, c, d]
	P22(*)
	Cria uma lista contendo todos os inteiros dentro de um determinado intervalo.
	inteiros_de((4,9, L).
L = [4,5,6,7,8,9]
	P23(**)
	Extrai um dado número de elementos selecionados aleatoriamente em uma lista. Os itens selecionados devem ser colocados em uma lista de resultados.
Dica: Use o gerador aleatório de números aleatórios / 2 e o resultado do problema P20.
	? - rnd_sel ([a, b, c, d, e, f, g, h], 3, L).
L = [e, d, a]
	P24(*)
	Loteria: Desenhe N números aleatórios diferentes do conjunto 1.M.
Os números selecionados devem ser colocados em uma lista de resultados.
	? - rnd_select (6,49, L).
L = [23,1,17,33,21,37]
	P25(*)
	Gerar uma permutação aleatória dos elementos de uma lista.
Dica: Use a solução do problema P23.
	? - rnd_permu ([a, b, c, d, e, f], L).
L = [b, a, d, c, e, f]
	P26(**)
	Gera as combinações de K objetos distintos, escolhidos dentre os N elementos de uma lista;
de quantas maneiras um comitê de 3 pode ser escolhido de um grupo de 12 pessoas? Todos nós sabemos que existem C (12,3) = 220 possibilidades (C (N, K) denota os coeficientes binomiais bem conhecidos). Para matemáticos puros, esse resultado pode ser ótimo. Mas queremos realmente gerar todas as possibilidades (via retrocesso).
	? - combinação(3, [a, b, c, d, e, f], L).
L = [a, b, c];
L = [a, b, d];
L = [a, b, e];
...
	P27a(**)
	Agrupe os elementos de um conjunto em subconjuntos disjuntos.
a) De quantas maneiras um grupo de 9 pessoas pode trabalhar em 3 subgrupos separados de 2, 3 e 4 pessoas? Escreva um predicado que gere todas as possibilidadesvia retrocesso.
	? - group3 ([aldo, beat, carla, david, evi, flip, gary, hugo, ida], G1, G2, G3).
G1 = [aldo, beat], G2 = [carla, david, evi], G3 = [virar, gary, hugo, ida]
...
	P27b(**)
	b) Generalize o predicado acima de forma que possamos especificar uma lista de tamanhos de grupo e o predicado retornará uma lista de grupos.
Note que não queremos permutações dos membros do grupo; ou seja, [[aldo, beat], ...] é a mesma solução que [[beat, aldo], ...]. No entanto, fazemos a diferença entre [[aldo, beat], [carla, david], ...] e [[carla, david], [aldo, beat], ...].
	- grupo ([aldo, beat, carla, david, evi, flip, gary, hugo, ida], [2,2,5], Gs).
Gs = [[aldo, beat], [carla, david], [evi, flip, gary, hugo, ida]]
	P28a(**)
	Classificando uma lista de listas de acordo com o tamanho das sub-listas
a) Supomos que uma lista (InList) contenha elementos que são próprios listas. O objetivo é classificar os elementos de InList de acordo com seu tamanho. Por exemplo. listas curtas primeiro, listas mais longas depois, ou vice-versa.
	- lsort ([[a, b, c], [d, e], [f, g, h], [d, e], [i, j, k, l], [m, n], [ o]], L).
L = [[o], [d, e], [d, e], [m, n], [a, b, c], [f, g, h], [i, j, k, l] ]
	P28b(**)
	b) Mais uma vez, supomos que uma lista (InList) contém elementos que são próprios listas. Mas desta vez o objetivo é classificar os elementos da InList de acordo com sua freqüência de comprimento; ou seja, no padrão, onde a classificação é feita de forma crescente, as listas com comprimentos raros são colocadas primeiro, outras com um comprimento mais frequente vêm depois.
Note que no Exemplo acima, as duas primeiras listas no resultado L têm comprimento 4 e 1, ambos os comprimentos aparecem apenas uma vez. A terceira e quarta lista tem comprimento 3, que aparece, há duas listas desse tamanho. E finalmente, as últimas três listas têm comprimento 2. Este é o comprimento mais frequente.
	- lfsort ([[a, b, c], [d, e], [f, g, h], [d, e], [i, j, k, l], [m, n], [ o]], L).
L = [[i, j, k, l], [o], [a, b, c], [f, g, h], [d, e], [d, e], [m, n] ]
	Problemas Aritméticos
	#
	Descrição
	Predicado - Examplo
	
P31 (**)
	Determine se um número inteiro é primo
	?- is_prime(7).
Yes
	P32 (**)
	Determine o maior divisor comum de dois números inteiros positivos (algoritmo de Euclides). 
Definir gcd como uma função aritmética; então você pode usá-lo assim: gcd(36,63).
	?- gcd(36, 63, G).
G = 9
Yes
?- G is gcd(36,63).
G = 9
Yes
	P33 (*)
	Determine se dois números inteiros positivos são coprime.
Dois números são coprime se seu maior divisor comum for igual a 1.
	?- coprime(35, 64).
Yes
	P34 (**)
	Calcule a função totiente de Euler phi (m). A chamada função totiente phi (m) de Euler é definida como o número de inteiros positivos r (1 <= r <m) que são coprime para m.
Exemplo: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note o caso especial: phi(1) = 1.
Descubra qual é o valor de phi (m) se m é um número primo. A função totiente de Euler desempenha um papel importante em um dos métodos de criptografia de chave pública (RSA) mais usados. Neste exercício, você deve usar o método mais primitivo para calcular esta função (existem maneiras mais inteligentes para isso).
	?- Phi is totient_phi(10).
Phi = 4
Yes
	P35 (**)
	Determine os fatores primos de um número inteiro positivo.
Construa uma lista simples contendo os principais fatores em ordem crescente.
	?- prime_factors(315, L).
L = [3,3,5,7]
	P36 (**)
	Determine os fatores primos de um número inteiro positivo. Construa uma lista contendo os fatores primos e sua multiplicidade.
Dica: Similar ao problema 13.
	?- prime_factors_mult(315, L).
L = [[3,2],[5,1],[7,1]]
	P37 (**)
	Calcule a função totiente de Euler phi (m) (aprimorada). Veja o problema P34 para a definição da função totiente de Euler. Se a lista dos fatores primos de um número m for conhecida na forma do problema P36, a função phi (m) poderá ser eficientemente calculada da seguinte forma: Seja [[p1, m1], [p2, m2], [p3, m3], ...] seja a lista de fatores primos (e suas multiplicidades) de um determinado número m. Então phi (m) pode ser calculado com a seguinte fórmula
phi(m) = (p1 - 1) * p1**(m1 - 1) * (p2 - 1) * p2**(m2 - 1) * (p3 - 1) * p3**(m3 - 1) * ...
Nota: a ** b representa a b'ésima potência de a.
	
	P38 (*)
	Compare os dois métodos de cálculo da função totiente de Euler.
Use as soluções dos problemas P34 e P37 para comparar os algoritmos. Tome o número de inferências lógicas como uma medida de eficiência. Tente calcular phi (10090) como um exemplo.
	
	P39 (*)
	Uma lista de números primos. Dado um intervalo de números inteiros pelo seu limite inferior e superior, construa uma lista de todos os números primos nesse intervalo.
	
	P40 (**)
	Conjectura de Goldbach.
A conjectura de Goldbach diz que todo número par positivo maior que 2 é a soma de dois números primos. Exemplo: 28 = 5 + 23. É um dos fatos mais famosos da teoria dos números que não se provou correto no caso geral. Foi confirmado numericamente até números muito grandes (muito maiores do que o nosso sistema Prolog). Escreva um predicado para encontrar os dois números primos que somam um número inteiro par.
	?- goldbach(28, L).
L = [5,23]
Yes
	P41 (**)
	Uma lista de composições de Goldbach. Dado um intervalo de números inteiros pelo limite inferior e superior, imprima uma lista de todos os números pares e sua composição Goldbach.
Na maioria dos casos, se um número par for escrito como a soma de dois números primos, um deles será muito pequeno. Muito raramente, os números primos são maiores do que 50. Tente descobrir quantos casos existem no intervalo 2..3000.
Exemplo (para um limite de impressão de 50):
	?- goldbach_list(9,20).
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17
?- goldbach_list(1,2000,50).
992 = 73 + 919
1382 = 61 + 1321
1856 = 67 + 1789
1928 = 61 + 1867
	Lógica e Códigos
	P46 (**)
	Tabelas verdade para expressões lógicas.
Definir predicados and / 2, or / 2, nand / 2, nor / 2, xor / 2, impl / 2 e equ / 2 (para equivalência lógica) que são bem-sucedidos ou falham de acordo com o resultado de suas respectivas operações; por exemplo. and(A, B) terá sucesso, se e somente se A e B tiverem sucesso. Observe que A e B podem ser objetivos do Prolog (não apenas as constantes verdadeiras e falhas).
Uma expressão lógica em duas variáveis ​​pode ser escrita em notação de prefixo, como no exemplo a seguir: and (or(A, B), nand (A, B)).
Agora, escreva uma tabela de predicado / 3 que imprima a tabela verdade de uma determinada expressão lógica em duas variáveis.
	?- table(A,B,and(A,or(A,B))).
true true true
true fail true
fail true fail
fail fail fail
No.
	P47 (*)
	Tabelas verdade para expressões lógicas (2). Continue o problema P46, definindo e / 2, ou / 2, etc. como operadores. Isso permite escrever a expressão lógica da maneira mais natural, como no Exemplo: A e (A ou não B). Defina a precedência do operador como de costume; ou seja, como em Java.
	?- table(A,B, A and (A or not B)).
true true true
true fail true
fail true fail
fail fail fail
	P48 (**)
	Tabelas verdade para expressões lógicas (3). Generalize o problema P47 de maneira que a expressão lógica possa conter qualquer número de variáveis ​​lógicas. Defina a tabela / 2 de maneira que a tabela (Lista, Expr) imprima a tabela verdade para a expressão Expr, que contém as variáveis ​​lógicas enumeradas na Lista
	?- table([A,B,C], A and (B or C) equ A and B or A and C).
true true true true
true true fail true
true fail true true
true fail fail true
fail true true true
fail true fail true
fail fail true true
fail fail fail true
	P49 (***)
	O Código Gray.
Um código Gray de n bits é uma sequência de seqüências de n bits construídas de maneira  não ponderada onde de um número para outro apenas um bit varia: 
n = 1: C(1) = ['0','1'].
n = 2: C(2) = ['00','01','11','10'].
n = 3: C(3) = ['000','001','011','010',´110´,´111´,´101´,´100´].
Veja a tabela de conversão para n=4:
	Código decimal
	Código Binário
	Código Gray
	0
	0000
	0000
	1
	0001
	0001
	2
	00100011
	3
	0011
	0010
	4
	0100
	0110
	5
	0101
	0111
	6
	0110
	0101
	7
	0111
	0100
	8
	1000
	1100
	9
	1001
	1101
	10
	1010
	1111
	11
	1011
	1110
	12
	1100
	1010
	13
	1101
	1011
	14
	1110
	1001
	15
	1111
	1000
Descubra as regras de construção e escreva um predicado com a seguinte especificação:
% gray(N, C): - C é o código cinza de N bits
	
	P50 (***)
	O Código Huffman.
Antes de tudo, consulte um bom livro sobre matemática ou algoritmos discretos para obter uma descrição detalhada dos códigos de Huffman!
Supomos um conjunto de símbolos com suas frequências, dados como uma lista de termos fr(S, F).
Exemplo: [fr (a, 45), fr (b, 13), fr (c, 12), fr (d, 16), fr (e, 9), fr (f, 5)]. 
Nosso objetivo é construir uma lista de termos hc(S, C), onde C é a palavra de código Huffman para o símbolo S.
No nosso exemplo, o resultado pode ser Hs = [hc (a, '0'), hc (b , '101'), hc (c, '100'), hc (d, '111'), hc (e, '1101'), hc (f, '1100')] [hc (a, '01 ' ), ... etc.] A tarefa deve ser realizada pelo predicado huffman / 2 definido da seguinte maneira:
% huffman (Fs, Hs): - Hs é a tabela de códigos Huffman para a tabela de frequências Fs
	?- huffman (Fs, Hs).
[hc (a, '0'), hc (b , '101'), hc (c, '100'), hc (d, '111'), hc (e, '1101'), hc (f, '1100')] [hc (a, '01 ' ), ... ]
	Árvores Binárias: Uma árvore binária está vazia ou é composta por um elemento raiz e dois sucessores, que são as próprias árvores binárias...
Em Prolog, representamos a árvore vazia pelo átomo 'nil' e a árvore não vazia pelo termo t (X, L, R), onde X denota o nó raiz e L e R denotam a subárvore esquerda e direita, respectivamente. 
A árvore Exemplo representada abaixo é, portanto, representada pelo seguinte termo Prolog:
T1 = t(a,t(b,t(d,nil,nil),t(e,nil,nil)),t(c,nil,t(f,t(g,nil,nil),nil))) 
Outros exemplos são uma árvore binária que consiste apenas em um nó raiz:
T2 = t (a, nil, nil) ou uma árvore binária vazia: T3 = nil.
	P54 (**)
	Verifique se um determinado termo representa uma árvore binária Escreva um predicado istree / 1 que seja bem-sucedido se, e somente se, seu argumento for um termo Prolog representando uma árvore binária
	?- istree(t(a,t(b,nil,nil),nil)).
Yes
?- istree(t(a,t(b,nil,nil))).
No
	P55 (**)
	Construa árvores binárias completamente equilibradas
Em uma árvore binária completamente equilibrada, a seguinte propriedade é válida para cada nó: O número de nós na subárvore esquerda e o número de nós na subárvore direita são quase iguais, o que significa que a diferença não é maior que um.
Escreva um predicado cbal_tree / 2 para construir árvores binárias completamente equilibradas para um determinado número de nós. O predicado deve gerar todas as soluções via backtracking. Coloque a letra 'x' como informação em todos os nós da árvore.
	?- cbal_tree(4,T).
T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ;
T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil)) ;
etc......No
	P56 (**)
	Árvores binárias simétricas
Vamos chamar uma árvore binária de simétrica se você pode desenhar uma linha vertical através do nó raiz e, em seguida, a subárvore direita é a imagem espelhada da subárvore esquerda. Escreva um predicado simétrico / 1 para verificar se uma determinada árvore binária é simétrica. Dica: Escreva um espelho predicado / 2 primeiro para verificar se uma árvore é a imagem espelhada de outra. Estamos interessados ​​apenas na estrutura, não no conteúdo dos nós.
	
	P57 (**)
	Árvores de pesquisa binária (dicionários)
Use o predicado add / 3, para escrever um predicado para construir uma árvore de pesquisa binária a partir de uma lista de números inteiros.
Em seguida, use esse predicado para testar a solução do problema P56
	?- construct([3,2,5,7,1],T).
T = t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))
?- test_symmetric([5,3,18,1,4,12,21]).
Yes
?- test_symmetric([3,2,5,7,4]).
No
	P58 (**)
	Paradigma de geração e teste: Aplique o paradigma de geração e teste para construir todas as árvores binárias simétricas e completamente balanceadas com um determinado número de nós. 
Quantas árvores existem com 57 nós? 
Investigue sobre quantas soluções existem para um determinado número de nós? E se o número for par? Escreva um predicado apropriado.
	?- sym_cbal_trees(5,Ts).
Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))] 
	P59 (**)
	Construir árvores binárias com altura equilibrada
Em uma árvore binária com altura equilibrada, a seguinte propriedade é válida para cada nó: A altura de sua subárvore esquerda e a altura de sua subárvore direita são quase iguais, o que significa que sua diferença não é maior que uma.
Escreva um predicado hbal_tree / 2 para construir árvores binárias com altura equilibrada para uma determinada altura. O predicado deve gerar todas as soluções via backtracking. Coloque a letra 'x' como informação em todos os nós da árvore.
	?- hbal_tree(3,T).
T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil))) ;
T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil)) ;
etc......No
	P60 (**)
	Construa árvores binárias com altura equilibrada com um número determinado de nós;
Considere uma árvore binária de altura H. com altura equilibrada. Qual é o número máximo de nós que ela pode conter?
Claramente, MaxN = 2 ** H - 1. 
No entanto, qual é o número mínimo MinN? Esta questão é mais difícil. Tente encontrar uma declaração recursiva e transformá-la em um predicado minNodes / 2 definido como segue:
% minNodes (H, N): - N é o número mínimo de nós em uma árvore binária com altura H.
(inteiro, inteiro), (+ ,?)
Por outro lado, podemos perguntar: qual é a altura máxima H que uma árvore binária com altura de N com nós pode ter?
% maxHeight (N, H): - H é a altura máxima de uma árvore binária equilibrada em altura com N nós
(inteiro, inteiro), (+ ,?)
Agora, podemos atacar o principal problema: construir todas as árvores binárias com altura equilibrada com um determinado nuber de nós.
% hbal_tree_nodes (N, T): - T é uma árvore binária com altura de N e N nós.
Descubra quantas árvores de altura equilibrada existem para N = 15.
	
	P61 (**)
	Contar as folhas de uma árvore binária Uma folha é um nó sem sucessores. Escreva um predicado count_leaves / 2 para contá-los.
	count_leaves(T,N) :- A árvore binária T tem N folhas.
	P61A(**)
	Colete as folhas de uma árvore binária em uma lista Uma folha é um nó sem sucessores. Escreva um predicado leaves / 2 para coletá-los em uma lista.
	leaves(T,S) :- S é a lista de todas as folhas da árvore binária T.
	P62 (*)
	Coletar os nós internos de uma árvore binária em uma lista
Um nó interno de uma árvore binária possui um ou dois sucessores não vazios. Escreva um predicado interno / 2 para coletá-los em uma lista
	internals(T,S) :- S é a lista de nós internos da árvore binária T. 
	P62B (*)
	Colete os nós em um determinado nível em uma lista
Um nó de uma árvore binária está no nível N se o caminho da raiz para o nó tiver comprimento N-1. O nó raiz está no nível 1. Escreva um predicado atlevel / 3 para coletar todos os nós em um determinado nível em uma lista.
Usando atlevel / 3, é fácil construir um predicado levelorder / 2 que cria a sequência de ordem de nível dos nós. No entanto, existem maneiras mais eficientes de fazer isso.
	atlevel(T,L,S) :- S é a lista de nós da árvore binária T no nível L
	P63 (**)
	Construir uma árvore binária completa
Uma árvore binária completa com altura H é definida da seguinte forma: Os níveis 1,2,3, ..., H-1 contêm o número máximo de nós (ou seja, 2 ** (i-1) no nível i, observe que começamos a contar os níveis de 1 na raiz). No nível H, que pode conter menos do que o número máximo possível de nós, todos os nós são "ajustados à esquerda". Isso significa que, em uma travessia de árvore de ordem de nível, todos os nós internos vêm primeiro, as folhas vêm em segundo e sucessores vazios (os nulos que não são realmente nós!) Vêm por último.
Particularmente, árvores binárias completassão usadas como estruturas de dados (ou esquemas de endereçamento) para pilhas.
Podemos atribuir um número de endereço para cada nó em uma árvore binária completa, enumerando os nós na ordem de nível, começando na raiz com o número 1. Ao fazer isso, percebemos que para cada nó X com endereço A, a seguinte propriedade é válida: dos sucessores esquerdo e direito de X são 2 * A e 2 * A + 1, respectivamente, supostamente os sucessores existem. Esse fato pode ser usado para construir elegantemente uma estrutura completa de árvore binária. Escreva um predicado complete_binary_tree / 2 com a seguinte especificação:
	complete_binary_tree(N,T) :- T é uma árvore binária completa com N nodes. (+,?)
	P64 (**)
	Layout de uma árvore binária (1)
Dada uma árvore binária como o termo Prolog usual t (X, L, R) (ou nulo). Como preparação para desenhar a árvore, é necessário um algoritmo de layout para determinar a posição de cada nó em uma grade retangular. Vários métodos de layout são concebíveis, um deles é mostrado na ilustração abaixo.
Nesta estratégia de layout, a posição de um nó v é obtida pelas duas regras a seguir:
· x (v) é igual à posição do nó v na sequência de pedidos não solicitados
· y (v) é igual à profundidade do nó v na árvore
Para armazenar a posição dos nós, estendemos o termo Prolog representando um nó (e seus sucessores) da seguinte maneira:
% nil representa a árvore vazia (como de costume)
% t (W, X, Y, L, R) representa uma árvore binária (não vazia) com a raiz W "posicionada" em (X, Y) e subárvores L e R.
	layout_binary_tree / 2:
layout_binary_tree(T,PT) :- PT é a árvore binária posicionada, obtida da árvore binária T. (+,?)
	P65 (**)
	Um método de layout alternativo é mostrado na ilustração ao lado. Descubra as regras e escreva o predicado correspondente do Prolog. Dica: em um determinado nível, a distância horizontal entre os nós vizinhos é constante. Use as mesmas convenções do problema P64 e teste seu predicado de maneira apropriada.
	
	P66(***)
	Ainda outra estratégia de layout é mostrada na ilustração ao lado. O método produz um layout muito compacto, mantendo uma certa simetria em cada nó. Descubra as regras e escreva o predicado correspondente do Prolog. Dica: considere a distância horizontal entre um nó e seus nós sucessores. Quão forte você pode juntar duas subárvores para construir a árvore binária combinada?
Use as mesmas convenções dos problemas P64 e P65 e teste seu predicado de maneira apropriada. Nota: Este é um problema difícil. Não desista cedo demais!
Qual layout você mais gosta?
	
	P67 (**)
	Uma representação em cadeia de árvores binárias
Podemos representar árvores binárias como sequências do seguinte tipo:
 a (b (d, e), c (, f (g,))))
a) Escreva um predicado Prolog que gere essa representação de string, se a árvore for fornecida como de costume (como nulo ou t (X, L, R)). Em seguida, escreva um predicado que faça isso inverso; ou seja, dada a representação da string, construa a árvore da forma usual. Por fim, combine os dois predicados em um único predicado tree_string / 2, que pode ser usado nas duas direções.
b) Escreva o mesmo predicado tree_string / 2 usando listas de diferenças e um único predicado tree_dlist / 2 que faz a conversão entre uma árvore e uma lista de diferenças nas duas direções.
Para simplificar, suponha que as informações nos nós sejam uma única letra e não haja espaços na sequência.
	
	P68 (**)
	Sequências de pré-encomenda e inorder de árvores binárias:
Consideramos árvores binárias com nós que são identificados por letras minúsculas únicas, como no Exemplo do problema P67.
a) Escreva predicados pré-encomenda / 2 e inorder / 2 que constroem a sequência de pré-encomenda e inorder de uma determinada árvore binária, respectivamente. Os resultados devem ser átomos, p. 'abdecfg' para a sequência de pré-encomendas do Exemplo no problema P67.
b) Você pode usar a pré-encomenda / 2 da parte problemática a) na direção inversa; ou seja, dada uma sequência de pré-encomenda, construa uma árvore correspondente? Caso contrário, faça as providências necessárias.
c) Se a sequência de pré-encomenda e a sequência de inorder dos nós de uma árvore binária forem fornecidas, a árvore será determinada sem ambiguidade. Escreva um predicado pre_in_tree / 3 que faça o trabalho.
d) Resolver problemas de a) a c) usando listas de diferenças. Legal! Use o tempo predicado predefinido / 1 para comparar as soluções.
O que acontece se o mesmo caractere aparecer em mais de um nó. Tente, por exemplo, pre_in_tree (aba, baa, T).
	
	P69 (**)
	Representação de string de árvores binárias:
Consideramos novamente árvores binárias com nós que são identificados por letras minúsculas únicas, como no Exemplo do problema P67.
Essa árvore pode ser representada pela sequência de pré-ordem de seus nós, na qual os pontos (.) São inseridos onde uma subárvore vazia (nula) é encontrada durante o percurso da árvore. Para Exemplo, a árvore mostrada no problema P67 é representada como 'abd..e..c.fg ...'. Primeiro, tente estabelecer uma sintaxe (BNF ou diagramas de sintaxe) e depois escreva um predicado tree_dotstring / 2 que faz a conversão nas duas direções. 
Use listas de diferenças.
	
	Árvores Multiway:
Uma árvore de múltiplas vias é composta por um elemento raiz e um conjunto (possivelmente vazio) de sucessores que são as próprias árvores de múltiplas vias. Uma árvore de várias vias nunca está vazia. O conjunto de árvores sucessoras às vezes é chamado de floresta.
No Prolog, representamos uma árvore de múltiplas vias por um termo t (X, F), onde X denota o nó raiz e F denota a floresta de árvores sucessoras (uma lista Prolog). A árvore Exemplo representada ao contrário é, portanto, representada pelo seguinte termo Prolog:
T = t (a, [t (f, [t (g, [])]), t (c, []), t (b, [t (d, []), t (e, []) ])])
	P70(**)
	Construção de árvore a partir de uma sequência de nós:
Supomos que os nós de uma árvore de múltiplas vias contenham caracteres únicos.
Na sequência de primeira ordem de profundidade de seus nós, um caractere especial é inserido sempre que, durante a travessia da árvore, o movimento é uma volta ao nível anterior. 
Por essa regra, a árvore na figura ao lado é representada como: afg ^^ c ^ bd ^ e ^^^ 
Defina a sintaxe da string e escreva uma árvore predicada (String, Tree) para construir a Tree quando a String for fornecida. 
Trabalhe com átomos (em vez de cadeias). Faça seu predicado funcionar nas duas direções.
	
	P70B(*)
	Verifique se um determinado termo representa uma árvore de múltiplas vias
Escreva um predicado istree / 1 que seja bem-sucedido se, e somente se, seu argumento for um termo Prolog representando uma árvore de múltiplas vias.
	istree(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])).
Yes
	P70C(*)
	Contar os nós de uma árvore de várias vias
Escreva um nó predicado / 1 que conte os nós de uma determinada árvore de múltiplas vias.
Escreva outra versão do predicado que permita um padrão de fluxo (o, i).
	nnodes(t(a,[t(f,[])]),N).
N = 2
	P71(*)
	Determina o comprimento do caminho interno de uma árvore:
Definimos o comprimento do caminho interno de uma árvore de múltiplas vias como a soma total dos comprimentos do caminho da raiz para todos os nós da árvore. 
Por essa definição, a árvore na figura do problema P70 possui um comprimento de caminho interno igual a 9. Escreva um IPL predicado (Árvore, IPL) para o padrão de fluxo (+, -).
	
	P72(*)
	Construa a sequência de ordem de baixo para cima dos nós da árvore.
Escreva um predicado bottom_up (Tree, Seq) que construa a sequência bottom-up dos nós da árvore de múltiplas vias. Seq deve ser uma lista de Prolog. 
O que acontece se você executar suas senhas predicadas?
	
	
	Representação em árvore do tipo Lisp:
Há uma notação específica para árvores de várias vias no Lisp. Lisp é uma linguagem de programação funcional proeminente, usada principalmente para problemas de inteligência artificial. Como tal, é um dos principais concorrentesdo Prolog.
No Lisp, quase tudo é uma lista, assim como no Prolog, tudo é um termo.
As figuras a seguir mostram como as estruturas de árvores de múltiplas vias são representadas no Lisp.
Observe que na notação "lispy" um nó com sucessores (filhos) na árvore é sempre o primeiro elemento de uma lista, seguido por seus filhos. 
A representação "lispy" de uma árvore de múltiplas vias é uma sequência de átomos e parênteses '(' e ')', que chamaremos coletivamente de "tokens". Podemos representar essa sequência de tokens como uma lista de Prolog; por exemplo. a expressão lispy (a (b c)) pode ser representada como a lista Prolog ['(', a, '(', b, c, ')', ')']. 
Escreva um predicado tree_ltl (T, LTL) que construa a LTL da "lista de tokens lispy" se a árvore for fornecida como termo T na notação Prolog usual. 
Como um segundo exercício, ainda mais interessante, tente reescrever tree_ltl / 2 de uma maneira que a conversão inversa também seja possível: Dada a lista LTL, construa a árvore Prolog T. Use as listas de diferenças.
	? - tree_ltl (t (a, [t (b, []), t (c, [])]), LTL). LTL = ['(', a, '(', b, c, ')', ')']
	
	
	
	
	
	
	
	
	
Graphs
A graph is defined as a set of nodes and a set of edges, where each edge is a pair of nodes.
There are several ways to represent graphs in Prolog. One method is to represent each edge separately as one clause (fact). In this form, the graph depicted below is represented as the following predicate:
edge(h,g).
edge(k,f).
edge(f,b).
...
We call this edge-clause form. Obviously, isolated nodes cannot be represented. Another method is to represent the whole graph as one data object. According to the definition of the graph as a pair of two sets (nodes and edges), we may use the following Prolog term to represent the Exemplo graph:
graph([b,c,d,f,g,h,k],[e(b,c),e(b,f),e(c,f),e(f,k),e(g,h)])
We call this graph-term form. Note, that the lists are kept sorted, they are really sets, without duplicated elements. Each edge appears only once in the edge list; i.e. an edge from a node x to another node y is represented as e(x,y), the term e(y,x) is not present. The graph-term form is our default representation. In SWI-Prolog there are predefined predicates to work with sets.
A third representation method is to associate with each node the set of nodes that are adjacent to that node. We call this the adjacency-list form. In our Exemplo:
[n(b,[c,f]), n(c,[b,f]), n(d,[]), n(f,[b,c,k]), ...]
The representations we introduced so far are Prolog terms and therefore well suited for automated processing, but their syntax is not very user-friendly. Typing the terms by hand is cumbersome and error-prone. We can define a more compact and "human-friendly" notation as follows: A graph is represented by a list of atoms and terms of the type X-Y (i.e. functor '-' and arity 2). The atoms stand for isolated nodes, the X-Y terms describe edges. If an X appears as an endpoint of an edge, it is automatically defined as a node. Our Exemplo could be written as:
[b-c, f-c, g-h, d, f-b, k-f, h-g]
We call this the human-friendly form. As the Exemplo shows, the list does not have to be sorted and may even contain the same edge multiple times. Notice the isolated node d. (Actually, isolated nodes do not even have to be atoms in the Prolog sense, they can be compound terms, as in d(3.75,blue) instead of d in the Exemplo).
When the edges are directed we call them arcs. These are represented by ordered pairs. Such a graph is called directed graph. To represent a directed graph, the forms discussed above are slightly modified. The Exemplo graph opposite is represented as follows:
Arc-clause form
arc(s,u).
arc(u,r).
...
Graph-term form
digraph([r,s,t,u,v],[a(s,r),a(s,u),a(u,r),a(u,s),a(v,u)])
Adjacency-list form
[n(r,[]),n(s,[r,u]),n(t,[]),n(u,[r]),n(v,[u])]
Note that the adjacency-list does not have the information on whether it is a graph or a digraph.
Human-friendly form
[s > r, t, u > r, s > u, u > s, v > u]
Finally, graphs and digraphs may have additional information attached to nodes and edges (arcs). For the nodes, this is no problem, as we can easily replace the single character identifiers with arbitrary compound terms, such as city('London',4711). On the other hand, for edges we have to extend our notation. Graphs with additional information attached to edges are called labelled graphs.
Arc-clause form
arc(m,q,7).
arc(p,q,9).
arc(p,m,5).
Graph-term form
digraph([k,m,p,q],[a(m,p,7),a(p,m,5),a(p,q,9)])
Adjacency-list form
[n(k,[]),n(m,[q/7]),n(p,[m/5,q/9]),n(q,[])]
Notice how the edge information has been packed into a term with functor '/' and arity 2, together with the corresponding node.
Human-friendly form
[p>q/9, m>q/7, k, p>m/5]
The notation for labelled graphs can also be used for so-called multi-graphs, where more than one edge (or arc) are allowed between two given nodes.
P80 (***) Conversions
Write predicates to convert between the different graph representations. With these predicates, all representations are equivalent; i.e. for the following problems you can always pick freely the most convenient form. The reason this problem is rated (***) is not because it's particularly difficult, but because it's a lot of work to deal with all the special cases.
P81 (**) Path from one node to another one
Write a predicate path(G,A,B,P) to find an acyclic path P from node A to node b in the graph G. The predicate should return all paths via backtracking.
P82 (*) Cycle from a given node
Write a predicate cycle(G,A,P) to find a closed path (cycle) P starting at a given node A in the graph G. The predicate should return all cycles via backtracking.
P83 (**) Construct all spanning trees
Write a predicate s_tree(Graph,Tree) to construct (by backtracking) all spanning trees of a given graph. With this predicate, find out how many spanning trees there are for the graph depicted to the left. The data of this Exemplo graph can be found in the file p83.dat. When you have a correct solution for the s_tree/2 predicate, use it to define two other useful predicates: is_tree(Graph) and is_connected(Graph). Both are five-minutes tasks!
P84 (**) Construct the minimal spanning tree
Write a predicate ms_tree(Graph,Tree,Sum) to construct the minimal spanning tree of a given labelled graph. Hint: Use the algorithm of Prim. A small modification of the solution of P83 does the trick. The data of the Exemplo graph to the right can be found in the file p84.dat.
P85 (**) Graph isomorphism
Two graphs G1(N1,E1) and G2(N2,E2) are isomorphic if there is a bijection f: N1 -> N2 such that for any nodes X,Y of N1, X and Y are adjacent if and only if f(X) and f(Y) are adjacent.
Write a predicate that determines whether two graphs are isomorphic. Hint: Use an open-ended list to represent the function f.
P86 (**) Node degree and graph coloration
a) Write a predicate degree(Graph,Node,Deg) that determines the degree of a given node.
b) Write a predicate that generates a list of all nodes of a graph sorted according to decreasing degree.
c) Use Welch-Powell's algorithm to paint the nodes of a graph in such a way that adjacent nodes have different colors.
P87 (**) Depth-first order graph traversal (alternative solution)
Write a predicate that generates a depth-first order graph traversal sequence. The starting point should be specified, and the output should be a list of nodes that are reachable from this starting point (in depth-first order).
P88 (**) Connected components (alternative solution)
Write a predicate that splits a graph into its connected components.
P89 (**) Bipartite graphs
Write a predicate that finds out whether a given graph is bipartite.
Miscellaneous Problems
P90 (**) Eight queens problem
This is a classical problem in computer science. The objective is to place eight queens on a chessboard so that no two queens are attacking each other; i.e., no two queens are in the same row, the same column, or on the same diagonal.
Hint: Represent the positions of the queens as a list of numbers 1..N. Exemplo: [4,2,7,3,6,8,5,1]means that the queen in the first column is in row 4, the queen in the second column is in row 2, etc. Use the generate-and-test paradigm.
P91 (**) Knight's tour
Another famous problem is this one: How can a knight jump on an NxN chessboard in such a way that it visits every square exactly once?
Hints: Represent the squares by pairs of their coordinates of the form X/Y, where both X and Y are integers between 1 and N. (Note that '/' is just a convenient functor, not division!) Define the relation jump(N,X/Y,U/V) to express the fact that a knight can jump from X/Y to U/V on a NxN chessboard. And finally, represent the solution of our problem as a list of N*N knight positions (the knight's tour).
P92 (***) Von Koch's conjecture
Several years ago I met a mathematician who was intrigued by a problem for which he didn't know a solution. His name was Von Koch, and I don't know whether the problem has been solved since.
 
Anyway the puzzle goes like this: Given a tree with N nodes (and hence N-1 edges). Find a way to enumerate the nodes from 1 to N and, accordingly, the edges from 1 to N-1 in such a way, that for each edge K the difference of its node numbers equals to K. The conjecture is that this is always possible.
For small trees the problem is easy to solve by hand. However, for larger trees, and 14 is already very large, it is extremely difficult to find a solution. And remember, we don't know for sure whether there is always a solution!
Write a predicate that calculates a numbering scheme for a given tree. What is the solution for the larger tree pictured above?
P93 (***) An arithmetic puzzle
Given a list of integer numbers, find a correct way of inserting arithmetic signs (operators) such that the result is a correct equation. Exemplo: With the list of numbers [2,3,5,7,11] we can form the equations 2-3+5+7 = 11 or 2 = (3*5+7)/11 (and ten others!).
P94 (***) Generate K-regular simple graphs with N nodes
In a K-regular graph all nodes have a degree of K; i.e. the number of edges incident in each node is K. How many (non-isomorphic!) 3-regular graphs with 6 nodes are there? See also a table of results and a Java applet that can represent graphs geometrically.
P95 (**) English number words
On financial documents, like cheques, numbers must sometimes be written in full words. Exemplo: 175 must be written as one-seven-five. Write a predicate full_words/1 to print (non-negative) integer numbers in full words.
P96 (**) Syntax checker (alternative solution with difference lists)
In a certain programming language (Ada) identifiers are defined by the syntax diagram (railroad chart) opposite. Transform the syntax diagram into a system of syntax diagrams which do not contain loops; i.e. which are purely recursive. Using these modified diagrams, write a predicate identifier/1 that can check whether or not a given string is a legal identifier.
% identifier(Str) :- Str is a legal identifier 
P97 (**) Sudoku
Sudoku puzzles go like this:
 Problem statement Solution
 . . 4 | 8 . . | . 1 7	 9 3 4 | 8 2 5 | 6 1 7	 
 | | | |
 6 7 . | 9 . . | . . .	 6 7 2 | 9 1 4 | 8 5 3
 | | | |
 5 . 8 | . 3 . | . . 4 5 1 8 | 6 3 7 | 9 2 4
 --------+---------+-------- --------+---------+--------
 3 . . | 7 4 . | 1 . . 3 2 5 | 7 4 8 | 1 6 9
 | | | |
 . 6 9 | . . . | 7 8 . 4 6 9 | 1 5 3 | 7 8 2
 | | | |
 . . 1 | . 6 9 | . . 5 7 8 1 | 2 6 9 | 4 3 5
 --------+---------+-------- --------+---------+--------
 1 . . | . 8 . | 3 . 6	 1 9 7 | 5 8 2 | 3 4 6
 | | | |
 . . . | . . 6 | . 9 1	 8 5 3 | 4 7 6 | 2 9 1
 | | | |
 2 4 . | . . 1 | 5 . . 2 4 6 | 3 9 1 | 5 7 8
 
Every spot in the puzzle belongs to a (horizontal) row and a (vertical) column, as well as to one single 3x3 square (which we call "square" for short). At the beginning, some of the spots carry a single-digit number between 1 and 9. The problem is to fill the missing spots with digits in such a way that every number between 1 and 9 appears exactly once in each row, in each column, and in each square.
P98 (***) Nonograms
Around 1994, a certain kind of puzzles was very popular in England. The "Sunday Telegraph" newspaper wrote: "Nonograms are puzzles from Japan and are currently published each week only in The Sunday Telegraph. Simply use your logic and skill to complete the grid and reveal a picture or diagram." As a Prolog programmer, you are in a better situation: you can have your computer do the work! Just write a little program ;-).
The puzzle goes like this: Essentially, each row and column of a rectangular bitmap is annotated with the respective lengths of its distinct strings of occupied cells. The person who solves the puzzle must complete the bitmap given only these lengths.
 Problem statement: Solution:
 |_|_|_|_|_|_|_|_| 3 |_|X|X|X|_|_|_|_| 3 
 |_|_|_|_|_|_|_|_| 2 1 |X|X|_|X|_|_|_|_| 2 1 
 |_|_|_|_|_|_|_|_| 3 2 |_|X|X|X|_|_|X|X| 3 2 
 |_|_|_|_|_|_|_|_| 2 2 |_|_|X|X|_|_|X|X| 2 2 
 |_|_|_|_|_|_|_|_| 6 |_|_|X|X|X|X|X|X| 6 
 |_|_|_|_|_|_|_|_| 1 5 |X|_|X|X|X|X|X|_| 1 5 
 |_|_|_|_|_|_|_|_| 6 |X|X|X|X|X|X|_|_| 6 
 |_|_|_|_|_|_|_|_| 1 |_|_|_|_|X|_|_|_| 1 
 |_|_|_|_|_|_|_|_| 2 |_|_|_|X|X|_|_|_| 2 
 1 3 1 7 5 3 4 3 1 3 1 7 5 3 4 3 
 2 1 5 1 2 1 5 1 
 
For the Exemplo above, the problem can be stated as the two lists [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]] and [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]] which give the "solid" lengths of the rows and columns, top-to-bottom and left-to-right, respectively. Published puzzles are larger than this Exemplo, e.g. 25 x 20, and apparently always have unique solutions.
P99 (***) Crossword puzzle
Given an empty (or almost empty) framework of a crossword puzzle and a set of words. The problem is to place the words into the framework.
The particular crossword puzzle is specified in a text file which first lists the words (one word per line) in an arbitrary order. Then, after an empty line, the crossword framework is defined. In this framework specification, an empty character location is represented by a dot (.). In order to make the solution easier, character locations can also contain predefined character values. The puzzle opposite is defined in the file p99a.dat, other Exemplos are p99b.dat and p99d.dat. There is also an Exemplo of a puzzle (p99c.dat) which does not have a solution. 
Words are strings (character lists) of at least two characters. A horizontal or vertical sequence of character places in the crossword puzzle framework is called a site. Our problem is to find a compatible way of placing words onto sites. 
Hints: (1) The problem is not easy. You will need some time to thoroughly understand it. So, don't give up too early! And remember that the objective is a clean solution, not just a quick-and-dirty hack!
(2) Reading the data file is a tricky problem for which a solution is provided in the file p99-readfile.pl. Use the predicate read_lines/2.
(3) For efficiency reasons it is important, at least for larger puzzles, to sort the words and the sites in a particular order. For this part of the problem, the solution of P28 may be very helpful.
Last modified: Sun Apr 26 10:55:38 W. Europe Daylight Time 2009