Вступ
Головоломка про зебру - це відома логічна головоломка, у якій є пʼять будинків, кожен пофарбований в інший колір.
У будинках живуть різні мешканці: вони мають різні національності, тримають різних улюбленців, пʼють різні напої та мають різні захоплення.
Щоб допомогти розвʼязати головоломку, нам дають 15 тверджень, які описують розвʼязок.
Однак лише поєднавши інформацію з усіх тверджень, ми зможемо знайти розвʼязок головоломки.
Головоломка про зебру належить до задач задоволення обмежень (CSP).
У такій задачі ми маємо набір можливих значень і набір обмежень, які визначають, які з цих значень припустимі.
Ще одна відома задача задоволення обмежень - судоку.
Вказівки
Розвʼяжіть задачу про зебру та знайдіть відповіді на ці два запитання:
- Хто з мешканців пʼє воду?
- Хто тримає зебру?
Задача
Про всі наведені нижче 15 тверджень відомо, що вони правдиві:
- Є пʼять будинків.
- Англієць живе в червоному будинку.
- Іспанець тримає собаку.
- Мешканець зеленого будинку пʼє каву.
- Українець пʼє чай.
- Зелений будинок стоїть одразу праворуч від будинку кольору слонової кістки.
- Той, хто тримає равлика, любить ходити на танці.
- У жовтому будинку живе художник.
- Мешканець середнього будинку пʼє молоко.
- Норвежець живе в першому будинку.
- Той, хто любить читати, живе в будинку поруч із тим, у кого живе лисиця.
- Будинок художника стоїть поруч із будинком, де живе кінь.
- Той, хто грає у футбол, пʼє апельсиновий сік.
- Японець грає в шахи.
- Норвежець живе поруч із синім будинком.
Крім того, кожен із пʼяти будинків пофарбований в інший колір, а їхні мешканці різного національного походження, тримають різних тварин, пʼють різні напої та мають різні захоплення.
Існує 24 мільярди (5!⁵ = 24,883,200,000) можливих розвʼязків, тож спробуйте відкинути якомога більше з них.
Підказки
У цій вправі нам потрібно опрацювати колекцію даних. Ми можемо спростити свій код, використавши ліниві послідовності, щоб підвищити продуктивність.
Докладніше див. ліниве обчислення.
