Lecture
There is a puzzle that was invented by A. Einstein. He argued that only 2% of people can solve this problem. It also says that 2% of people solve this problem at about the same time. I was intrigued, but did I enter into this 2%. I looked at the conditions, noticed the time, and ... 25 minutes was spent on solving the problem. I wonder how much the computer will think? Made a program on the PROLOGUE, launched ... tired of waiting. I could not even check whether it works correctly? After reading the site carefully, I realized that it would be very long for a simple search. And why did I decide much faster? I began to analyze the course of my thoughts when solving a puzzle. And then, in the likeness of his thoughts, he created an algorithm, and then the program itself on the PROLOGUE, which solves this problem. Creating a program took a whole day. But she gave the decision in 0.5 seconds!
Conditions of the problem.
1. There are 5 houses each in a different color.
2. In each house lives one person, different from the neighboring nationality: German, English, Swede, Dane, Norwegian.
3. Everyone drinks only one specific drink, smokes a certain brand of cigarettes and holds a certain animal.
4. None of the 5 people drinks the same as other drinks, does not smoke the same cigarettes and does not keep the same animal.
Question: Who owns the fish?
Tips:
1. The Englishman lives in the red house.
2. The Swede keeps the dog.
3. Dane drinking tea.
4. The green house stands to the left of the white.
5. A resident of the green house drinks coffee.
6. The person who smokes Pall Mall is holding a bird.
7. A resident from an average home drinks milk.
8. A yellow house dweller smokes Dunhill.
9. Norwegian lives in the first house.
10. The smoker Marlboro lives about the one who holds the cat.
11. The man who holds the horse lives near the one who smokes Dunhill.
12. Cigarette smoker Winfield drinks beer.
13. The Norwegian lives near the blue house.
14. German smokes Rothmans.
15. The Marlboro smoker lives next door to a person who drinks water.
Below is a program to solve the puzzle.
/ *
puzzle solution example
who has fish? (Who has a fish?)
Author: Ermolaev D.S. www.icreator.ru
There are five colorful houses in which different people live,
who drink different drinks
and who have different animals and who smoke different cigarettes.
need to answer the question with 15 tips
Who has fish?
Here is a quick way to find a solution.
* /
domains
Color = yellow; blue; red; green; white
House number = first; second; third; fourth; fifth
% reference - here indicates the ability to work with null values
Home Tag = reference tag (Color, House Number)
Nationality = Norwegian; Dane; Englishman; German; Swede
Drink = water; tea; milk; coffee; beer
Cigarettes = dunhill; marlboro; pall_mall; rothmans; winfield
Animal = cat; horse; bird; a fish; dog
House = reference house (Sign House, Nationality, Drink, Cigarettes, Animal)
Houses = reference House *
Value = q (Color); Nd (House number); nts (nationality);
np (Beverage); sg (cigarettes); ww (animal)
Values = Value *
predicates
nondeterm color (Color)
nondeterm nationality (Nationality)
nondeterm drink (Beverage)
nondeterm cigarettes (Cigarettes)
nondeterm animal (Animal)
nondeterm house (Number, Sign Home, Nationality, Drink, Cigarettes, Animal)
nondeterm house_name (SignHome, Nationality, Drink, Cigarettes, Animal)
nondeterm condition (Number, House, Homes)
conditions not broken (Room, House, House)
% without "left" - "right"
nondeterm houses (order, houses, house, house nearby)
% subject to "left" - "right"
nondeterm houses_fitted (Houses, House, House Nearby)
nondeterm near (House Number, House Number)
nondeterm adjoins (House number Left, House number Right)
house_non-unicorn1 (House, House)
House_Neuniquelen (House, Houses)
compare_values (House, Values, House, Values)
value_connected (Value)
clauses
% definition of possible values
% explicit definition helps during debugging
% catch errors in values
yellow color). blue color). color (red). Green colour). White colour).
nationality (Norwegian). nationality (Dane).
nationality (Englishman). nationality (German). nationality (Swede).
drink (water). drink (tea). drink (milk). drink (coffee). drink (beer).
cigarettes (dunhill). cigarettes (marlboro). cigarettes (pall_mall).
cigarettes (rothmans). cigarettes (winfield).
animal (cat). animal (horse). animal (bird).
animal (fish). animal (dog).
%
% basic task conditions
%
%one. An Englishman lives in a red house.
house (1, tag (red, _), English, _, _, _).
% 2. Swede contains a dog.
house (2, _, swede, _, _, dog).
% 3. Dane drinking tea.
house (3, _, Dane, tea, _, _).
%five. the tenant of the green house drinks coffee.
house (5, tag (green, _), _, coffee, _, _).
% 6. the one who smokes Pall Mall contains a bird.
house (6, _, _, _, pall_mall, bird).
% 7. who lives in the average (third) house drinks milk.
house (7, sign (_, third), _, milk, _, _).
%eight. he who lives in the yellow house smokes Dunhill.
house (8, tag (yellow, _), _, _, dunhill, _).
%9. in the first house lives a Norwegian.
house (9, tag (_, first), Norwegian, _, _, _).
% 12 Winfield cigarette smoker drinks beer.
house (12, _, _, beer, winfield, _).
% 14 German Rothmans smoke.
house (14, _, German, _, rothmans, _).
% this condition - that you can take any value - if it is not yet connected
dom_nabum (sign (Color, _), Nat, Nap, Sig, Alive): -
color (Color), nationality (Nat),
drink (nap), cigarettes (sig), animal (alive).
% condition-dependency, here the check is done immediately for both houses
%four. the green house is to the left of the white
Condition (4, HomeGreen, Homes): -
HomeGreen = Home (tag (green, _), _, _, _, _),
not (non_uniquelen (homegreen, houses)),
houses_fitted (Houses, HomeGreen, HouseWhite),
Home White = home (tag (white, _), _, _, _, _),
not (dom_ununikalen (HomeWhite, Homes)).
%ten. the Marlboro smoker lives next to the one who keeps the cat.
condition (10, House, Houses): - House = house (_, _, _, marlboro, _),
not (non_uniquelen home (House, Houses)),
home_s (Houses, Home, HomeRyad),
DomNadom = house (_, _, _, _, cat),
not (non_uniquelen (DomRyad, Home)).
%eleven. one who has a horse lives next to one who smokes Dunhill.
condition (11, House, Houses): - House = house (_, _, _, _, horse),
not (non_uniquelen home (House, Houses)),
home_s (Houses, Home, HomeRyad),
DomNear = house (_, _, _, dunhill, _),
not (non_uniquelen (DomRyad, Home)).
% 13 Norwegian lives near the blue house.
condition (13, House, Houses): - House = house (_, Norwegian, _, _, _),
not (non_uniquelen home (House, Houses)),
home_s (Houses, Home, HomeRyad),
DomNear = house (sign (blue, _), _, _, _, _),
not (non_uniquelen (DomRyad, Home)).
% 15 Smoker Marlboro lives next door to a person who drinks water.
condition (15, House, Houses): - House = house (_, _, _, marlboro, _),
not (non_uniquelen home (House, Houses)),
home_s (Houses, Home, HomeRyad),
DomNear = house (_, _, water, _, _),
not (non_uniquelen (DomRyad, Home)).
% condition for access to simple facts
condition (Nome, House, Homes): -
house (Nome, N, Nat, Nap, Sig, Alive),
Home = home (P, Nat, Nap, Sig, Alive),
not (dom_newunikalen (House, Houses)).
%
% now the conditions for validation
%
% condition-dependency, here the check is done immediately for both houses
% here is not exactly the condition
% so that all conditions are checked
% 4. the green house is to the left of the white
conditions not broken (4, Homegreen, Houses): -
HomeGreen = home (sign (Color, _), _, _, _, _),
(color),
Color = green,
Home White = home (tag (white, _), _, _, _, _),
not (houses_single (Houses, HomeGreen, HomeWhite)),
fail.
%ten. the Marlboro smoker lives next to the one who keeps the cat.
conditions are not violated (10, House, Houses): - House = house (_, _, _, Cig, _),
bound (sig)
Sig = marlboro,
DomNadom = house (_, _, _, _, cat),
not (home_unit (Home, House, HomeOrD)),
fail.
%eleven. the one who has the horse lives next to the one who smokes Dunhill.
conditions are not violated (11, House, Houses): - House = house (_, _, _, _, Alive),
bound (Alive)
Alive = horse
DomNear = house (_, _, _, dunhill, _),
not (home_unit (Home, House, HomeOrD)),
fail.
% 13 Norwegian lives near the blue house.
conditions are not violated (13, House, Houses): - House = house (_, Nat, _, _, _),
bound (nat)
Nat = Norwegian
DomNear = house (sign (blue, _), _, _, _, _),
not (home_unit (Home, House, HomeOrD)),
fail.
% 15 Smoker Marlboro lives next door to a person who drinks water.
conditions are not violated (15, House, Houses): - House = house (_, _, _, Sig, _),
bound (sig)
Sig = marlboro,
DomNear = house (_, _, water, _, _),
not (home_unit (Home, House, HomeOrD)),
fail.
% check for simple fact conditions
conditions are not violated (0, Home, _): -
% take the values of the checked house
House = house (sign (Color, Number), Nat, Nap, Whitefish, Alive),
% take the values of the conditional fact
home (_, sign (Color1, Number1), Nat1, Nap1, Cig1, Alive1),
% if values from one list are related and
% from another too - they should be equal
% Otherwise the condition is not met.
not (compare_values (
House,
[t (Color), nd (Number), nts (Nat), np (Nap), sg (Cig), Livestock (Alive)],
house (sign (Color1, Number1), Nat1, Nap1, Cig1, Alive1),
[ts (Tsvet1), nd (Number 1), nts (Nats1), np (Nap1), sg (Sig1), zhv (Alive1)])
),
fail.
% if it came here, then
% all conditions are met
conditions are not violated (0, _, _): - !.
value_connected (v (Value)): - bound (Value),!.
value_connected (LD (Eq)): - bound (Value),!.
value_connected (nc (zn)): - bound (zn),!.
value_connected (np (Value)): - bound (Value),!.
value_connected (cr (Value)): - bound (Value),!.
value_connected (eq (zn)): - bound (zn),!.
% verification of relationships in simple conditions-facts
compare_values (Home, [What | _], Home1, [What1 | _]): -
value_ is related (What),
value_connected (What1),
What = What1,
% if something matched, then everything else should match
!% so there is a prohibition of rollback
House = House1,
!
compare_values (House, [_ | Ost], House1, [_ | Ost1]): -
% take the next couple of values
compare_values (House, Ost, Dom1, Ost1),
!
check_values (_, [], _, []): -
% comparison successful
!
% do not compare with yourself
house_ is not unique1 (house (sign (_, Number1), _, _, _, _),
house (sign (_, Number2), _, _, _, _)): - Number1 = Number2,
fail.
% if both values are related and equal
house_ is not unique1 (house (sign (What, _), _, _, _, _), house (sign (What1, _), _, _, _, _)): -
bound (What), bound (What1), What = What1,
!
house_ is not unique1 (house (_, what, _, _, _), house (_, what1, _, _, _)): -
bound (What), bound (What1), What = What1,
!
house_ is not unique1 (house (_, _, what, _, _), house (_, _, what1, _, _)): -
bound (What), bound (What1), What = What1,
!
house_non-unicorn1 (house (_, _, _, what, _), house (_, _, _, what1, _)): -
bound (What), bound (What1), What = What1,
!
house_ is not unique1 (house (_, _, _, _, what), house (_, _, _, _, what1)): -
bound (What), bound (What1), What = What1,
!
%
% check on the condition of uniqueness: all values at home
% must be unique
%
dom_nunikalen (dom, [domDrugoy | _]): -
house_non-unicorn1 (House, HouseOther),
!
dom_newunikalen (dom, [_ | dom]): -
dom_nunikalen (House, Houses),
!
% definition of general rules for the location of houses
Near (Place, Near): - adjacent (Place, Near).
Near (Place, Near): - adjacent (Near, Place).
adjacent (first, second).
adjacent (second, third).
adjacent (third, fourth).
adjacent (fourth, fifth).
% definition of the house next to the data without left-right
home_circuit ([HomeBank | _], home (sign (_, Place), _, _, _, _), HomeBank): -
DomNear = house (sign (_, Near), _, _, _, _)
near (Place, Near).
home_number ([_ | Houses], Home, HomeOrD): -
home_s (Houses, Home, HomeRyad),
!
% definition of the house next to the data given the left-right
houses_single ([HomeDeath | _], home (sign (_, Place), _, _, _, _), HomeDeck): -
DomNear = house (sign (_, Near), _, _, _, _)
adjacent (Location, Nearby).
houses_single ([_ | Houses], House, DomBank): -
houses_fitted (Houses, House, HouseBefore),
!
predicates
all_connected1 (House)
all_connected (Houses)
not_connected1 (House)
nondeterm is not related (Home, House)
clauses
all_connected1 (house (P, H, Nap, Sig, G)): - bound (P), bound (N), bound (Nap),
bound (sig), bound (Ж),!.
% Is everything solved?
all_connected ([Home | Houses]): -
!
all_connected1 (House),
all_connected (Houses)
!
all_connected ([]): - !.
un_connected1 (house (sign (What, _), _, _, _, _)): - free (What),!.
un_connected1 (house (_, What, _, _, _)): - free (What),!.
un_connected1 (house (_, _, what, _, _)): - free (what),!.
un_connected1 (house (_, _, _, What, _)): - free (What),!.
un_connected1 (house (_, _, _, _, what)): - free (what),!.
% find a house that has unrelated values
Unbound ([Home | _], Home): -
not_connected1 (House).
Unrelated ([_ | Houses], Home): -
Unrelated (Houses, House).
predicates
nondeterm select_explicit_number (Number)
nondeterm solve2 (House, Homes, Room)
all_conditions_used (rooms, houses)
nondeterm remember_selection (House, House)
condition_handled (Number, Numbers)
nondeterm solve1 (Houses, Rooms)
nondeterm finish out (Home)
solve (at home)
clauses
% choose such conditions and connections - which are clearly
% follow current data and conditions
% it speeds up the decision
select_explicit_number (Nom): -
condition (Nome, Home, []),
Home = home (tag (_, Number), _, _, _, _),
% If a number linking occurred, then it is explicit!
bound (Number).
% if some condition worked,
% you need to remember its result in the general list
remember_select (Home, [Home | _]).
remember_select (Home, [_ | Home]): -
remember_selection (House, Houses).
% checks if such a condition has already been processed
condition_handled (Nome, [Nom | _]): - !.
condition_handled (Nome, [_ | Processed]): -
condition_handled (Nome, Processed),
!
% choice of conditions
solve2 (House, AllHouses, Nome): -
% to speed up the decision - the choice of the best conditions.
% using this predicate execution is less than 0.5 seconds,
% without this predicate - runtime on ORDERS is more!
select_explicit_connection (Nom),
condition (Nome, Home, All Homes).
solve2 (House, AllHouses, Nome): -
% enumeration of all conditions
condition (Nome, Home, All Homes).
% check - are all conditions used
all_conditions_used (Processed, Home): -
condition (Number, _, Home),
not (condition_handled (Number, Processed))
fail.
all_conditions_used (_, _): -!.
% applies all the conditions of the problem and returns the received
% result for further binding
Solve1 (All Homes, Processed): -
% if all rules are used, then exit and give the result
% for further selection at random
all_conditions_used (Processed, AllHouses),
!
Solve1 (All Homes, Processed): -
% use the condition of the problem
decide2 (House, AllHouses, Nome),
% this condition has not yet been processed
not (condition_handled (Nom, Processed)),
% remember the result of the condition
% here if there is a rollback below, then the assignment
% can be done for other homes
remember_select (House, AllHouses),
% if the house is unique
not (non_uniquelen home (House, AllHouses)),
% and not others violated the conditions of the problem
conditions are not violated (_, House, All Houses),
% then move on
Solve1 (All Homes, [Nom | Processed]).
The% remaining unbound values will bind based on
% condition that values should not be repeated
% that is, you can take any possible value
% and insert it if the conditions of the problem are not violated
finish out (All House): -
% take a house that has unrelated value
not_connected (AllHouses, House),
House = house (P, N, Nap, Sig, Alive),
% choose this value randomly
dom_nabum (P, N, Nap, Sig, Alive),
% check the condition of uniqueness
not (non_uniquelen home (House, AllHouses)),
% and at the same time all the conditions of the problem are true
conditions are not violated (_, House, All Houses),
% search for another unrelated value
finish out (All House).
finish (House): -
% if everything is already decided (connected), then the output
all_connected (Houses)
!
solve (Home): -
Houses = [house (sign (_, first), _, _, _, _),
house (sign (_, second), _, _, _, _),
house (sign (_, third), _, _, _, _),
house (sign (_, fourth), _, _, _, _),
house (sign (_, fifth), _, _, _, _)],
% processing conditions
% here all conditions must be met (applied)
solve1 (Houses, []),
% remaining unbound values needed
% tie at random with a condition check
to finish (House),
!
Goal: -
marktime (0, T1),
solve (at home)
marktime (0, T2),
difftime (T2, T1, Toast),
nl, write (Home, ":", Toast).
Perhaps the program will seem pretty tricked out to you, but it is precisely such actions a person performs when solving this puzzle.
Comments
To leave a comment
Presentation and use of knowledge
Terms: Presentation and use of knowledge