Todos os domingos em nossa empresa, é costume organizar testes divertidos, este é um deles.

Riddle

Para encontrar o assassino do Sr. Boddy, você precisa descobrir onde cada pessoa estava e quais armas estavam na sala. As dicas estão espalhadas pelo questionário (você não pode responder à primeira pergunta até ler todos os dez).

• Primeiro, imagine os suspeitos. Existem três homens (George, John, Robert) e três mulheres (Barbara, Christina, Yolanda). Cada pessoa está em uma sala separada (banheiro, sala de jantar, cozinha, sala de estar, despensa, escritório). Armas suspeitas foram encontradas em cada quarto (bolsa, arma de fogo, gás, faca, veneno, corda). Pergunta: quem foi encontrado na cozinha?
• Dica 1. Com um homem na cozinha, não há corda, faca ou sacola. A arma não é uma arma de fogo. Pergunta: Quais armas foram encontradas na cozinha?

• Dica 2. Barbara está no escritório ou no banheiro, e Yolanda está em outro dos dois quartos nomeados. Em que quarto Barbara encontrou?
• Dica 3. O homem com a bolsa não é Barbara nem George, e ele não estava no banheiro nem na sala de jantar. Quem tinha a bolsa?
• Dica 4. Uma mulher com uma corda foi encontrada no escritório. Quem é esse?
• Dica 5. A arma na sala pertence a John ou George. Que tipo de arma na sala de estar?
• Dica 6. Não havia faca na sala de jantar. Onde estava a faca?
• Dica 7. Yolanda não estava no escritório nem na despensa com as armas apropriadas para essas salas. Que tipo de arma Yolanda tem?
• Dica 8. George encontrou uma arma de fogo. Qual quarto?
• Foi descoberto que o Sr. Boddy foi gaseado na despensa. O suspeito naquela sala era um assassino. Quem é esse?

Eu gosto de tais quebra-cabeças (na verdade, de quase todos os quebra-cabeças). Eles podem levar horas e horas de reflexão, mas Prolog sempre vem em socorro! Vamos ver como isso ajuda a resolver esses problemas de raciocínio.

Prolog 101

Instale o SWI-Prolog

~> swipl Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.6) Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- write('Hello, World!'). Hello, World! true. ?- write('Hello,'), nl, write('world'). Hello, world true. ?- X is 3*4 + 2. X = 14. 

• swipl - intérprete de Prolog
• write é chamado de functor, e a representação write/1 significa que é necessário 1 argumento (o mesmo conceito em Erlang e Elixir para adicionar o número de argumentos ao nome de uma função)
• nl usado para imprimir uma nova linha
• a sequência de comandos é separada por vírgulas, que também substituem o operador AND
• operador de atribuição is seguido por uma expressão matemática
• variáveis ​​são escritas em maiúsculas X , não x

Base de conhecimento

A essência do Prolog é declarar fatos, compilar fatos e solicitá-los.

Criando o arquivo hello.pl :

 friend(john, julia). friend(john, jack). friend(julia, sam). friend(julia, molly). loves(john, julia). loves(julia, sam). loves(sam, julia). male(brad). male(john). male(jim). male(alfred). female(marry). child(brad, alfred). child(john, jim). child(john, marry). 

• usamos [hello]. para carregar [hello]. : preste atenção ao ponto no final
• listing lista todos os fatos na base de conhecimento

 ?- [hello]. % hello compiled 0.00 sec, 3 clauses true. ?- listing(friend). friend(john, julia). friend(john, jack). friend(julia, sam). friend(julia, molly). true. ?- listing(loves). loves(john, julia). loves(julia, sam). loves(sam, julia). true. 

Solicitação de fatos

Depois de declarar os fatos na base de conhecimento, podemos ir além e fazer perguntas sobre a verdade dos fatos, bem como quais conclusões podem ser tiradas deles.

 ?- friend(john, julia). true . ?- friend(john, jack). true. ?- loves(john, julia). true. ?- loves(john, sam). false. 

Podemos fazer perguntas mais complexas. Por exemplo, quem é amigo de John ou quem ama Julia.

 ?- friend(john, Who). Who = julia ; Who = jack. 

 ?- listing(child). child(brad, alfred). child(john, jim). child(john, mary). true. ?- child(john, X). X = jim ; X = mary. 

John está na zona de amizade?

Estabelecemos a amizade de John com Julia ( friend(john, julia) ), mas para Prolog isso não significa que Julia seja amiga de John: você precisa adicionar outro fato friend(julia, john) . Também indicamos quem tem filhos e, obviamente, não deseja duplicar o código, indicando separadamente os pais de cada filho. Não queremos escrever algo como

 child(brad, alfred). child(john, jim). child(john, mary). parent(alfred, brad). parent(jim, john). parent(mary, john). 

O Prolog ajuda a evitar duplicação com regras de conclusão lógica:

 rule :- stmt1, stmt2,... 

A regra é verdadeira se todas as instruções internas forem verdadeiras (listadas e dobradas logicamente com uma vírgula).

 friend(X, Y) :- friend(Y,X). parent(X, Y) :- child(Y,X). father(X, Y) :- child(Y,X), male(X). mother(X, Y) :- child(Y,X), female(X). friendzoned(X) :- loves(X, Y), \+ loves(Y,X). 

• friend(X,Y) verdadeiro para friend(Y,X )
• parent(X,Y) verdadeiro quando child(Y,X)
• father(X,Y) verdadeiro com o conjunto parent(X,Y) e male(X)
• mother(X,Y) verdadeira quando parent(X,Y) e female(X)
• friendzoned(X) verdadeiro se X ama SOMEONE Y e Y não ama X (observe a variável oculta Y?)

 ?- friend(julia, john). true . ?- male(jim). true. ?- parent(jim,X). X = john. ?- father(jim, X). X = john. ?- mother(X, john). X = marry. ?- mother(marry,X). X = john. ?- mother(marry, john). true. ?- loves(julia, X). X = sam. ?- friendzoned(julia). false. ?- friendzoned(john). true. 

Ok, agora temos todo o conhecimento necessário. Vamos praticar a coloração do mapa.

Coloração de cartão

Vamos começar com o conhecido problema matemático. É necessário que nenhuma área adjacente tenha a mesma cor.



Portanto, o raciocínio deve ser tal, temos três coisas:

1. Variáveis ​​são as áreas que queremos colorir: A, B, C, D, E.
2. Domínio - um intervalo de valores que podem ser atribuídos a variáveis: vermelho, azul, verde.
3. A limitação é que as áreas adjacentes não podem ter a mesma cor.

Domínio

Defina o domínio de nossas regiões (vermelho, verde, azul).

 color(red). color(green). color(blue). 

Isso é tudo.

Pedimos uma solução

 colorify(A,B,C,D,E) :- color(A), color(B), color(C), color(D), color(E), \+ A=B, \+ A=C, \+ A=D, \+ A=E, \+ B=C, \+ C=D, \+ D=E. 

Aqui, definimos a solução como uma regra colorify com cinco variáveis ​​A, B, C, D, E, e dentro da regra atribuímos a cor do domínio (vermelho, azul, verde) para as variáveis ​​e definimos as restrições de que A não é igual a B, não é igual a C ... e etc.

\+ X=Y significa que X não é igual a Y

O Prolog continuará gerando valores até encontrar uma opção que satisfaça a regra com restrições.

 ?- [mapcoloring] | . true. ?- colorify(A,B,C,D,E) | . A = red, B = D, D = green, C = E, E = blue ; A = red, B = D, D = blue, C = E, E = green ; A = green, B = D, D = red, C = E, E = blue ; A = green, B = D, D = blue, C = E, E = red ; A = blue, B = D, D = red, C = E, E = green ; A = blue, B = D, D = green, C = E, E = red 

 color(red). color(green). color(blue). colorify(A,B,C,D,E) :- color(A), color(B), color(C), color(D), color(E), \+ A=B, \+ A=C, \+ A=D, \+ A=E, \+ B=C, \+ C=D, \+ D=E. 

... mas não estamos colorindo as imagens aqui, mas procurando o assassino.

A matança

Primeiro, imagine os suspeitos. Existem três homens (George, John, Robert) e três mulheres (Barbara, Christina, Yolanda). Cada pessoa está em uma sala separada (banheiro, sala de jantar, cozinha, sala de estar, despensa, escritório). Armas suspeitas foram encontradas em cada quarto (bolsa, arma de fogo, gás, faca, veneno, corda).

Quem foi encontrado na cozinha?

Domínio

A partir disso, podemos concluir que temos cinco domínios: man , woman , person ou suspeito, location e weapons , e nossas variáveis ​​(A, B, C, D, E, F) devem representar a pessoa, o local e a arma com algumas limitações que serão reveladas nas próximas dicas.

 man(george). man(john). man(robert). woman(barbara). woman(christine). woman(yolanda). person(X):- man(X). person(X):- woman(X). location(bathroom). location(dining). location(kitchen). location(livingroom). location(pantry). location(study). weapon(bag). weapon(firearm). weapon(gas). weapon(knife). weapon(poison). weapon(rope). 

A regra uniq_ppl gera valores exclusivos para nossas variáveis.

 uniq_ppl(A,B,C,D,E,F):- person(A), person(B), person(C), person(D), person(E), person(F), \+A=B, \+A=C, \+A=D, \+A=E, \+A=F, \+B=C, \+B=D, \+B=E, \+B=F, \+C=D, \+C=E, \+C=F, \+D=E, \+D=F, \+E=F. 

Solução

Começamos definindo a regra de um assassino com pessoas únicas em lugares e pessoas únicas com armas, e agora indicará a relação entre pessoas em lugares com aqueles que possuem armas.

Observe que ainda temos seis suspeitos.

Entrada

 murderer(X) :- uniq_ppl(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study), uniq_ppl(Bag, Firearm, Gas, Knife, Poison, Rope), 

Para falar facilmente sobre variáveis, como banheiro, sala de jantar, armas de fogo, gás, determinamos imediatamente:

• Banheiro - é o mesmo suspeito (masculino ou feminino) no banheiro
• Armas de fogo - é o mesmo suspeito (masculino ou feminino) com uma arma de fogo
• e assim por diante ... você pode imaginar isso como uma grade

Agora continuamos a adicionar restrições após a última vírgula na regra do murderer .

Dica 1

Com um homem na cozinha, não há corda, faca ou bolsa. A arma não é uma arma de fogo. Quais armas são encontradas na cozinha?

 % 2. Clue 1: The man in the kitchen was not found with the rope, knife, or bag. % Which weapon, then, which was not the firearm, was found in the kitchen? man(Kitchen), \+Kitchen=Rope, \+Kitchen=Knife, \+Kitchen=Bag, \+Kitchen=Firearm, 

Aqui dizemos que a variável Kitchen satisfaz o fato do man (definido em nosso domínio) e declaramos que, independentemente de quem seja a pessoa na cozinha, ele não possui nenhum dos seguintes Rope : Rope , Knife , Bag , Firearm .

Dica 2

Dica 2. Barbara está no escritório ou no banheiro, e Yolanda está em outro dos dois quartos nomeados. Em que quarto Barbara encontrou?

Assim, podemos dizer que há uma woman no escritório e no banheiro. E essa não é Christina, e também cruzamos as outras opções para Barbara e Yolanda (cozinha, sala de jantar, sala de estar, despensa).

 % % 3. Clue 2: Barbara was either in the study or the bathroom; Yolanda was in the other. % % Which room was Barbara found in? woman(Bathroom), woman(Study), \+christine=Bathroom, \+christine=Study, \+barbara=Dining, \+barbara=Kitchen, \+barbara=Livingroom, \+barbara=Pantry, 

Dica 3

O homem com a sacola não é Barbara nem George, e ele não estava no banheiro nem na sala de jantar. Quem tinha a bolsa?

 % % 4. Clue 3: The person with the bag, who was not Barbara nor George, was not in the bathroom nor the dining room. % % Who had the bag in the room with them? \+barbara=Bag, \+george=Bag, \+Bag=Bathroom, \+Bag=Dining, 

Dica 4

Uma mulher com uma corda foi encontrada no escritório. Quem é esse?

 % % 5. Clue 4: The woman with the rope was found in the study. % % Who had the rope? woman(Rope), Rope=Study, 

Dica 5

Dica 5. A arma na sala pertence a John ou George. Que tipo de arma na sala de estar?

 man in Livingroom Livingroom isn't robert % % 6. Clue 5: The weapon in the living room was found with either John or George. % % What weapon was in the living room? man(Livingroom), \+Livingroom=robert, 

Dica 6

Não havia faca na sala de jantar. Onde estava a faca?

 % % 7. Clue 6: The knife was not in the dining room. % % So where was the knife? \+Knife=Dining, 

Dica 7

Dica 7. Yolanda não estava no escritório nem na despensa. Qual arma está no quarto de Yolanda?

 % % 8. Clue 7: Yolanda was not with the weapon found in the study nor the pantry. % % What weapon was found with Yolanda? \+yolanda=Pantry, \+yolanda=Study, 

Dica 8

George encontrou uma arma de fogo.

 % % 9. Clue 8: The firearm was in the room with George. % % In which room was the firearm found? Firearm=george, 

Dica 9

Foi descoberto que o Sr. Boddy foi gaseado na despensa. O suspeito naquela sala era um assassino. Quem é esse?

 % % 10. It was discovered that Mr. Boddy was gassed in the pantry. The suspect found in that room was the murderer. % % Who, then, do you point the finger towards? Pantry=Gas, Pantry=X, write("KILLER IS :"), write(X), nl, writeanswers(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study, Bag, Firearm, Gas, Knife, Poison, Rope). 

Combine o gás, a despensa e o assassino, depois use write para write writeanswers .

 writeanswers(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study, Bag, Firearm, Gas, Knife, Poison, Rope):- write("Bathroom: "), write(Bathroom), nl, write("Dining: "), write(Dining), nl, write("Livingroom: "), write(Livingroom), nl, write("Pantry: "), write(Pantry), nl, write("Study: "), write(Study), nl, write("Kitchen: "), write(Kitchen), nl, write("Knife: "), write(Knife), nl, write("Gas: "), write(Gas), nl, write("Rope: "), write(Rope), nl, write("Bag: "), write(Bag), nl, write("Poison: "), write(Poison), nl, write("Firearm: "), write(Firearm), nl. 

Quem é o assassino?

  ?- [crime2]. true. ?- murderer(X). KILLER IS :christine Bathroom: yolanda Dining: george Livingroom: john Pantry: christine Study: barbara Kitchen: robert Knife: yolanda Gas: christine Rope: barbara Bag: john Poison: robert Firearm: george X = christine ; 

O código está publicado aqui . Provavelmente poderia ter sido muito melhor, já que eu não sou especialista em Prolog :)