![](https://habrastorage.org/webt/sm/wd/pu/smwdpuay0kombaijwgt8h-d_v7u.jpeg)
SQL — язык сверхвысокого уровня, а SQL-движки очень высоко оптимизированы. И поэтому во многих случаях с помощью него можно просто и быстро решать сложные задачи. Вы удивитесь, но даже существует шахматный движок на SQL.
Сегодня мы рассмотрим решение непростой загадки Джиндоша из замечательной игры Dishonored 2 с помощью SQL.
Загадка Джиндоша
Во время игры Dishonored 2 мы сталкиваемся с запертой изобретателем Джиндошем кодовой дверью, чтобы её открыть нужно решить весьма запутанную загадку, ну или бегать по всей карте, ища другие подсказки.
Вот сама задача:
![](https://habrastorage.org/webt/jw/gw/il/jwgwilclee8rsz0ulk39a-hszls.jpeg)
Вот текст задачи для тех, кому неудобно читать с картинки:
На званом обеде были леди Уинслоу, доктор Марколла, графиня Конти, мадам Нациу и баронесса Финч.
Женщины сидели в ряд. Все они были одеты в разные цвета. Например, Леди Уинслоу носила причудливое синее пончо; Доктор Марколла левее всех, рядом с гостьей, одетой в белое. Дама, одетая в красное платье, сидела слева от гостьи, одетой в пурпурное. Я помню красное платье, потому что его обладательница пролила на него виски. Путешественница, недавно покинувшая Морли, была одета во всё зелёное. Когда одна гостья хвастливо демонстрировала Портсигар, женщина, сидевшая рядом с ней, заметила: «Мой родной Морли славится такими безделушками».
Тогда Баронесса Финч достала из сумочки свою фамильную ценность — Кулон с птицей. Дама, до того рассказывавшая, как красив в это время года её родной край, Фрейпорт, с усмешкой заметила, что её Перстень — куда большая редкость. Другая дама начала демонстративно рассматривать свою реликвию — Бриллиант; сидевшая рядом с ней гостья (помнится, её родина — Дануолл) чуть не выбила коктейль из рук своей соседки. Внезапно Графиня Конти, пившая исключительно абсент, предложила тост. Дама, которой предстояло навестить Серконос и которая весь вечер налегала на сидр, попыталась запрыгнуть на стол, но повалилась на гостью, сидевшую посередине, и та пролила ром. Затем Мадам Нациу завладела всеобщим вниманием, рассказав про Бейлтон времён своей юности.
Наутро под столом валялись 4 фамильные драгоценности: Портсигар, Орден, Перстень и Бриллиант.
Но кому принадлежит каждая из них?
Для каждого игрока меняются цвета, имена дам и т. п. Мы будем решать вариант, описанный выше.
На первый взгляд эта загадка кажется бредом, каким-то потоком сознания пьяной аристократки, но с помощью SQL, а точнее MySQL, мы её решим.
Подход к решению
Общий подход будет следующий: мы с помощью JOIN создадим все возможные комбинации дам, ценностей, мест, цветов и напитков, а потом ограничим это с помощью условий.
В подобных задачах SQL хорошо себя показывает по скорости, иногда даже лучше, чем компилируемые языки. Был случай в моей практике, когда более сложная переборная задача, чем эта, решалась SQL-запросом быстрее, чем скомпилированный код на Haskel.
SQL-база имеет планировщик, который замечательно выстраивает план запроса и выполняет перебор не полный, а с возвратом, оптимизированный, быстро сужая его область. SQL-движки уже многие десятилетия эволюционируют и тщательно оптимизированы для того, чтобы выдавать быстрый результат. Вплоть до того, что иногда используется внутренняя компиляция запроса в нативный код или байт-код.
Итак, для начала создадим таблицы, в которые занесём все классы информации, встретившиеся в этой задаче. Я установил MySQL на виртуальный сервер RUVDS, поэтому использую СУБД прямо из сессии SSH для решения этой загадки.
Решаем загадку
▍ Структуры данных
create database dis2;
use dis2;
-- Имена дам
create table Names (name char(10)) ENGINE=MEMORY;
insert into Names values ('Winslow'), ('Marcolla'), ('Contee'), ('Natsiou'), ('Finch');
-- Позиции дам за столом
create table Positions (pos int) ENGINE=MEMORY;
insert into Positions values (1), (2), (3), (4), (5);
-- Цвета платьев
create table Colors (color char(10)) ENGINE=MEMORY;
insert into Colors values ('red'), ('white'), ('purple'), ('blue'), ('green');
-- Родные города дам
create table Cities (city char(10)) ENGINE=MEMORY;
insert into Cities values ('Bailton'), ('Serkonos'), ('Freiport'), ('Morley'), ('Danuol');
-- Напитки дам
create table Drinks (drink char(10)) ENGINE=MEMORY;
insert into Drinks values ('absent'), ('coctail'), ('rum'), ('cider'), ('whiskey');
-- Ценности
create table Items (item char(10)) ENGINE=MEMORY;
insert into Items values ('ring'), ('diamond'), ('order'), ('cigar-case'), ('coulomb');
Я использую движок таблиц MEMORY для скорости. Это вещь специфичная для MySQL. В других SQL БД «ENGINE=MEMORY» указывать не нужно. Строго говоря, в этой задачке выбор движка MEMORY ни на что не повлияет, но если бы перебор был более значительным, то это увеличило бы скорость.
▍ Соединяем таблицы для создания всех возможных вариантов
Теперь подсоединим все таблички друг к другу и впишем условия. Соединить таблицы в MySQL мы можем через JOIN, INNER JOIN, CROSS JOIN и без JOIN вообще — через запятую.
Мы это делаем для того, чтобы создать абсолютно все варианты сочетаний имён, платьев, городов, ценностей и цветов. К каждой строке первой таблицы будут присоединены все варианты строк из всех остальных таблиц.
Пример соединения таблиц через INNER JOIN:
SELECT COUNT(*) FROM Positions
INNER JOIN Names
INNER JOIN Colors
INNER JOIN Drinks
INNER JOIN Cities
INNER JOIN Items
Получим 15625 вариантов. Для краткости записи соединим таблицы через запятую и добавим условия, которые выудим из текста, чтобы уменьшить число вариантов.
▍ Добавляем условия для минимизации числа вариантов
Возьмём, к примеру, условие «путешественница покинувшая Морли была одета во всё зелёное». Из этого условия следуют ДВА взаимоисключающих условия для каждой строки на SQL:
city='Morley' AND color = 'green'
city!='Morley' AND color != 'green'
Поскольку условия взаимоисключающие, то они будут соединены через OR (ИЛИ). После этого такое комбинированное условие должно выполняться абсолютно на каждой строке вывода.
А все пары таких условий мы соединим через AND, так как они должны выполняться для всех нужных нам строк.
Однако мы не сможем записать абсолютно все условия, так как некоторые условия касаются позиции (левее, правее, рядом), а строки в SQL-выводе не связаны между собой. Это сделано по дизайну SQL, поэтому условиями, связанными с порядком, в котором сидели дамы, мы займёмся позже.
SELECT pos, name, item, color, drink, city FROM Positions, Names, Colors, Drinks, Cities, Items
WHERE
((name='Winslow' AND color = 'blue') OR (name!='Winslow' AND color != 'blue'))
AND
((name='Marcolla' AND pos = 1) OR (name!='Marcolla' AND pos != 1))
AND
((color='white' AND pos = 2) OR (color!='white' AND pos != 2))
AND
((color='red' AND drink = 'whiskey') OR (color!='red' AND drink != 'whiskey'))
AND
((city='Morley' AND color = 'green') OR (city!='Morley' AND color != 'green'))
AND
((name='Finch' AND item = 'coulomb') OR (name!='Finch' AND item != 'coulomb'))
AND
((city='Freiport' AND item = 'ring') OR (city!='Freiport' AND item != 'ring'))
AND
((name='Contee' AND drink = 'absent') OR (name!='Contee' AND drink != 'absent'))
AND
((city='Serkonos' AND drink = 'cider') OR (city!='Serkonos' AND drink != 'cider'))
AND
((pos=3 AND drink = 'rum') OR (pos!=3 AND drink != 'rum'))
AND
((name='Natsiou' AND city = 'Bailton') OR (name!='Natsiou' AND city != 'Bailton'))
ORDER BY pos, name, item, color, city;
Получим 80 строк.
+------+----------+------------+--------+---------+----------+
| pos | name | item | color | drink | city |
+------+----------+------------+--------+---------+----------+
| 1 | Marcolla | cigar-case | green | coctail | Morley |
| 1 | Marcolla | cigar-case | purple | coctail | Danuol |
| 1 | Marcolla | cigar-case | purple | cider | Serkonos |
| 1 | Marcolla | cigar-case | red | whiskey | Danuol |
| 1 | Marcolla | diamond | green | coctail | Morley |
| 1 | Marcolla | diamond | purple | coctail | Danuol |
| 1 | Marcolla | diamond | purple | cider | Serkonos |
| 1 | Marcolla | diamond | red | whiskey | Danuol |
| 1 | Marcolla | order | green | coctail | Morley |
| 1 | Marcolla | order | purple | coctail | Danuol |
| 1 | Marcolla | order | purple | cider | Serkonos |
| 1 | Marcolla | order | red | whiskey | Danuol |
| 1 | Marcolla | ring | purple | coctail | Freiport |
| 1 | Marcolla | ring | red | whiskey | Freiport |
| 2 | Contee | cigar-case | white | absent | Danuol |
| 2 | Contee | diamond | white | absent | Danuol |
| 2 | Contee | order | white | absent | Danuol |
| 2 | Contee | ring | white | absent | Freiport |
| 2 | Finch | coulomb | white | coctail | Danuol |
| 2 | Finch | coulomb | white | cider | Serkonos |
| 2 | Natsiou | cigar-case | white | coctail | Bailton |
| 2 | Natsiou | diamond | white | coctail | Bailton |
| 2 | Natsiou | order | white | coctail | Bailton |
| 3 | Finch | coulomb | green | rum | Morley |
| 3 | Finch | coulomb | purple | rum | Danuol |
| 3 | Natsiou | cigar-case | purple | rum | Bailton |
| 3 | Natsiou | diamond | purple | rum | Bailton |
| 3 | Natsiou | order | purple | rum | Bailton |
| 3 | Winslow | cigar-case | blue | rum | Danuol |
| 3 | Winslow | diamond | blue | rum | Danuol |
| 3 | Winslow | order | blue | rum | Danuol |
| 3 | Winslow | ring | blue | rum | Freiport |
| 4 | Contee | cigar-case | green | absent | Morley |
| 4 | Contee | cigar-case | purple | absent | Danuol |
| 4 | Contee | diamond | green | absent | Morley |
| 4 | Contee | diamond | purple | absent | Danuol |
| 4 | Contee | order | green | absent | Morley |
| 4 | Contee | order | purple | absent | Danuol |
| 4 | Contee | ring | purple | absent | Freiport |
| 4 | Finch | coulomb | green | coctail | Morley |
| 4 | Finch | coulomb | purple | coctail | Danuol |
| 4 | Finch | coulomb | purple | cider | Serkonos |
| 4 | Finch | coulomb | red | whiskey | Danuol |
| 4 | Natsiou | cigar-case | purple | coctail | Bailton |
| 4 | Natsiou | cigar-case | red | whiskey | Bailton |
| 4 | Natsiou | diamond | purple | coctail | Bailton |
| 4 | Natsiou | diamond | red | whiskey | Bailton |
| 4 | Natsiou | order | purple | coctail | Bailton |
| 4 | Natsiou | order | red | whiskey | Bailton |
| 4 | Winslow | cigar-case | blue | coctail | Danuol |
| 4 | Winslow | cigar-case | blue | cider | Serkonos |
| 4 | Winslow | diamond | blue | coctail | Danuol |
| 4 | Winslow | diamond | blue | cider | Serkonos |
| 4 | Winslow | order | blue | coctail | Danuol |
| 4 | Winslow | order | blue | cider | Serkonos |
| 4 | Winslow | ring | blue | coctail | Freiport |
| 5 | Contee | cigar-case | green | absent | Morley |
| 5 | Contee | cigar-case | purple | absent | Danuol |
| 5 | Contee | diamond | green | absent | Morley |
| 5 | Contee | diamond | purple | absent | Danuol |
| 5 | Contee | order | green | absent | Morley |
| 5 | Contee | order | purple | absent | Danuol |
| 5 | Contee | ring | purple | absent | Freiport |
| 5 | Finch | coulomb | green | coctail | Morley |
| 5 | Finch | coulomb | purple | coctail | Danuol |
| 5 | Finch | coulomb | purple | cider | Serkonos |
| 5 | Finch | coulomb | red | whiskey | Danuol |
| 5 | Natsiou | cigar-case | purple | coctail | Bailton |
| 5 | Natsiou | cigar-case | red | whiskey | Bailton |
| 5 | Natsiou | diamond | purple | coctail | Bailton |
| 5 | Natsiou | diamond | red | whiskey | Bailton |
| 5 | Natsiou | order | purple | coctail | Bailton |
| 5 | Natsiou | order | red | whiskey | Bailton |
| 5 | Winslow | cigar-case | blue | coctail | Danuol |
| 5 | Winslow | cigar-case | blue | cider | Serkonos |
| 5 | Winslow | diamond | blue | coctail | Danuol |
| 5 | Winslow | diamond | blue | cider | Serkonos |
| 5 | Winslow | order | blue | coctail | Danuol |
| 5 | Winslow | order | blue | cider | Serkonos |
| 5 | Winslow | ring | blue | coctail | Freiport |
+------+----------+------------+--------+---------+----------+
80 rows in set (0,00 sec)
create table s (pos int, name char(10), item char(10), color char(10), drink char(10), city char(10)) ENGINE=MEMORY;
INSERT INTO s
SELECT pos, name, item, color, drink, city FROM Positions, Names, Colors, Drinks, Cities, Items
WHERE
((name='Winslow' AND color = 'blue') OR (name!='Winslow' AND color != 'blue'))
AND
((name='Marcolla' AND pos = 1) OR (name!='Marcolla' AND pos != 1))
AND
((color='white' AND pos = 2) OR (color!='white' AND pos != 2))
AND
((color='red' AND drink = 'whiskey') OR (color!='red' AND drink != 'whiskey'))
AND
((city='Morley' AND color = 'green') OR (city!='Morley' AND color != 'green'))
AND
((name='Finch' AND item = 'coulomb') OR (name!='Finch' AND item != 'coulomb'))
AND
((city='Freiport' AND item = 'ring') OR (city!='Freiport' AND item != 'ring'))
AND
((name='Contee' AND drink = 'absent') OR (name!='Contee' AND drink != 'absent'))
AND
((city='Serkonos' AND drink = 'cider') OR (city!='Serkonos' AND drink != 'cider'))
AND
((pos=3 AND drink = 'rum') OR (pos!=3 AND drink != 'rum'))
AND
((name='Natsiou' AND city = 'Bailton') OR (name!='Natsiou' AND city != 'Bailton'));
▍ Новый запрос с особыми условиями, для обеспечения правильного уникального порядка элементов
Но нам нужно 5 строк с разными именами дам. Поэтому теперь мы наложим условие, чтобы те элементы (имя, цвет, город, предмет, напиток), которые были использованы в первой строке (и последующих строках) не были использованы далее. Но в SQL мы не можем обращаться к произвольным строкам вывода по дизайну. Обойдём это ограничение, выведя всю нужную информацию в одну строку.
Для этого мы будем теперь присоединять полученную таблицу s саму к себе, и накладывать эти условия. Хоть эти условия и выглядят многословно и сложно, по сути они очень просты.
Для того, чтобы присоединять таблицу s саму к себе, нам потребуется при каждом присоединении давать ей новый псевдоним. Это будут t1, t2, t3, t4, t5.
Запросили в одну строку имя первой дамы, потом её предмет, потом имя второй дамы и её предмет, и так далее.
SELECT t1.name, t1.item, t2.name, t2.item, t3.name, t3.item, t4.name, t4.item, t5.name, t5.item
FROM s t1
JOIN s t2 ON t2.name != t1.name
AND t2.item != t1.item
AND t2.color != t1.color
AND t2.drink != t1.drink
AND t2.city != t1.city
JOIN s t3 ON t3.name NOT IN (t1.name, t2.name)
AND t3.item NOT IN (t1.item, t2.item)
AND t3.color NOT IN (t1.color, t2.color)
AND t3.drink NOT IN (t1.drink, t2.drink)
AND t3.city NOT IN (t1.city, t2.city)
JOIN s t4 ON t4.name NOT IN (t1.name, t2.name, t3.name)
AND t4.item NOT IN (t1.item, t2.item, t3.item)
AND t4.color NOT IN (t1.color, t2.color, t3.color)
AND t4.drink NOT IN (t1.drink, t2.drink, t3.drink)
AND t4.city NOT IN (t1.city, t2.city, t3.city)
JOIN s t5 ON t5.name NOT IN (t1.name, t2.name, t3.name, t4.name)
AND t5.item NOT IN (t1.item, t2.item, t3.item, t4.item)
AND t5.color NOT IN (t1.color, t2.color, t3.color, t4.color)
AND t5.drink NOT IN (t1.drink, t2.drink, t3.drink, t4.drink)
AND t5.city NOT IN (t1.city, t2.city, t3.city, t4.city)
Да, запрос получился большой, хотя он по сути примитивный. Если кто придумает, как его сократить — добро пожаловать в комментарии.
▍ Добавляем условия, связанные с относительным расположением дам на банкете
WHERE
-- Мы хотим вывести дам в том порядке, в котором они сидели
t1.pos = 1 AND t2.pos=2 AND t3.pos = 3 AND t4.pos=4 AND t5.pos=5
-- Дама в красном сидит левее дамы в пурпурном, но место 2 занято дамой в белом, поэтому остаются места 3 и 4
AND (
(t3.color='red' AND t4.color='purple' ) OR (t4.color='red' AND t5.color='purple')
)
-- Рядом с дамой с портсигаром сидит дама из Морли
AND
(
(t1.item='cigar-case' AND t2.city='Morley') OR
(t2.item='cigar-case' AND 'Morley' IN (t1.city, t3.city)) OR
(t3.item='cigar-case' AND 'Morley' IN (t2.city, t4.city)) OR
(t4.item='cigar-case' AND 'Morley' IN (t3.city, t5.city)) OR
(t5.item='cigar-case' AND t4.city='Morley')
)
-- Рядом с дамой с бриллиантом сидит дама из Дануолл
AND
(
(t1.item='diamond' AND t2.city='Danuol') OR
(t2.item='diamond' AND 'Danuol' IN (t1.city, t3.city)) OR
(t3.item='diamond' AND 'Danuol' IN (t2.city, t4.city)) OR
(t4.item='diamond' AND 'Danuol' IN (t3.city, t5.city)) OR
(t5.item='diamond' AND t4.city='Danuol')
)
-- Рядом с дамой из Дануолла другая дама пила коктейль
AND
(
(t1.drink='coctail' AND t2.city='Danuol') OR
(t2.drink='coctail' AND 'Danuol' IN (t1.city, t3.city)) OR
(t3.drink='coctail' AND 'Danuol' IN (t2.city, t4.city)) OR
(t4.drink='coctail' AND 'Danuol' IN (t3.city, t5.city)) OR
(t5.drink='coctail' AND t4.city='Danuol')
);
Решение головоломки
В итоге мы получим:
+----------+---------+--------+------------+---------+------+---------+-------+-------+---------+
| name | item | name | item | name | item | name | item | name | item |
+----------+---------+--------+------------+---------+------+---------+-------+-------+---------+
| Marcolla | diamond | Contee | cigar-case | Winslow | ring | Natsiou | order | Finch | coulomb |
+----------+---------+--------+------------+---------+------+---------+-------+-------+---------+
1 row in set (0,00 sec)
Более того, мы решили головоломку даже сильнее, чем требовалось. Если заменить первую строку последнего запроса на это:
SELECT t1.*, t2.*, t3.*, t4.*, t5.* FROM s t1
то мы получим полную информацию о каждой из дам: позицию в ряду, принадлежащую ей драгоценность, её город, напиток и цвет платья.
WITH s(pos, name, item, color, drink, city) AS
(
SELECT pos, name, item, color, drink, city FROM Positions, Names, Colors, Drinks, Cities, Items
WHERE
((name='Winslow' AND color = 'blue') OR (name!='Winslow' AND color != 'blue'))
AND
((name='Marcolla' AND pos = 1) OR (name!='Marcolla' AND pos != 1))
AND
((color='white' AND pos = 2) OR (color!='white' AND pos != 2))
AND
((color='red' AND drink = 'whiskey') OR (color!='red' AND drink != 'whiskey'))
AND
((city='Morley' AND color = 'green') OR (city!='Morley' AND color != 'green'))
AND
((name='Finch' AND item = 'coulomb') OR (name!='Finch' AND item != 'coulomb'))
AND
((city='Freiport' AND item = 'ring') OR (city!='Freiport' AND item != 'ring'))
AND
((name='Contee' AND drink = 'absent') OR (name!='Contee' AND drink != 'absent'))
AND
((city='Serkonos' AND drink = 'cider') OR (city!='Serkonos' AND drink != 'cider'))
AND
((pos=3 AND drink = 'rum') OR (pos!=3 AND drink != 'rum'))
AND
((name='Natsiou' AND city = 'Bailton') OR (name!='Natsiou' AND city != 'Bailton'))
)
SELECT t1.name, t1.item, t2.name, t2.item, t3.name, t3.item, t4.name, t4.item, t5.name, t5.item
FROM s t1
JOIN s t2 ON t2.name != t1.name AND t2.item != t1.item AND t2.color != t1.color AND t2.drink != t1.drink AND t2.city != t1.city
JOIN s t3 ON t3.name NOT IN (t1.name, t2.name)
AND t3.item NOT IN (t1.item, t2.item)
AND t3.color NOT IN (t1.color, t2.color)
AND t3.drink NOT IN (t1.drink, t2.drink)
AND t3.city NOT IN (t1.city, t2.city)
JOIN s t4 ON t4.name NOT IN (t1.name, t2.name, t3.name)
AND t4.item NOT IN (t1.item, t2.item, t3.item)
AND t4.color NOT IN (t1.color, t2.color, t3.color)
AND t4.drink NOT IN (t1.drink, t2.drink, t3.drink)
AND t4.city NOT IN (t1.city, t2.city, t3.city)
JOIN s t5 ON t5.name NOT IN (t1.name, t2.name, t3.name, t4.name)
AND t5.item NOT IN (t1.item, t2.item, t3.item, t4.item)
AND t5.color NOT IN (t1.color, t2.color, t3.color, t4.color)
AND t5.drink NOT IN (t1.drink, t2.drink, t3.drink, t4.drink)
AND t5.city NOT IN (t1.city, t2.city, t3.city, t4.city)
WHERE
-- Мы хотим вывести дам в том порядке, в котором они сидели
t1.pos = 1 AND t2.pos=2 AND t3.pos = 3 AND t4.pos=4 AND t5.pos=5
-- Дама в красном сидит левее дамы в пурпурном, но место 2 занято дамой в белом, поэтому остаются места 3 и 4
AND (
(t3.color='red' AND t4.color='purple' ) OR (t4.color='red' AND t5.color='purple')
)
-- Рядом с дамой с портсигаром сидит дама из Морли
AND
(
(t1.item='cigar-case' AND t2.city='Morley') OR
(t2.item='cigar-case' AND 'Morley' IN (t1.city, t3.city)) OR
(t3.item='cigar-case' AND 'Morley' IN (t2.city, t4.city)) OR
(t4.item='cigar-case' AND 'Morley' IN (t3.city, t5.city)) OR
(t5.item='cigar-case' AND t4.city='Morley')
)
-- Рядом с дамой с бриллиантом сидит дама из Дануолл
AND
(
(t1.item='diamond' AND t2.city='Danuol') OR
(t2.item='diamond' AND 'Danuol' IN (t1.city, t3.city)) OR
(t3.item='diamond' AND 'Danuol' IN (t2.city, t4.city)) OR
(t4.item='diamond' AND 'Danuol' IN (t3.city, t5.city)) OR
(t5.item='diamond' AND t4.city='Danuol')
)
-- Рядом с дамой из Дануолла другая дама пила коктейль
AND
(
(t1.drink='coctail' AND t2.city='Danuol') OR
(t2.drink='coctail' AND 'Danuol' IN (t1.city, t3.city)) OR
(t3.drink='coctail' AND 'Danuol' IN (t2.city, t4.city)) OR
(t4.drink='coctail' AND 'Danuol' IN (t3.city, t5.city)) OR
(t5.drink='coctail' AND t4.city='Danuol')
);
Но он отработал бы за несколько суток. Видимо, планировщик в MySQL недостаточно умён, чтобы самостоятельно создать временную таблицу с которой всё отработало бы моментально. Поэтому этот подход в MySQL бесполезен. В PostgreSQL он отработает быстро.
drop database if exists dis2;
create database dis2;
use dis2;
-- Имена дам
create table Names (name char(10)) ENGINE=MEMORY;
insert into Names values ('Winslow'), ('Marcolla'), ('Contee'), ('Natsiou'), ('Finch');
-- Позиции дам за столом
create table Positions (pos int) ENGINE=MEMORY;
insert into Positions values (1), (2), (3), (4), (5);
-- Цвета платьев
create table Colors (color char(10)) ENGINE=MEMORY;
insert into Colors values ('red'), ('white'), ('purple'), ('blue'), ('green');
-- Родные города дам
create table Cities (city char(10)) ENGINE=MEMORY;
insert into Cities values ('Bailton'), ('Serkonos'), ('Freiport'), ('Morley'), ('Danuol');
-- Напитки дам
create table Drinks (drink char(10)) ENGINE=MEMORY;
insert into Drinks values ('absent'), ('coctail'), ('rum'), ('cider'), ('whiskey');
-- Ценности
create table Items (item char(10)) ENGINE=MEMORY;
insert into Items values ('ring'), ('diamond'), ('order'), ('cigar-case'), ('coulomb');
-- Таблица предварительных вариантов для просеивания
create table s (pos int, name char(10), item char(10), color char(10), drink char(10), city char(10)) ENGINE=MEMORY;
INSERT INTO s
SELECT pos, name, item, color, drink, city FROM Positions, Names, Colors, Drinks, Cities, Items
WHERE
((name='Winslow' AND color = 'blue') OR (name!='Winslow' AND color != 'blue'))
AND
((name='Marcolla' AND pos = 1) OR (name!='Marcolla' AND pos != 1))
AND
((color='white' AND pos = 2) OR (color!='white' AND pos != 2))
AND
((color='red' AND drink = 'whiskey') OR (color!='red' AND drink != 'whiskey'))
AND
((city='Morley' AND color = 'green') OR (city!='Morley' AND color != 'green'))
AND
((name='Finch' AND item = 'coulomb') OR (name!='Finch' AND item != 'coulomb'))
AND
((city='Freiport' AND item = 'ring') OR (city!='Freiport' AND item != 'ring'))
AND
((name='Contee' AND drink = 'absent') OR (name!='Contee' AND drink != 'absent'))
AND
((city='Serkonos' AND drink = 'cider') OR (city!='Serkonos' AND drink != 'cider'))
AND
((pos=3 AND drink = 'rum') OR (pos!=3 AND drink != 'rum'))
AND
((name='Natsiou' AND city = 'Bailton') OR (name!='Natsiou' AND city != 'Bailton'));
SELECT t1.name, t1.item, t2.name, t2.item, t3.name, t3.item, t4.name, t4.item, t5.name, t5.item
FROM s t1
JOIN s t2 ON t2.name != t1.name AND t2.item != t1.item AND t2.color != t1.color AND t2.drink != t1.drink AND t2.city != t1.city
JOIN s t3 ON t3.name NOT IN (t1.name, t2.name)
AND t3.item NOT IN (t1.item, t2.item)
AND t3.color NOT IN (t1.color, t2.color)
AND t3.drink NOT IN (t1.drink, t2.drink)
AND t3.city NOT IN (t1.city, t2.city)
JOIN s t4 ON t4.name NOT IN (t1.name, t2.name, t3.name)
AND t4.item NOT IN (t1.item, t2.item, t3.item)
AND t4.color NOT IN (t1.color, t2.color, t3.color)
AND t4.drink NOT IN (t1.drink, t2.drink, t3.drink)
AND t4.city NOT IN (t1.city, t2.city, t3.city)
JOIN s t5 ON t5.name NOT IN (t1.name, t2.name, t3.name, t4.name)
AND t5.item NOT IN (t1.item, t2.item, t3.item, t4.item)
AND t5.color NOT IN (t1.color, t2.color, t3.color, t4.color)
AND t5.drink NOT IN (t1.drink, t2.drink, t3.drink, t4.drink)
AND t5.city NOT IN (t1.city, t2.city, t3.city, t4.city)
WHERE
-- Мы хотим вывести дам в том порядке, в котором они сидели
t1.pos = 1 AND t2.pos=2 AND t3.pos = 3 AND t4.pos=4 AND t5.pos=5
-- Дама в красном сидит левее дамы в пурпурном, но место 2 занято дамой в белом, поэтому остаются места 3 и 4
AND (
(t3.color='red' AND t4.color='purple' ) OR (t4.color='red' AND t5.color='purple')
)
-- Рядом с дамой с портсигаром сидит дама из Морли
AND
(
(t1.item='cigar-case' AND t2.city='Morley') OR
(t2.item='cigar-case' AND 'Morley' IN (t1.city, t3.city)) OR
(t3.item='cigar-case' AND 'Morley' IN (t2.city, t4.city)) OR
(t4.item='cigar-case' AND 'Morley' IN (t3.city, t5.city)) OR
(t5.item='cigar-case' AND t4.city='Morley')
)
-- Рядом с дамой с бриллиантом сидит дама из Дануолл
AND
(
(t1.item='diamond' AND t2.city='Danuol') OR
(t2.item='diamond' AND 'Danuol' IN (t1.city, t3.city)) OR
(t3.item='diamond' AND 'Danuol' IN (t2.city, t4.city)) OR
(t4.item='diamond' AND 'Danuol' IN (t3.city, t5.city)) OR
(t5.item='diamond' AND t4.city='Danuol')
)
-- Рядом с дамой из Дануолла другая дама пила коктейль
AND
(
(t1.drink='coctail' AND t2.city='Danuol') OR
(t2.drink='coctail' AND 'Danuol' IN (t1.city, t3.city)) OR
(t3.drink='coctail' AND 'Danuol' IN (t2.city, t4.city)) OR
(t4.drink='coctail' AND 'Danuol' IN (t3.city, t5.city)) OR
(t5.drink='coctail' AND t4.city='Danuol')
);
Запросы для PostgreSQL в онлайн-редакторе с возможностью теста
ИТОГИ
Полученный запрос не назовёшь кратким (как и задачу), но он решает проблему. Я уверен, что другие читатели смогут в комментариях предложить более короткие решения. Возможно, существенно более короткое решение есть для PostgreSQL, которая богата разными функциями.
Но, тем не менее, мы практически человеческим языком описали условия из задачи в SQL-запросы и получили правильный результат.
Использованный подход по самосоединению таблиц под разными псевдонимами, а потом с сужением области результатов условиями, позволяет эффективно решать различные переборные задачи.
© 2024 ООО «МТ ФИНАНС»
Telegram-канал со скидками, розыгрышами призов и новостями IT ?
![](https://habrastorage.org/webt/7u/o0/_9/7uo0_9itb0bkl_y8_0_n1a57vuc.jpeg)
Комментарии (15)
firstmixon
10.09.2024 13:15Это старая задача, и уже описывалась, там вопрос кто живет в доме(цветном), не помню в каком, тут же на сайте было ее решение при помощи SQL
задача Эйнштейна
http://akmych.org/various/einstein.html
artptr86
10.09.2024 13:15В статье https://dkalemis.wordpress.com/2014/08/23/using-sql-server-to-solve-einsteins-puzzles/ использован другой подход: создаётся временная таблица со всеми возможными комбинациями, а затем последовательно удаляются все неподходящие под условия задачи строки. В результате остаются только строки, соответствующие решению.
inetstar Автор
10.09.2024 13:15+1В общем случае, это плохой подход, так как вариантов может быть настолько много, что не хватит всех жёстких дисков мира, чтобы создать все комбинации.
И этот вариант головоломки Эйнштейна не включает относительное местоположение, что заметно упрощает её, в сравнении с задачей Джиндоша.artptr86
10.09.2024 13:15Обычно задача формулируется так, что получается матрица n*n, то есть возможно n^n комбинаций. Для задачи про 5 участников с 5 атрибутами для каждого получается 5^5=3125 комбинаций, для 6^6=46656 комбинаций. Уже задача 10x10 даёт 10 млрд комбинаций, что, впрочем, по силам для хранения в БД на диске.
А неявный джойн с ограничениями будет решать задачу эффективнее?
inetstar Автор
10.09.2024 13:15С помощью ограничений мы сжимаем задачу всего лишь до 80 вариантов, что есть в статье.
Без этого можно столкнуться с тем, что таблицу с 5^5 строк нам придётся джойнить саму к себе, что даст гораздо больше вариантов, а именно (5^5=3125)^5, что сильно меньше, чем 80^5.
А без этого второго джойна будет трудно обработать условия относительного местоположения.
В похожей задачке человек обошёлся одним мегаджойном, который без учёта условий тоже даёт (5^5)^5 строк. Я значительно облегчил работу планировщику запросов, а он отдал всю оптимизацию на откуп планировщику. SQL Server справился (не знаю за какое время), MySQL сделал это по моей технике за время меньшее миллисекунды.
А явный или неявный джойн - это значения не имеет.
HardWrMan
10.09.2024 13:15Обычно задача формулируется так, что получается матрица n*n, то есть возможно n^n комбинаций.
Так вроде вариантов сильно меньше же. Ведь все атрибуты должны быть использованы и каждый только 1 раз, а результат - лишь их порядок (каждому обладателю атрибута присвоим порядковый номер). А значит это обычный факториал. Для 5 атрибутов "всего" 120 вариантов.
Suoriks
ChatGPT решает эту задачку с легкостью, но решение на SQL конечно интересное
inetstar Автор
Можете прислать как конкретно ответила нейросеть?
Я задал эту загадку Copilot (bing.com) и получил неверный ответ:
gotch
Это ответ ChatGPT, честно говоря я его не понимаю )
inetstar Автор
Ответ верный, но в рассуждениях есть ошибки.
Нет. Это значит только, что рядом с дамой с портсигаром сидела дама из Морли.
Это подтверждает, что она из Морли. Если это условие выкинуть вообще, так как, в теории, путешественница могла посещать вообще что угодно, то есть 7 вариантов решения задачи.
Скрытый текст
Рассуждения сомнительные, однако ответ верный.
alhimik45
Возможно эта задача просто была в обучающей выборке, так как её на каких-нибудь игровых форумах разжёвывали
inetstar Автор
Да, её разжёвывали множество раз в сети.
gotch
Да это как раз то, что привело меня в замешательство, очевидно неверные выводы и правильное общее решение.