Многие логические головоломки можно решать с помощью сетки, которая представляет собой набор таблиц, связывающих между собой попарно по два измерения (категории, атрибута). Например, в разобранном ранее случае мы использовали таблицы "Имя — Специальность", "Имя — Город", "Специальность — Город". Количество связывающих таблиц равно
N * (N - 1) / 2
где N - количество категорий (измерений).
Два типа сеток
При количестве измерений = 2 (плоский случай) у нас всего одна таблица. При трёх измерениях мы имеем куб, который можно разложить на 3 таблицы и работать с ними достаточно наглядно и удобно. Это стандартная логическая сетка.
При большем количестве измерений таким же образом работать очень затруднительно. Нет удобного визуального представления 4-мерного (и более) пространства. Единственный вариант — нацелиться на решение какой-то локальной задачи и держать в голове таблицы, связывающие искомый атрибут.
Правда, есть специальный случай использования сетки для решения более сложных головоломок. Это — загадка Эйнштейна, с 6 измерениями (позиция + 5 атрибутов). Вместо 15 таблиц используют т. н. позиционную сетку Эйнштейна.
Загадка Эйнштейна и позиционная сетка
Приведём полные условия загадки Эйнштейна.
ИЗМЕРЕНИЯ:
Номер дома: Дом 1, Дом 2, Дом 3, Дом 4, Дом 5
Цвет: жёлтый, голубой, красный, зелёный, белый
Национальность: норвежец, датчанин, англичанин, немец, швед
Напиток: вода, чай, молоко, кофе, пиво
Марка сигарет: Dunhill, Blend, Pall Mall, Prince, Blue Master
Питомцы: кошка, лошадь, птицы, рыбки, собака
УСЛОВИЯ:
1. Англичанин живёт в красном доме.
2. Швед держит собаку.
3. Датчанин пьёт чай.
4. Зелёный дом стоит сразу слева от белого.
5. Хозяин зелёного дома пьёт кофе.
6. Тот, кто курит Pall Mall, держит птиц.
7. Хозяин жёлтого дома курит Dunhill.
8. В центральном доме пьют молоко.
9. Норвежец живёт в первом доме.
10. Тот, кто курит Blend, живёт рядом с тем, у кого кошка.
11. Тот, кто держит лошадей, живёт рядом с тем, кто курит Dunhill.
12. Тот, кто курит Blue Master, пьёт пиво.
13. Немец курит Prince.
14. Норвежец живёт рядом с голубым домом.
15. Тот, кто курит Blend, живёт рядом с тем, кто пьёт воду.
Для решения загадки Эйнштейна используется не 15 таблиц, а только одна — позиционная 5 х 5, где номер дома представлен в колонках, а атрибуты в строках.
Сокращение возможно из-за природы подсказок. Загадка содержит 5 соседских и порядковых условий («рядом с», «сразу слева от»). Эти условия работают только через позицию. Мы стараемся привязать все условия к позиции.
Позиция — мастер-переменная. Как только позиция атрибута зафиксирована, соседские условия каскадно определяют другие атрибуты.
Четыре типа подсказок и порядок их использования
Правило приоритета: сначала все якорные (дают прямую запись в сетку), затем все прямые связи (сужают диапазон), затем порядковые и соседские — применяются к уже частично заполненной сетке.
Алгоритм решения загадки Эйнштейна
Шаг 1. Якорные условия — вносим напрямую:
Условие 9: Норвежец → Дом 1.
Условие 8: Молоко → Дом 3.
Вот позиционная сетка после установки "якорей".
Шаг 2. Соседское условие 14 активируется первым якорем:
14. Норвежец живёт рядом с голубым домом.
Норвежец в доме 1 → сосед с голубым домом → голубой = дом 2.
Шаг 3. Какой дом зелёный:
5. Хозяин зелёного дома пьёт кофе.
Дом 3 — молоко, значит зелёный — не дом 3.
4. Зелёный дом стоит сразу слева от белого.
Дом 1 — норвежец (цвет пока неизвестен). Дом 2 — голубой. Зелёный не может быть домом №1 (сосед №2 голубой, не белый), не №2 (голубой), не №5 (нет дома правее).
Остаётся только дом 4. → зелёный = 4, белый = 5.
Шаг 4. Определяем оставшиеся цвета
Остались красный и жёлтый дома.
1. Англичанин живёт в красном доме.
Норвежец в доме 1. Если красный = дом 1, то норвежец = англичанин — противоречие. Значит: жёлтый = дом 1, красный = дом 3 = англичанин.
Шаг 5. Прямое условие 7:
7. Хозяин жёлтого дома курит Dunhill.
Дом 1 = жёлтый = Dunhill.
Шаг 6. Соседское условие 11:
11. Тот, кто держит лошадей, живёт рядом с тем, кто курит Dunhill.
Dunhill в доме 1 → лошадь только в доме 2 (единственный сосед). Дом 2 = лошадь.
Шаг 7. Прямое условие 5:
5. Хозяин зелёного дома пьёт кофе.
Дом 4 = кофе.
Шаг 8. Что пьют в Доме 1:
3. Датчанин пьёт чай.
Дом 1 ≠ чай.
12. Тот, кто курит Blue Master, пьёт пиво.
Дом 1 (курят Dunhill) ≠ пиво
Остаётся: Дом 1 = вода.
Шаг 9. Соседское условие 15:
15. Тот, кто курит Blend, живёт рядом с тем, кто пьёт воду.
Blend = Дом 2
Шаг 10. Где пьют чай и пиво:
Чай или пиво пьют в доме 2 или доме 5.
12. Тот, кто курит Blue Master, пьёт пиво.
Пиво не может быть в доме 2 потому что там курят Blend → Дом 2 = чай. Дом 5 = пиво = Blue Master.
3. Датчанин пьёт чай.
Дом 2 = Датчанин.
Шаг 11. Где живёт немец
13. Немец курит Prince.
Немец = дом 4 = Prince.
Остается один вариант для сигарет:
Pall Mall = дом 3.
Остается один вариант для национальности:
Швед = дом 5.
Шаг 12. Прямые условия 2 и 6:
2. Швед держит собаку.
Швед = собака
6. Тот, кто курит Pall Mall, держит птиц.
Дом 3 = птицы.
Шаг 13. Соседское условие 10:
10. Тот, кто курит Blend, живёт рядом с тем, у кого кошка.
Blend = дом 2 → Кошка = дом 1
Немец = рыбки
Окончательный вариант решения.
Ответ: рыбок держит немец (дом 4).
Количество шагов, нужных для решения, зависит от того, какие и в каком порядке условия вы обрабатываете.
Применимость метода позиционной сетки к другим задачам
Метод работает для любой задачи класса «зебра-пазл» при условии:
— Есть хотя бы одна якорная подсказка (точная позиция или единственно возможное значение).
— Подсказки образуют связный граф — каждый вывод открывает хотя бы одну следующую подсказку.
— Задача имеет единственное решение (это гарантируется правильно составленным набором условий).
Если задача имеет чисто бинарные (попарные) условия, то стандартная сетка эффективнее.