«Только 1% людей способны решить эту задачу». С такой подписью в школьные годы мне попалась задача Эйнштейна. На подобную наживку я тогда клевал без раздумий и решал честно, как велели правила: в уме, без бумаги, 40 минут на всё.
Что с тех пор изменилось? Происхождение задачи по-прежнему окутано различными историями: задачу связывают с Альбертом Эйнштейном, Льюисом Кэрроллом и редактором Life International. Но в итоге она оказалась на газетной полосе в 1962 году вышеупомянутого издания.
Профессиональное развитие накладывает свою призму на подходы к решению различных задач. Попробуем собрать этот пазл с помощью программирования в ограничениях (CP-SAT OR-Tools).
Постановка выглядит как перечисление логических высказываний о связях между характеристиками и как набор ограничений на их сочетания.
Ограничения уникальности: Есть пять домов со следующими уникальными характеристиками:
Каждый дом своего цвета;
Жители этих домов имеют разные национальности;
Жители этих домов содержат различных животных;
Жители этих домов пьют различные напитки;
Жители этих домов курят различные марки сигарет.
Топология расположения домов — последовательная цепь. Пять домов и пять характеристик, каждая встречается ровно в одном ограничении, совокупность условий ограничивает число возможных комбинаций — подгон условия под единственное решение. Точечные условия на пары характеристик вообще приводят к формату судоку:
Англичанин живёт в красном доме;
Швед держит собаку;
Датчанин пьёт чай;
Зелёный дом стоит рядом слева от белого;
Жилец зелёного дома пьёт кофе;
Человек, который курит «Pall Mall», держит птицу;
Жилец из среднего дома пьёт молоко;
Жилец из жёлтого дома курит «Dunhill»;
Норвежец живёт в первом доме;
Курильщик «Marlboro» живёт около того, кто держит кошку;
Человек, который содержит лошадь, живёт около того, кто курит «Dunhill»;
Курильщик сигарет «Winfield» пьёт пиво;
Норвежец живёт около голубого дома;
Немец курит «Rothmans»;
Курильщик «Marlboro» живёт по соседству с человеком, который пьёт воду.
Кульминация постановки задачи: кому принадлежит рыбка?
Условие громоздкое — за один присест не перескажешь. Это один из усложняющих факторов: держать в уме 15 пунктов, выборочно связывающих 25 характеристик между собой.
Из пушки по воробьям: решим задачу средствами CP-SAT
LeetCode с оптимизационными задачами никто не взялся разрабатывать: эта задача непременно туда попала бы. Постановка задачи хорошо ложится в constraint satisfaction problem (CSP). Переменные кодируют номер дома для каждого атрибута и его значения (пять характеристик по пять значений в каждой); домены — номера домов; три типа ограничений (равенство, соседство, all-different).
Скелет задачи «Эйнштейна» содержит элементы, которые используются для решения вполне прикладных проблем: назначение смен сотрудников, когда исключается работа «два дня подряд»; размещение станков в производственном цехе с ограничением по совместимости; назначение экзаменов без пересечений по аудиториям и преподавателям.
Моделирование
Карандаш и бумагу заменим на несколько десятков строк кода.
Реализация и решение задачи в python при помощи CP-SAT.
from ortools.sat.python import cp_model # Список домов houses = range(5) # Характеристики и их возможные значения categories = { "национальность": ["Англичанин", "Швед", "Датчанин", "Норвежец", "Немец"], "цвет": ["красный", "зелёный", "белый", "жёлтый", "голубой"], "животное": ["собака", "птица", "кошка", "лошадь", "рыба"], "напиток": ["чай", "кофе", "молоко", "пиво", "вода"], "сигареты": ["Pall Mall", "Dunhill", "Marlboro", "Winfield", "Rothmans"], } def solve_fish_problem(): """ Построение CP модели и решение задачи """ model = cp_model.CpModel() # Инициализация переменных для каждого характеристики и ее значения house = { category: { value: model.NewIntVar(0, 4, f"{category}_{value}") for value in values } for category, values in categories.items() } # У кажой характеристики-значение может быть только один дом for variables in house.values(): model.AddAllDifferent(list(variables.values())) # Конструктор ограничений типа равенство def same(category_a, value_a, category_b, value_b): model.Add(house[category_a][value_a] == house[category_b][value_b]) # Конструктор ограничений типа "рядом" def next_to(category_a, value_a, category_b, value_b): distance = model.NewIntVar(0, 4, "distance") model.AddAbsEquality( distance, house[category_a][value_a] - house[category_b][value_b], ) model.Add(distance == 1) same("национальность", "Англичанин", "цвет", "красный") same("национальность", "Швед", "животное", "собака") same("национальность", "Датчанин", "напиток", "чай") model.Add(house["цвет"]["зелёный"] + 1 == house["цвет"]["белый"]) same("цвет", "зелёный", "напиток", "кофе") same("сигареты", "Pall Mall", "животное", "птица") model.Add(house["напиток"]["молоко"] == 2) same("цвет", "жёлтый", "сигареты", "Dunhill") model.Add(house["национальность"]["Норвежец"] == 0) next_to("сигареты", "Marlboro", "животное", "кошка") next_to("животное", "лошадь", "сигареты", "Dunhill") same("сигареты", "Winfield", "напиток", "пиво") next_to("национальность", "Норвежец", "цвет", "голубой") same("национальность", "Немец", "сигареты", "Rothmans") next_to("сигареты", "Marlboro", "напиток", "вода") solver = cp_model.CpSolver() status = solver.Solve(model) if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE): print("Решение не найдено") return fish_house = solver.Value(house["животное"]["рыба"]) fish_owner = next( nationality for nationality in categories["национальность"] if solver.Value(house["национальность"][nationality]) == fish_house ) print(f"\nРыбка принадлежит: {fish_owner}") if __name__ == "__main__": solve_fish_problem()
Рыбка живёт у ...
Дом | Национальность | Цвет | Животное | Напиток | Сигареты |
|---|---|---|---|---|---|
1 | Норвежец | жёлтый | кошка | вода | Dunhill |
2 | Датчанин | голубой | лошадь | чай | Marlboro |
3 | Англичанин | красный | птица | молоко | Pall Mall |
4 | Немец | зелёный | рыба | кофе | Rothmans |
5 | Швед | белый | собака | пиво | Winfield |
Солвер находит ответ за миллисекунды, а мы просто формализовали условия задачи в CP. Здесь можно проследить разницу между «решить руками» и «смоделировать»: во втором случае платим один раз за формализацию задачи, затем подставляем различные сценарии/условия.
Аналогия
Что если воспользоваться той же структурой ограничений: равенство, соседство и все разные в другой задаче, например, назначение смен сотрудникам?
Сотрудник Иван Иваныч не может работать в одну смену с сотрудником Семён Семеныч. Ограничение all-different на уровне пары.
11-часовой отдых между сменами сотрудника. Ограничение соседства смен по времени.
В каждой смене должен быть хотя бы один главный инженер. Вариация ограничения равенства — ограничение покрытия.
Детально рассматривал задачи с такими ограничениями: планирование смен хирургов и планирование смен водителей.
Незаметно скакнули от развлекательной головоломки к вполне реальным задачам составления расписаний, которые, между прочим, решаются с помощью CP-SAT или MILP-солверами. Конечно, у реальных задач планирования расписаний масштаб гораздо больше 25 переменных, но, понимая принцип решения задачи Эйнштейна на пяти домах, переход к более крупным задачам — вопрос масштабирования и терпения солвера, а не новых алгоритмов и моделей.
