Вступ
Задача про зебру - це відома логічна головоломка, у якій є пʼять будинків, кожен пофарбований в інший колір.
У будинках живуть різні мешканці: вони мають різні національності, тримають різних тварин, пʼють різні напої та курять різні марки цигарок.
Щоб допомогти розвʼязати головоломку, нам дають 15 тверджень, які описують розвʼязок.
Однак лише поєднавши інформацію з усіх тверджень, ми зможемо знайти розвʼязок головоломки.
Задача про зебру - це задача задоволення обмежень (CSP).
У такій задачі є набір можливих значень і набір обмежень, які визначають, які значення допустимі.
Ще одна добре відома задача задоволення обмежень - це судоку.
Вказівки
Ваше завдання - розвʼязати загадку про зебру й знайти відповіді на два запитання:
- Хто з мешканців пʼє воду?
- У кого живе зебра?
Загадка
Наступні 15 тверджень вважаються істинними:
- Є пʼять будинків.
- Englishman живе в червоному будинку.
- Spaniard утримує собаку.
- Каву пʼють у зеленому будинку.
- Ukrainian пʼє чай.
- Зелений будинок розташований безпосередньо праворуч від будинку кольору слонової кістки.
- Курень Old Gold утримує равликів.
- Kools палять у жовтому будинку.
- Молоко пʼють у середньому будинку.
- Norwegian живе в першому будинку.
- Людина, яка палить Chesterfields, живе в будинку поруч із людиною, у якої лисиця.
- Kools палять у будинку поруч із будинком, де утримують коня.
- Курень Lucky Strike пʼє апельсиновий сік.
- Japanese палить Parliaments.
- Norwegian живе поруч із синім будинком.
Крім того, кожен із пʼяти будинків пофарбовано в інший колір, а їхні мешканці мають різне національне походження, утримують різних домашніх тварин, пʼють різні напої та палять різні марки цигарок.
Існує 24 мільярди (5!⁵ = 24,883,200,000) можливих розвʼязків, тож спробуйте виключити якомога більше розвʼязків.
