Решаем загадку Джиндоша из Dishonored 2 на SQL перебором с возвратом

+------+----------+------------+--------+---------+----------+
| 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'));

В MySQL, начиная с версии 8, поддерживается SQL-оператор WITH. Мы могли бы сделать такой запрос-монстр:

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')
 );