Кому принадлежит рыбка: задача Эйнштейна с точки зрения оптимизации

«Только 1% людей способны решить эту задачу». С такой подписью в школьные годы мне попалась задача Эйнштейна. На подобную наживку я тогда клевал без раздумий и решал честно, как велели правила: в уме, без бумаги, 40 минут на всё.

Что с тех пор изменилось? Происхождение задачи по-прежнему окутано различными историями: задачу связывают с Альбертом Эйнштейном, Льюисом Кэрроллом и редактором Life International. Но в итоге она оказалась на газетной полосе в 1962 году вышеупомянутого издания.

Профессиональное развитие накладывает свою призму на подходы к решению различных задач. Попробуем собрать этот пазл с помощью программирования в ограничениях (CP-SAT OR-Tools).

Постановка выглядит как перечисление логических высказываний о связях между характеристиками и как набор ограничений на их сочетания.

Ограничения уникальности: Есть пять домов со следующими уникальными характеристиками:

• Каждый дом своего цвета;

• Жители этих домов имеют разные национальности;

• Жители этих домов содержат различных животных;

• Жители этих домов пьют различные напитки;

• Жители этих домов курят различные марки сигарет.

Топология расположения домов — последовательная цепь. Пять домов и пять характеристик, каждая встречается ровно в одном ограничении, совокупность условий ограничивает число возможных комбинаций — подгон условия под единственное решение. Точечные условия на пары характеристик вообще приводят к формату судоку:

1. Англичанин живёт в красном доме;

2. Швед держит собаку;

3. Датчанин пьёт чай;

4. Зелёный дом стоит рядом слева от белого;

5. Жилец зелёного дома пьёт кофе;

6. Человек, который курит «Pall Mall», держит птицу;

7. Жилец из среднего дома пьёт молоко;

8. Жилец из жёлтого дома курит «Dunhill»;

9. Норвежец живёт в первом доме;

10. Курильщик «Marlboro» живёт около того, кто держит кошку;

11. Человек, который содержит лошадь, живёт около того, кто курит «Dunhill»;

12. Курильщик сигарет «Winfield» пьёт пиво;

13. Норвежец живёт около голубого дома;

14. Немец курит «Rothmans»;

15. Курильщик «Marlboro» живёт по соседству с человеком, который пьёт воду.

Кульминация постановки задачи: кому принадлежит рыбка?

Условие громоздкое — за один присест не перескажешь. Это один из усложняющих факторов: держать в уме 15 пунктов, выборочно связывающих 25 характеристик между собой.

Из пушки по воробьям: решим задачу средствами CP-SAT

LeetCode с оптимизационными задачами никто не взялся разрабатывать: эта задача непременно туда попала бы. Постановка задачи хорошо ложится в constraint satisfaction problem (CSP). Переменные кодируют номер дома для каждого атрибута и его значения (пять характеристик по пять значений в каждой); домены — номера домов; три типа ограничений (равенство, соседство, all-different).

Скелет задачи «Эйнштейна» содержит элементы, которые используются для решения вполне прикладных проблем: назначение смен сотрудников, когда исключается работа «два дня подряд»; размещение станков в производственном цехе с ограничением по совместимости; назначение экзаменов без пересечений по аудиториям и преподавателям.

Моделирование

Карандаш и бумагу заменим на несколько десятков строк кода.

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()

Солвер находит ответ за миллисекунды, а мы просто формализовали условия задачи в CP. Здесь можно проследить разницу между «решить руками» и «смоделировать»: во втором случае платим один раз за формализацию задачи, затем подставляем различные сценарии/условия.

Аналогия

Что если воспользоваться той же структурой ограничений: равенство, соседство и все разные в другой задаче, например, назначение смен сотрудникам?

• Сотрудник Иван Иваныч не может работать в одну смену с сотрудником Семён Семеныч. Ограничение all-different на уровне пары.

• 11-часовой отдых между сменами сотрудника. Ограничение соседства смен по времени.

• В каждой смене должен быть хотя бы один главный инженер. Вариация ограничения равенства — ограничение покрытия.

Детально рассматривал задачи с такими ограничениями: планирование смен хирургов и планирование смен водителей.

Незаметно скакнули от развлекательной головоломки к вполне реальным задачам составления расписаний, которые, между прочим, решаются с помощью CP-SAT или MILP-солверами. Конечно, у реальных задач планирования расписаний масштаб гораздо больше 25 переменных, но, понимая принцип решения задачи Эйнштейна на пяти домах, переход к более крупным задачам — вопрос масштабирования и терпения солвера, а не новых алгоритмов и моделей.