Решение вопроса “Кому принадлежит Zebra” программным путем?
-
11-07-2019 - |
Вопрос
Редактировать:эта головоломка также известна как "Загадка Эйнштейна".
В Кому принадлежит "Зебра" (вы можете попробуйте онлайн-версию здесь) является примером классического набора головоломок, и я готов поспорить, что большинство пользователей Stack Overflow могут решить его с помощью ручки и бумаги.Но как бы выглядело программное решение?
Основываясь на подсказках, перечисленных ниже...
- Там пять домов.
- Каждый дом имеет свой собственный неповторимый цвет.
- Все владельцы дома - разных национальностей.
- У всех них есть разные домашние животные.
- Все они пьют разные напитки.
- Все они курят разные сигареты.
- Англичанин живет в красном доме.
- У шведа есть собака.
- Датчанин пьет чай.
- Зеленый дом находится с левой стороны от белого дома.
- Они пьют кофе в зеленом доме.
- У человека, который курит "Пэлл Мэлл", есть птицы.
- В желтом доме курят "Данхилл".
- В среднем доме они пьют молоко.
- Норвежец живет в первом доме.
- Мужчина, который курит Смесь, живет в доме рядом с домом с кошками.
- В доме рядом с домом, где у них есть лошадь, они курят "Данхилл".
- Человек, который курит Blue Master, пьет пиво.
- Немец курит "Принц".
- Норвежец живет рядом с голубым домом.
- Они пьют воду в доме рядом с домом, где курят смесь.
... кому принадлежит "Зебра"?
Решение
Вот решение на Python, основанное на программировании ограничений:
from constraint import AllDifferentConstraint, InSetConstraint, Problem
# variables
colors = "blue red green white yellow".split()
nationalities = "Norwegian German Dane Swede English".split()
pets = "birds dog cats horse zebra".split()
drinks = "tea coffee milk beer water".split()
cigarettes = "Blend, Prince, Blue Master, Dunhill, Pall Mall".split(", ")
# There are five houses.
minn, maxn = 1, 5
problem = Problem()
# value of a variable is the number of a house with corresponding property
variables = colors + nationalities + pets + drinks + cigarettes
problem.addVariables(variables, range(minn, maxn+1))
# Each house has its own unique color.
# All house owners are of different nationalities.
# They all have different pets.
# They all drink different drinks.
# They all smoke different cigarettes.
for vars_ in (colors, nationalities, pets, drinks, cigarettes):
problem.addConstraint(AllDifferentConstraint(), vars_)
# In the middle house they drink milk.
#NOTE: interpret "middle" in a numerical sense (not geometrical)
problem.addConstraint(InSetConstraint([(minn + maxn) // 2]), ["milk"])
# The Norwegian lives in the first house.
#NOTE: interpret "the first" as a house number
problem.addConstraint(InSetConstraint([minn]), ["Norwegian"])
# The green house is on the left side of the white house.
#XXX: what is "the left side"? (linear, circular, two sides, 2D house arrangment)
#NOTE: interpret it as 'green house number' + 1 == 'white house number'
problem.addConstraint(lambda a,b: a+1 == b, ["green", "white"])
def add_constraints(constraint, statements, variables=variables, problem=problem):
for stmt in (line for line in statements if line.strip()):
problem.addConstraint(constraint, [v for v in variables if v in stmt])
and_statements = """
They drink coffee in the green house.
The man who smokes Pall Mall has birds.
The English man lives in the red house.
The Dane drinks tea.
In the yellow house they smoke Dunhill.
The man who smokes Blue Master drinks beer.
The German smokes Prince.
The Swede has a dog.
""".split("\n")
add_constraints(lambda a,b: a == b, and_statements)
nextto_statements = """
The man who smokes Blend lives in the house next to the house with cats.
In the house next to the house where they have a horse, they smoke Dunhill.
The Norwegian lives next to the blue house.
They drink water in the house next to the house where they smoke Blend.
""".split("\n")
#XXX: what is "next to"? (linear, circular, two sides, 2D house arrangment)
add_constraints(lambda a,b: abs(a - b) == 1, nextto_statements)
def solve(variables=variables, problem=problem):
from itertools import groupby
from operator import itemgetter
# find & print solutions
for solution in problem.getSolutionIter():
for key, group in groupby(sorted(solution.iteritems(), key=itemgetter(1)), key=itemgetter(1)):
print key,
for v in sorted(dict(group).keys(), key=variables.index):
print v.ljust(9),
print
if __name__ == '__main__':
solve()
Выходной сигнал:
1 yellow Norwegian cats water Dunhill
2 blue Dane horse tea Blend
3 red English birds milk Pall Mall
4 green German zebra coffee Prince
5 white Swede dog beer Blue Master
Поиск решения занимает 0,6 секунды (процессор 1,5 ГГц).
Ответ таков: "Зебра принадлежит немцу".
Для установки constraint
модуль через pip
:pip устанавливает python-ограничение
Для установки вручную:
Скачать:
$ wget $ wget https://pypi.python.org/packages/source/p/python-constraint/python-constraint-1.2.tar.bz2#md5=d58de49c85992493db53fcb59b9a0a45
извлечь (Linux / Mac / BSD):
$ bzip2 -cd python-ограничение-1.2.tar.bz2 | tar xvf -
извлечь (Windows, с 7зип):
> 7z e python-ограничение-1.2.tar.bz2
> 7z e python-ограничение-1.2.tarустановить:
$ cd python-ограничение-1.2
$ python setup.py установить
Другие советы
В Prolog мы можем создать экземпляр домена, просто выбрав элементы От это :) (создание взаимоисключающий выбор, для повышения эффективности).Использование SWI-Prolog,
select([A|As],S):- select(A,S,S1),select(As,S1).
select([],_).
left_of(A,B,C):- append(_,[A,B|_],C).
next_to(A,B,C):- left_of(A,B,C) ; left_of(B,A,C).
zebra(Owns, HS):- % house: color,nation,pet,drink,smokes
HS = [ h(_,norwegian,_,_,_), h(blue,_,_,_,_), h(_,_,_,milk,_), _, _],
select([ h(red,brit,_,_,_), h(_,swede,dog,_,_),
h(_,dane,_,tea,_), h(_,german,_,_,prince)], HS),
select([ h(_,_,birds,_,pallmall), h(yellow,_,_,_,dunhill),
h(_,_,_,beer,bluemaster)], HS),
left_of( h(green,_,_,coffee,_), h(white,_,_,_,_), HS),
next_to( h(_,_,_,_,dunhill), h(_,_,horse,_,_), HS),
next_to( h(_,_,_,_,blend), h(_,_,cats, _,_), HS),
next_to( h(_,_,_,_,blend), h(_,_,_,water,_), HS),
member( h(_,Owns,zebra,_,_), HS).
Запускается довольно мгновенно:
?- time( (zebra(Who,HS), writeln(Who), nl, maplist(writeln,HS), nl, false
; writeln('no more solutions!') )).
german
h( yellow, norwegian, cats, water, dunhill )
h( blue, dane, horse, tea, blend )
h( red, brit, birds, milk, pallmall )
h( green, german, zebra, coffee, prince ) % formatted by hand
h( white, swede, dog, beer, bluemaster)
no more solutions!
% 1,706 inferences, 0.000 CPU in 0.070 seconds (0% CPU, Infinite Lips)
true.
В одном плакате уже упоминалось, что Prolog является потенциальным решением.Это правда, и это решение, которое я бы использовал.В более общих чертах, это идеальная задача для автоматизированной системы вывода.Prolog - это логический язык программирования (и связанный с ним интерпретатор), который формирует такую систему.Это в основном позволяет делать выводы о фактах из заявлений, сделанных с использованием Логика первого порядка.FOL - это, по сути, более продвинутая форма логики высказываний.Если вы решите, что не хотите использовать Prolog, вы могли бы использовать аналогичную систему собственного создания, используя такую технику, как способ поненса для выполнения сделайте выводы.
Вам, конечно, нужно будет добавить некоторые правила о зебрах, поскольку об этом нигде не упоминается...Я полагаю, цель состоит в том, чтобы вы могли вычислить остальных 4 домашних животных и, таким образом, сделать вывод, что последнее из них - зебра?Вы захотите добавить правила, в которых говорится, что зебра является одним из домашних животных, и в каждом доме может быть только одно домашнее животное.Внедрение такого рода знаний "здравого смысла" в систему вывода является основным препятствием для использования этой техники в качестве настоящего искусственного интеллекта.Есть несколько исследовательских проектов, таких как Cyc, которые пытаются передать такие общеизвестные знания с помощью грубой силы.Они добились интересного успеха.
Совместимость с SWI-Prolog:
% NOTE - This may or may not be more efficent. A bit verbose, though.
left_side(L, R, [L, R, _, _, _]).
left_side(L, R, [_, L, R, _, _]).
left_side(L, R, [_, _, L, R, _]).
left_side(L, R, [_, _, _, L, R]).
next_to(X, Y, Street) :- left_side(X, Y, Street).
next_to(X, Y, Street) :- left_side(Y, X, Street).
m(X, Y) :- member(X, Y).
get_zebra(Street, Who) :-
Street = [[C1, N1, P1, D1, S1],
[C2, N2, P2, D2, S2],
[C3, N3, P3, D3, S3],
[C4, N4, P4, D4, S4],
[C5, N5, P5, D5, S5]],
m([red, english, _, _, _], Street),
m([_, swede, dog, _, _], Street),
m([_, dane, _, tea, _], Street),
left_side([green, _, _, _, _], [white, _, _, _, _], Street),
m([green, _, _, coffee, _], Street),
m([_, _, birds, _, pallmall], Street),
m([yellow, _, _, _, dunhill], Street),
D3 = milk,
N1 = norwegian,
next_to([_, _, _, _, blend], [_, _, cats, _, _], Street),
next_to([_, _, horse, _, _], [_, _, _, _, dunhill], Street),
m([_, _, _, beer, bluemaster], Street),
m([_, german, _, _, prince], Street),
next_to([_, norwegian, _, _, _], [blue, _, _, _, _], Street),
next_to([_, _, _, water, _], [_, _, _, _, blend], Street),
m([_, Who, zebra, _, _], Street).
У переводчика:
?- get_zebra(Street, Who).
Street = ...
Who = german
Вот как бы я поступил на это.Сначала я бы сгенерировал все упорядоченные n-кортежи
(housenumber, color, nationality, pet, drink, smoke)
5 ^ 6 из них, 15625, легко управляемы.Затем я бы отфильтровал простые логические условия.их десять, и от каждого из них вы ожидаете отфильтровать 8/25 условий (1/25 условий содержат шведа с собакой, 16/25 содержат не-шведа с не-собакой).Конечно, они не являются независимыми, но после фильтрации их должно остаться не так уж много.
После этого у вас получится хорошая графическая задача.Создайте график, в котором каждый узел представляет один из оставшихся n-кортежей.Добавьте ребра к графику, если два конца содержат дубликаты в некоторой позиции из n кортежей или нарушают какие-либо "позиционные" ограничения (их всего пять).Оттуда вы почти дома, найдите на графике независимый набор из пяти узлов (ни один из узлов не соединен ребрами).Если их не слишком много, вы могли бы, возможно, просто исчерпывающе сгенерировать все 5 кортежей из n-кортежей и просто отфильтровать их снова.
Это могло бы стать хорошим кандидатом для code golf.Кто-то, вероятно, может решить это в одной строке с помощью чего-то вроде haskell :)
запоздалая мысль: Начальный проход фильтра также может исключить информацию из позиционных ограничений.Не так много (1/25), но все же значительно.
Другое решение на Python, на этот раз с использованием PyKE от Python (движок знаний Python).Конечно, это более подробно, чем использование модуля Python "constraint" в решении @J.F.Sebastian, но это обеспечивает интересное сравнение для любого, кто ищет необработанный механизм знаний для решения проблем такого типа.
подсказки.kfb
categories( POSITION, 1, 2, 3, 4, 5 ) # There are five houses.
categories( HOUSE_COLOR, blue, red, green, white, yellow ) # Each house has its own unique color.
categories( NATIONALITY, Norwegian, German, Dane, Swede, English ) # All house owners are of different nationalities.
categories( PET, birds, dog, cats, horse, zebra ) # They all have different pets.
categories( DRINK, tea, coffee, milk, beer, water ) # They all drink different drinks.
categories( SMOKE, Blend, Prince, 'Blue Master', Dunhill, 'Pall Mall' ) # They all smoke different cigarettes.
related( NATIONALITY, English, HOUSE_COLOR, red ) # The English man lives in the red house.
related( NATIONALITY, Swede, PET, dog ) # The Swede has a dog.
related( NATIONALITY, Dane, DRINK, tea ) # The Dane drinks tea.
left_of( HOUSE_COLOR, green, HOUSE_COLOR, white ) # The green house is on the left side of the white house.
related( DRINK, coffee, HOUSE_COLOR, green ) # They drink coffee in the green house.
related( SMOKE, 'Pall Mall', PET, birds ) # The man who smokes Pall Mall has birds.
related( SMOKE, Dunhill, HOUSE_COLOR, yellow ) # In the yellow house they smoke Dunhill.
related( POSITION, 3, DRINK, milk ) # In the middle house they drink milk.
related( NATIONALITY, Norwegian, POSITION, 1 ) # The Norwegian lives in the first house.
next_to( SMOKE, Blend, PET, cats ) # The man who smokes Blend lives in the house next to the house with cats.
next_to( SMOKE, Dunhill, PET, horse ) # In the house next to the house where they have a horse, they smoke Dunhill.
related( SMOKE, 'Blue Master', DRINK, beer ) # The man who smokes Blue Master drinks beer.
related( NATIONALITY, German, SMOKE, Prince ) # The German smokes Prince.
next_to( NATIONALITY, Norwegian, HOUSE_COLOR, blue ) # The Norwegian lives next to the blue house.
next_to( DRINK, water, SMOKE, Blend ) # They drink water in the house next to the house where they smoke Blend.
отношения.крб
#############
# Categories
# Foreach set of categories, assert each type
categories
foreach
clues.categories($category, $thing1, $thing2, $thing3, $thing4, $thing5)
assert
clues.is_category($category, $thing1)
clues.is_category($category, $thing2)
clues.is_category($category, $thing3)
clues.is_category($category, $thing4)
clues.is_category($category, $thing5)
#########################
# Inverse Relationships
# Foreach A=1, assert 1=A
inverse_relationship_positive
foreach
clues.related($category1, $thing1, $category2, $thing2)
assert
clues.related($category2, $thing2, $category1, $thing1)
# Foreach A!1, assert 1!A
inverse_relationship_negative
foreach
clues.not_related($category1, $thing1, $category2, $thing2)
assert
clues.not_related($category2, $thing2, $category1, $thing1)
# Foreach "A beside B", assert "B beside A"
inverse_relationship_beside
foreach
clues.next_to($category1, $thing1, $category2, $thing2)
assert
clues.next_to($category2, $thing2, $category1, $thing1)
###########################
# Transitive Relationships
# Foreach A=1 and 1=a, assert A=a
transitive_positive
foreach
clues.related($category1, $thing1, $category2, $thing2)
clues.related($category2, $thing2, $category3, $thing3)
check unique($thing1, $thing2, $thing3) \
and unique($category1, $category2, $category3)
assert
clues.related($category1, $thing1, $category3, $thing3)
# Foreach A=1 and 1!a, assert A!a
transitive_negative
foreach
clues.related($category1, $thing1, $category2, $thing2)
clues.not_related($category2, $thing2, $category3, $thing3)
check unique($thing1, $thing2, $thing3) \
and unique($category1, $category2, $category3)
assert
clues.not_related($category1, $thing1, $category3, $thing3)
##########################
# Exclusive Relationships
# Foreach A=1, assert A!2 and A!3 and A!4 and A!5
if_one_related_then_others_unrelated
foreach
clues.related($category, $thing, $category_other, $thing_other)
check unique($category, $category_other)
clues.is_category($category_other, $thing_not_other)
check unique($thing, $thing_other, $thing_not_other)
assert
clues.not_related($category, $thing, $category_other, $thing_not_other)
# Foreach A!1 and A!2 and A!3 and A!4, assert A=5
if_four_unrelated_then_other_is_related
foreach
clues.not_related($category, $thing, $category_other, $thingA)
clues.not_related($category, $thing, $category_other, $thingB)
check unique($thingA, $thingB)
clues.not_related($category, $thing, $category_other, $thingC)
check unique($thingA, $thingB, $thingC)
clues.not_related($category, $thing, $category_other, $thingD)
check unique($thingA, $thingB, $thingC, $thingD)
# Find the fifth variation of category_other.
clues.is_category($category_other, $thingE)
check unique($thingA, $thingB, $thingC, $thingD, $thingE)
assert
clues.related($category, $thing, $category_other, $thingE)
###################
# Neighbors: Basic
# Foreach "A left of 1", assert "A beside 1"
expanded_relationship_beside_left
foreach
clues.left_of($category1, $thing1, $category2, $thing2)
assert
clues.next_to($category1, $thing1, $category2, $thing2)
# Foreach "A beside 1", assert A!1
unrelated_to_beside
foreach
clues.next_to($category1, $thing1, $category2, $thing2)
check unique($category1, $category2)
assert
clues.not_related($category1, $thing1, $category2, $thing2)
###################################
# Neighbors: Spatial Relationships
# Foreach "A beside B" and "A=(at-edge)", assert "B=(near-edge)"
check_next_to_either_edge
foreach
clues.related(POSITION, $position_known, $category, $thing)
check is_edge($position_known)
clues.next_to($category, $thing, $category_other, $thing_other)
clues.is_category(POSITION, $position_other)
check is_beside($position_known, $position_other)
assert
clues.related(POSITION, $position_other, $category_other, $thing_other)
# Foreach "A beside B" and "A!(near-edge)" and "B!(near-edge)", assert "A!(at-edge)"
check_too_close_to_edge
foreach
clues.next_to($category, $thing, $category_other, $thing_other)
clues.is_category(POSITION, $position_edge)
clues.is_category(POSITION, $position_near_edge)
check is_edge($position_edge) and is_beside($position_edge, $position_near_edge)
clues.not_related(POSITION, $position_near_edge, $category, $thing)
clues.not_related(POSITION, $position_near_edge, $category_other, $thing_other)
assert
clues.not_related(POSITION, $position_edge, $category, $thing)
# Foreach "A beside B" and "A!(one-side)", assert "A=(other-side)"
check_next_to_with_other_side_impossible
foreach
clues.next_to($category, $thing, $category_other, $thing_other)
clues.related(POSITION, $position_known, $category_other, $thing_other)
check not is_edge($position_known)
clues.not_related($category, $thing, POSITION, $position_one_side)
check is_beside($position_known, $position_one_side)
clues.is_category(POSITION, $position_other_side)
check is_beside($position_known, $position_other_side) \
and unique($position_known, $position_one_side, $position_other_side)
assert
clues.related($category, $thing, POSITION, $position_other_side)
# Foreach "A left of B"...
# ... and "C=(position1)" and "D=(position2)" and "E=(position3)"
# ~> assert "A=(other-position)" and "B=(other-position)+1"
left_of_and_only_two_slots_remaining
foreach
clues.left_of($category_left, $thing_left, $category_right, $thing_right)
clues.related($category_left, $thing_left_other1, POSITION, $position1)
clues.related($category_left, $thing_left_other2, POSITION, $position2)
clues.related($category_left, $thing_left_other3, POSITION, $position3)
check unique($thing_left, $thing_left_other1, $thing_left_other2, $thing_left_other3)
clues.related($category_right, $thing_right_other1, POSITION, $position1)
clues.related($category_right, $thing_right_other2, POSITION, $position2)
clues.related($category_right, $thing_right_other3, POSITION, $position3)
check unique($thing_right, $thing_right_other1, $thing_right_other2, $thing_right_other3)
clues.is_category(POSITION, $position4)
clues.is_category(POSITION, $position5)
check is_left_right($position4, $position5) \
and unique($position1, $position2, $position3, $position4, $position5)
assert
clues.related(POSITION, $position4, $category_left, $thing_left)
clues.related(POSITION, $position5, $category_right, $thing_right)
#########################
fc_extras
def unique(*args):
return len(args) == len(set(args))
def is_edge(pos):
return (pos == 1) or (pos == 5)
def is_beside(pos1, pos2):
diff = (pos1 - pos2)
return (diff == 1) or (diff == -1)
def is_left_right(pos_left, pos_right):
return (pos_right - pos_left == 1)
driver.py (на самом деле больше, но в этом суть)
from pyke import knowledge_engine
engine = knowledge_engine.engine(__file__)
engine.activate('relations')
try:
natl = engine.prove_1_goal('clues.related(PET, zebra, NATIONALITY, $nationality)')[0].get('nationality')
except Exception, e:
natl = "Unknown"
print "== Who owns the zebra? %s ==" % natl
Пример вывода:
$ python driver.py
== Who owns the zebra? German ==
# Color Nationality Pet Drink Smoke
=======================================================
1 yellow Norwegian cats water Dunhill
2 blue Dane horse tea Blend
3 red English birds milk Pall Mall
4 green German zebra coffee Prince
5 white Swede dog beer Blue Master
Calculated in 1.19 seconds.
Источник: https://github.com/DreadPirateShawn/pyke-who-owns-zebra
Вот выдержка из полное решение используя Решатель, размещенный по адресу Загадка Эйнштейна в C#:
// The green house's owner drinks coffee
Post(greenHouse.Eq(coffee));
// The person who smokes Pall Mall rears birds
Post(pallMall.Eq(birds));
// The owner of the yellow house smokes Dunhill
Post(yellowHouse.Eq(dunhill));
Вот простое решение в CLP (FD) (смотрите также clpfd):
:- use_module(library(clpfd)).
solve(ZebraOwner) :-
maplist( init_dom(1..5),
[[British, Swedish, Danish, Norwegian, German], % Nationalities
[Red, Green, Blue, White, Yellow], % Houses
[Tea, Coffee, Milk, Beer, Water], % Beverages
[PallMall, Blend, Prince, Dunhill, BlueMaster], % Cigarettes
[Dog, Birds, Cats, Horse, Zebra]]), % Pets
British #= Red, % Hint 1
Swedish #= Dog, % Hint 2
Danish #= Tea, % Hint 3
Green #= White - 1 , % Hint 4
Green #= Coffee, % Hint 5
PallMall #= Birds, % Hint 6
Yellow #= Dunhill, % Hint 7
Milk #= 3, % Hint 8
Norwegian #= 1, % Hint 9
neighbor(Blend, Cats), % Hint 10
neighbor(Horse, Dunhill), % Hint 11
BlueMaster #= Beer, % Hint 12
German #= Prince, % Hint 13
neighbor(Norwegian, Blue), % Hint 14
neighbor(Blend, Water), % Hint 15
memberchk(Zebra-ZebraOwner, [British-british, Swedish-swedish, Danish-danish,
Norwegian-norwegian, German-german]).
init_dom(R, L) :-
all_distinct(L),
L ins R.
neighbor(X, Y) :-
(X #= (Y - 1)) #\/ (X #= (Y + 1)).
Запустив его, производит:
3 ?- время (решить (Z)).
% 111 798 выводов, 0,016 процессора за 0,020 секунды (78% процессора, 7166493 губ)
Z = немецкий.
Решение ES6 (Javascript)
С большим количеством Генераторы ES6 и еще немного Lodash.Вам понадобится Вавилонский Столб чтобы запустить это.
var _ = require('lodash');
function canBe(house, criteria) {
for (const key of Object.keys(criteria))
if (house[key] && house[key] !== criteria[key])
return false;
return true;
}
function* thereShouldBe(criteria, street) {
for (const i of _.range(street.length))
yield* thereShouldBeAtIndex(criteria, i, street);
}
function* thereShouldBeAtIndex(criteria, index, street) {
if (canBe(street[index], criteria)) {
const newStreet = _.cloneDeep(street);
newStreet[index] = _.assign({}, street[index], criteria);
yield newStreet;
}
}
function* leftOf(critA, critB, street) {
for (const i of _.range(street.length - 1)) {
if (canBe(street[i], critA) && canBe(street[i+1], critB)) {
const newStreet = _.cloneDeep(street);
newStreet[i ] = _.assign({}, street[i ], critA);
newStreet[i+1] = _.assign({}, street[i+1], critB);
yield newStreet;
}
}
}
function* nextTo(critA, critB, street) {
yield* leftOf(critA, critB, street);
yield* leftOf(critB, critA, street);
}
const street = [{}, {}, {}, {}, {}]; // five houses
// Btw: it turns out we don't need uniqueness constraint.
const constraints = [
s => thereShouldBe({nation: 'English', color: 'red'}, s),
s => thereShouldBe({nation: 'Swede', animal: 'dog'}, s),
s => thereShouldBe({nation: 'Dane', drink: 'tea'}, s),
s => leftOf({color: 'green'}, {color: 'white'}, s),
s => thereShouldBe({drink: 'coffee', color: 'green'}, s),
s => thereShouldBe({cigarettes: 'PallMall', animal: 'birds'}, s),
s => thereShouldBe({color: 'yellow', cigarettes: 'Dunhill'}, s),
s => thereShouldBeAtIndex({drink: 'milk'}, 2, s),
s => thereShouldBeAtIndex({nation: 'Norwegian'}, 0, s),
s => nextTo({cigarettes: 'Blend'}, {animal: 'cats'}, s),
s => nextTo({animal: 'horse'}, {cigarettes: 'Dunhill'}, s),
s => thereShouldBe({cigarettes: 'BlueMaster', drink: 'beer'}, s),
s => thereShouldBe({nation: 'German', cigarettes: 'Prince'}, s),
s => nextTo({nation: 'Norwegian'}, {color: 'blue'}, s),
s => nextTo({drink: 'water'}, {cigarettes: 'Blend'}, s),
s => thereShouldBe({animal: 'zebra'}, s), // should be somewhere
];
function* findSolution(remainingConstraints, street) {
if (remainingConstraints.length === 0)
yield street;
else
for (const newStreet of _.head(remainingConstraints)(street))
yield* findSolution(_.tail(remainingConstraints), newStreet);
}
for (const streetSolution of findSolution(constraints, street)) {
console.log(streetSolution);
}
Результат:
[ { color: 'yellow',
cigarettes: 'Dunhill',
nation: 'Norwegian',
animal: 'cats',
drink: 'water' },
{ nation: 'Dane',
drink: 'tea',
cigarettes: 'Blend',
animal: 'horse',
color: 'blue' },
{ nation: 'English',
color: 'red',
cigarettes: 'PallMall',
animal: 'birds',
drink: 'milk' },
{ color: 'green',
drink: 'coffee',
nation: 'German',
cigarettes: 'Prince',
animal: 'zebra' },
{ nation: 'Swede',
animal: 'dog',
color: 'white',
cigarettes: 'BlueMaster',
drink: 'beer' } ]
Время выполнения для меня составляет около 2,5 с, но это можно значительно улучшить, изменив порядок правил.Я решил сохранить первоначальный порядок для большей ясности.
Спасибо, это был классный вызов!
Это действительно проблема решения ограничений.Вы можете сделать это с помощью обобщенного вида распространения ограничений в языках, подобных логическому программированию.У нас есть демо-версия специально для задачи Zebra в системе ALE (attribute logic engine):
http://www.cs.toronto.edu /~gpenn/ale.html
Вот ссылка на кодирование упрощенной головоломки Zebra:
http://www.cs.toronto.edu /~gpenn/ale/files/grammars/baby.pl
Сделать это эффективно - совсем другое дело.
Самый простой способ решить такие проблемы программно - использовать вложенные циклы для всех перестановок и проверить, удовлетворяет ли результат предикатам в вопросе.Многие из предикатов могут быть перенесены из внутреннего цикла во внешние циклы, чтобы значительно снизить вычислительную сложность до тех пор, пока ответ не будет вычислен за разумное время.
Вот простое решение F #, полученное из статьи в F# Журнал:
let rec distribute y xs =
match xs with
| [] -> [[y]]
| x::xs -> (y::x::xs)::[for xs in distribute y xs -> x::xs]
let rec permute xs =
match xs with
| [] | [_] as xs -> [xs]
| x::xs -> List.collect (distribute x) (permute xs)
let find xs x = List.findIndex ((=) x) xs + 1
let eq xs x ys y = find xs x = find ys y
let nextTo xs x ys y = abs(find xs x - find ys y) = 1
let nations = ["British"; "Swedish"; "Danish"; "Norwegian"; "German"]
let houses = ["Red"; "Green"; "Blue"; "White"; "Yellow"]
let drinks = ["Milk"; "Coffee"; "Water"; "Beer"; "Tea"]
let smokes = ["Blend"; "Prince"; "Blue Master"; "Dunhill"; "Pall Mall"]
let pets = ["Dog"; "Cat"; "Zebra"; "Horse"; "Bird"]
[ for nations in permute nations do
if find nations "Norwegian" = 1 then
for houses in permute houses do
if eq nations "British" houses "Red" &&
find houses "Green" = find houses "White"-1 &&
nextTo nations "Norwegian" houses "Blue" then
for drinks in permute drinks do
if eq nations "Danish" drinks "Tea" &&
eq houses "Green" drinks "Coffee" &&
3 = find drinks "Milk" then
for smokes in permute smokes do
if eq houses "Yellow" smokes "Dunhill" &&
eq smokes "Blue Master" drinks "Beer" &&
eq nations "German" smokes "Prince" &&
nextTo smokes "Blend" drinks "Water" then
for pets in permute pets do
if eq nations "Swedish" pets "Dog" &&
eq smokes "Pall Mall" pets "Bird" &&
nextTo pets "Cat" smokes "Blend" &&
nextTo pets "Horse" smokes "Dunhill" then
yield nations, houses, drinks, smokes, pets ]
Выходной сигнал, полученный за 9 мс, равен:
val it :
(string list * string list * string list * string list * string list) list =
[(["Norwegian"; "Danish"; "British"; "German"; "Swedish"],
["Yellow"; "Blue"; "Red"; "Green"; "White"],
["Water"; "Tea"; "Milk"; "Coffee"; "Beer"],
["Dunhill"; "Blend"; "Pall Mall"; "Prince"; "Blue Master"],
["Cat"; "Horse"; "Bird"; "Zebra"; "Dog"])]
Пример Microsoft Solver Foundation из:https://msdn.microsoft.com/en-us/library/ff525831%28v=vs.93%29.aspx?f=255&MSPPError=-2147217396
delegate CspTerm NamedTerm(string name);
public static void Zebra() {
ConstraintSystem S = ConstraintSystem.CreateSolver();
var termList = new List<KeyValuePair<CspTerm, string>>();
NamedTerm House = delegate(string name) {
CspTerm x = S.CreateVariable(S.CreateIntegerInterval(1, 5), name);
termList.Add(new KeyValuePair<CspTerm, string>(x, name));
return x;
};
CspTerm English = House("English"), Spanish = House("Spanish"),
Japanese = House("Japanese"), Italian = House("Italian"),
Norwegian = House("Norwegian");
CspTerm red = House("red"), green = House("green"),
white = House("white"),
blue = House("blue"), yellow = House("yellow");
CspTerm dog = House("dog"), snails = House("snails"),
fox = House("fox"),
horse = House("horse"), zebra = House("zebra");
CspTerm painter = House("painter"), sculptor = House("sculptor"),
diplomat = House("diplomat"), violinist = House("violinist"),
doctor = House("doctor");
CspTerm tea = House("tea"), coffee = House("coffee"),
milk = House("milk"),
juice = House("juice"), water = House("water");
S.AddConstraints(
S.Unequal(English, Spanish, Japanese, Italian, Norwegian),
S.Unequal(red, green, white, blue, yellow),
S.Unequal(dog, snails, fox, horse, zebra),
S.Unequal(painter, sculptor, diplomat, violinist, doctor),
S.Unequal(tea, coffee, milk, juice, water),
S.Equal(English, red),
S.Equal(Spanish, dog),
S.Equal(Japanese, painter),
S.Equal(Italian, tea),
S.Equal(1, Norwegian),
S.Equal(green, coffee),
S.Equal(1, green - white),
S.Equal(sculptor, snails),
S.Equal(diplomat, yellow),
S.Equal(3, milk),
S.Equal(1, S.Abs(Norwegian - blue)),
S.Equal(violinist, juice),
S.Equal(1, S.Abs(fox - doctor)),
S.Equal(1, S.Abs(horse - diplomat))
);
bool unsolved = true;
ConstraintSolverSolution soln = S.Solve();
while (soln.HasFoundSolution) {
unsolved = false;
System.Console.WriteLine("solved.");
StringBuilder[] houses = new StringBuilder[5];
for (int i = 0; i < 5; i++)
houses[i] = new StringBuilder(i.ToString());
foreach (KeyValuePair<CspTerm, string> kvp in termList) {
string item = kvp.Value;
object house;
if (!soln.TryGetValue(kvp.Key, out house))
throw new InvalidProgramException(
"can't find a Term in the solution: " + item);
houses[(int)house - 1].Append(", ");
houses[(int)house - 1].Append(item);
}
foreach (StringBuilder house in houses) {
System.Console.WriteLine(house);
}
soln.GetNext();
}
if (unsolved)
System.Console.WriteLine("No solution found.");
else
System.Console.WriteLine(
"Expected: the Norwegian drinking water and the Japanese with the zebra.");
}
Это миницинковое решение головоломки zebra, как определено в Википедии:
include "globals.mzn";
% Zebra puzzle
int: nc = 5;
% Colors
int: red = 1;
int: green = 2;
int: ivory = 3;
int: yellow = 4;
int: blue = 5;
array[1..nc] of var 1..nc:color;
constraint alldifferent([color[i] | i in 1..nc]);
% Nationalities
int: eng = 1;
int: spa = 2;
int: ukr = 3;
int: nor = 4;
int: jap = 5;
array[1..nc] of var 1..nc:nationality;
constraint alldifferent([nationality[i] | i in 1..nc]);
% Pets
int: dog = 1;
int: snail = 2;
int: fox = 3;
int: horse = 4;
int: zebra = 5;
array[1..nc] of var 1..nc:pet;
constraint alldifferent([pet[i] | i in 1..nc]);
% Drinks
int: coffee = 1;
int: tea = 2;
int: milk = 3;
int: orange = 4;
int: water = 5;
array[1..nc] of var 1..nc:drink;
constraint alldifferent([drink[i] | i in 1..nc]);
% Smokes
int: oldgold = 1;
int: kools = 2;
int: chesterfields = 3;
int: luckystrike = 4;
int: parliaments = 5;
array[1..nc] of var 1..nc:smoke;
constraint alldifferent([smoke[i] | i in 1..nc]);
% The Englishman lives in the red house.
constraint forall ([nationality[i] == eng <-> color[i] == red | i in 1..nc]);
% The Spaniard owns the dog.
constraint forall ([nationality[i] == spa <-> pet[i] == dog | i in 1..nc]);
% Coffee is drunk in the green house.
constraint forall ([color[i] == green <-> drink[i] == coffee | i in 1..nc]);
% The Ukrainian drinks tea.
constraint forall ([nationality[i] == ukr <-> drink[i] == tea | i in 1..nc]);
% The green house is immediately to the right of the ivory house.
constraint forall ([color[i] == ivory -> if i<nc then color[i+1] == green else false endif | i in 1..nc]);
% The Old Gold smoker owns snails.
constraint forall ([smoke[i] == oldgold <-> pet[i] == snail | i in 1..nc]);
% Kools are smoked in the yellow house.
constraint forall ([smoke[i] == kools <-> color[i] == yellow | i in 1..nc]);
% Milk is drunk in the middle house.
constraint drink[3] == milk;
% The Norwegian lives in the first house.
constraint nationality[1] == nor;
% The man who smokes Chesterfields lives in the house next to the man with the fox.
constraint forall ([smoke[i] == chesterfields -> (if i>1 then pet[i-1] == fox else false endif \/ if i<nc then pet[i+1] == fox else false endif) | i in 1..nc]);
% Kools are smoked in the house next to the house where the horse is kept.
constraint forall ([smoke[i] == kools -> (if i>1 then pet[i-1] == horse else false endif \/ if i<nc then pet[i+1] == horse else false endif)| i in 1..nc]);
%The Lucky Strike smoker drinks orange juice.
constraint forall ([smoke[i] == luckystrike <-> drink[i] == orange | i in 1..nc]);
% The Japanese smokes Parliaments.
constraint forall ([nationality[i] == jap <-> smoke[i] == parliaments | i in 1..nc]);
% The Norwegian lives next to the blue house.
constraint forall ([color[i] == blue -> (if i > 1 then nationality[i-1] == nor else false endif \/ if i<nc then nationality[i+1] == nor else false endif) | i in 1..nc]);
solve satisfy;
Решение:
Compiling zebra.mzn
Running zebra.mzn
color = array1d(1..5 ,[4, 5, 1, 3, 2]);
nationality = array1d(1..5 ,[4, 3, 1, 2, 5]);
pet = array1d(1..5 ,[3, 4, 2, 1, 5]);
drink = array1d(1..5 ,[5, 2, 3, 4, 1]);
smoke = array1d(1..5 ,[2, 3, 1, 4, 5]);
----------
Finished in 47msec