Решение рекурсивной логической головоломки на Oracle SQL

Однажды в своем блоге коллега разместил картинку:


Вспомнив про статью Задача о восьми Ферзях на Oracle SQL, решил попробовать решить ее аналогичным путем.

Сначала описываю исходное декартово произведение всех возможных ответов:

  (select level a from dual connect by level <= 5) q1,
  (select level a from dual connect by level <= 5) q2,
  (select level a from dual connect by level <= 5) q3,
  (select level a from dual connect by level <= 5) q4,
  (select level a from dual connect by level <= 5) q5,
  (select level a from dual connect by level <= 5) q6,
  (select level a from dual connect by level <= 5) q7,
  (select level a from dual connect by level <= 5) q8,
  (select level a from dual connect by level <= 5) q9,
  (select level a from dual connect by level <= 5) q10,
  (select level a from dual connect by level <= 5) q11,
  (select level a from dual connect by level <= 5) q12,
  (select level a from dual connect by level <= 5) q13,
  (select level a from dual connect by level <= 5) q14,
  (select level a from dual connect by level <= 5) q15,
  (select level a from dual connect by level <= 5) q16,
  (select level a from dual connect by level <= 5) q17,
  (select level a from dual connect by level <= 5) q18,
  (select level a from dual connect by level <= 5) q19,
  (select level a from dual connect by level <= 5) q20

Затем для удобства переименовываю ответы по номерам a1..a20 и подсчитываю количества вариантов ответов, которые необходимы для некоторых условий — количество ответов “A” (1), количество ответов “B” с первого по десятый вопрос, количество ответов “B” всего, и так далее:

select 
       q1.a    a1,
       q2.a    a2,
       q3.a    a3,
       q4.a    a4,
       q5.a    a5,
       q6.a    a6,
       q7.a    a7,
       q8.a    a8,
       q9.a    a9,
       q10.a   a10,
       q11.a   a11,
       q12.a   a12,
       q13.a   a13,
       q14.a   a14,
       q15.a   a15,
       q16.a   a16,
       q17.a   a17,
       q18.a   a18,
       q19.a   a19,
       q20.a   a20,
       case q1.a when 1 then 1 else 0 end +
       case q2.a when 1 then 1 else 0 end +
       case q3.a when 1 then 1 else 0 end +
       case q4.a when 1 then 1 else 0 end +
       case q5.a when 1 then 1 else 0 end +
       case q6.a when 1 then 1 else 0 end +
       case q7.a when 1 then 1 else 0 end +
       case q8.a when 1 then 1 else 0 end +
       case q9.a when 1 then 1 else 0 end +
       case q10.a when 1 then 1 else 0 end +
       case q11.a when 1 then 1 else 0 end +
       case q12.a when 1 then 1 else 0 end +
       case q13.a when 1 then 1 else 0 end +
       case q14.a when 1 then 1 else 0 end +
       case q15.a when 1 then 1 else 0 end +
       case q16.a when 1 then 1 else 0 end +
       case q17.a when 1 then 1 else 0 end +
       case q18.a when 1 then 1 else 0 end +
       case q19.a when 1 then 1 else 0 end +
       case q20.a when 1 then 1 else 0 end a_count,
       case q1.a when 2 then 1 else 0 end +
       case q2.a when 2 then 1 else 0 end +
       case q3.a when 2 then 1 else 0 end +
       case q4.a when 2 then 1 else 0 end +
       case q5.a when 2 then 1 else 0 end +
       case q6.a when 2 then 1 else 0 end +
       case q7.a when 2 then 1 else 0 end +
       case q8.a when 2 then 1 else 0 end +
       case q9.a when 2 then 1 else 0 end +
       case q10.a when 2 then 1 else 0 end b_count10,
       case q1.a when 2 then 1 else 0 end +
       case q2.a when 2 then 1 else 0 end +
       case q3.a when 2 then 1 else 0 end +
       case q4.a when 2 then 1 else 0 end +
       case q5.a when 2 then 1 else 0 end +
       case q6.a when 2 then 1 else 0 end +
       case q7.a when 2 then 1 else 0 end +
       case q8.a when 2 then 1 else 0 end +
       case q9.a when 2 then 1 else 0 end +
       case q10.a when 2 then 1 else 0 end +
       case q11.a when 2 then 1 else 0 end +
       case q12.a when 2 then 1 else 0 end +
       case q13.a when 2 then 1 else 0 end +
       case q14.a when 2 then 1 else 0 end +
       case q15.a when 2 then 1 else 0 end +
       case q16.a when 2 then 1 else 0 end +
       case q17.a when 2 then 1 else 0 end +
       case q18.a when 2 then 1 else 0 end +
       case q19.a when 2 then 1 else 0 end +
       case q20.a when 2 then 1 else 0 end b_count,
       case q1.a when 3 then 1 else 0 end +
       case q2.a when 3 then 1 else 0 end +
       case q3.a when 3 then 1 else 0 end +
       case q4.a when 3 then 1 else 0 end +
       case q5.a when 3 then 1 else 0 end +
       case q6.a when 3 then 1 else 0 end +
       case q7.a when 3 then 1 else 0 end +
       case q8.a when 3 then 1 else 0 end +
       case q9.a when 3 then 1 else 0 end +
       case q10.a when 3 then 1 else 0 end +
       case q11.a when 3 then 1 else 0 end +
       case q12.a when 3 then 1 else 0 end +
       case q13.a when 3 then 1 else 0 end +
       case q14.a when 3 then 1 else 0 end +
       case q15.a when 3 then 1 else 0 end +
       case q16.a when 3 then 1 else 0 end +
       case q17.a when 3 then 1 else 0 end +
       case q18.a when 3 then 1 else 0 end +
       case q19.a when 3 then 1 else 0 end +
       case q20.a when 3 then 1 else 0 end c_count,
       case q1.a when 4 then 1 else 0 end +
       case q2.a when 4 then 1 else 0 end +
       case q3.a when 4 then 1 else 0 end +
       case q4.a when 4 then 1 else 0 end +
       case q5.a when 4 then 1 else 0 end +
       case q6.a when 4 then 1 else 0 end +
       case q7.a when 4 then 1 else 0 end +
       case q8.a when 4 then 1 else 0 end +
       case q9.a when 4 then 1 else 0 end +
       case q10.a when 4 then 1 else 0 end +
       case q11.a when 4 then 1 else 0 end +
       case q12.a when 4 then 1 else 0 end +
       case q13.a when 4 then 1 else 0 end +
       case q14.a when 4 then 1 else 0 end +
       case q15.a when 4 then 1 else 0 end +
       case q16.a when 4 then 1 else 0 end +
       case q17.a when 4 then 1 else 0 end +
       case q18.a when 4 then 1 else 0 end +
       case q19.a when 4 then 1 else 0 end +
       case q20.a when 4 then 1 else 0 end d_count,
       case q1.a when 5 then 1 else 0 end +
       case q2.a when 5 then 1 else 0 end +
       case q3.a when 5 then 1 else 0 end +
       case q4.a when 5 then 1 else 0 end +
       case q5.a when 5 then 1 else 0 end +
       case q6.a when 5 then 1 else 0 end +
       case q7.a when 5 then 1 else 0 end +
       case q8.a when 5 then 1 else 0 end +
       case q9.a when 5 then 1 else 0 end +
       case q10.a when 5 then 1 else 0 end +
       case q11.a when 5 then 1 else 0 end +
       case q12.a when 5 then 1 else 0 end +
       case q13.a when 5 then 1 else 0 end +
       case q14.a when 5 then 1 else 0 end +
       case q15.a when 5 then 1 else 0 end +
       case q16.a when 5 then 1 else 0 end +
       case q17.a when 5 then 1 else 0 end +
       case q18.a when 5 then 1 else 0 end +
       case q19.a when 5 then 1 else 0 end +
       case q20.a when 5 then 1 else 0 end e_count
  from 
  (select level a from dual connect by level <= 5) q1,
  (select level a from dual connect by level <= 5) q2,
  (select level a from dual connect by level <= 5) q3,
  (select level a from dual connect by level <= 5) q4,
  (select level a from dual connect by level <= 5) q5,
  (select level a from dual connect by level <= 5) q6,
  (select level a from dual connect by level <= 5) q7,
  (select level a from dual connect by level <= 5) q8,
  (select level a from dual connect by level <= 5) q9,
  (select level a from dual connect by level <= 5) q10,
  (select level a from dual connect by level <= 5) q11,
  (select level a from dual connect by level <= 5) q12,
  (select level a from dual connect by level <= 5) q13,
  (select level a from dual connect by level <= 5) q14,
  (select level a from dual connect by level <= 5) q15,
  (select level a from dual connect by level <= 5) q16,
  (select level a from dual connect by level <= 5) q17,
  (select level a from dual connect by level <= 5) q18,
  (select level a from dual connect by level <= 5) q19,
  (select level a from dual connect by level <= 5) q20

И, наконец, накладываю все условия и вывожу результат:

select a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20
from (select 
       q1.a    a1,
       q2.a    a2,
       q3.a    a3,
       q4.a    a4,
       q5.a    a5,
       q6.a    a6,
       q7.a    a7,
       q8.a    a8,
       q9.a    a9,
       q10.a   a10,
       q11.a   a11,
       q12.a   a12,
       q13.a   a13,
       q14.a   a14,
       q15.a   a15,
       q16.a   a16,
       q17.a   a17,
       q18.a   a18,
       q19.a   a19,
       q20.a   a20,
       case q1.a when 1 then 1 else 0 end +
       case q2.a when 1 then 1 else 0 end +
       case q3.a when 1 then 1 else 0 end +
       case q4.a when 1 then 1 else 0 end +
       case q5.a when 1 then 1 else 0 end +
       case q6.a when 1 then 1 else 0 end +
       case q7.a when 1 then 1 else 0 end +
       case q8.a when 1 then 1 else 0 end +
       case q9.a when 1 then 1 else 0 end +
       case q10.a when 1 then 1 else 0 end +
       case q11.a when 1 then 1 else 0 end +
       case q12.a when 1 then 1 else 0 end +
       case q13.a when 1 then 1 else 0 end +
       case q14.a when 1 then 1 else 0 end +
       case q15.a when 1 then 1 else 0 end +
       case q16.a when 1 then 1 else 0 end +
       case q17.a when 1 then 1 else 0 end +
       case q18.a when 1 then 1 else 0 end +
       case q19.a when 1 then 1 else 0 end +
       case q20.a when 1 then 1 else 0 end a_count,
       case q1.a when 2 then 1 else 0 end +
       case q2.a when 2 then 1 else 0 end +
       case q3.a when 2 then 1 else 0 end +
       case q4.a when 2 then 1 else 0 end +
       case q5.a when 2 then 1 else 0 end +
       case q6.a when 2 then 1 else 0 end +
       case q7.a when 2 then 1 else 0 end +
       case q8.a when 2 then 1 else 0 end +
       case q9.a when 2 then 1 else 0 end +
       case q10.a when 2 then 1 else 0 end b_count10,
       case q1.a when 2 then 1 else 0 end +
       case q2.a when 2 then 1 else 0 end +
       case q3.a when 2 then 1 else 0 end +
       case q4.a when 2 then 1 else 0 end +
       case q5.a when 2 then 1 else 0 end +
       case q6.a when 2 then 1 else 0 end +
       case q7.a when 2 then 1 else 0 end +
       case q8.a when 2 then 1 else 0 end +
       case q9.a when 2 then 1 else 0 end +
       case q10.a when 2 then 1 else 0 end +
       case q11.a when 2 then 1 else 0 end +
       case q12.a when 2 then 1 else 0 end +
       case q13.a when 2 then 1 else 0 end +
       case q14.a when 2 then 1 else 0 end +
       case q15.a when 2 then 1 else 0 end +
       case q16.a when 2 then 1 else 0 end +
       case q17.a when 2 then 1 else 0 end +
       case q18.a when 2 then 1 else 0 end +
       case q19.a when 2 then 1 else 0 end +
       case q20.a when 2 then 1 else 0 end b_count,
       case q1.a when 3 then 1 else 0 end +
       case q2.a when 3 then 1 else 0 end +
       case q3.a when 3 then 1 else 0 end +
       case q4.a when 3 then 1 else 0 end +
       case q5.a when 3 then 1 else 0 end +
       case q6.a when 3 then 1 else 0 end +
       case q7.a when 3 then 1 else 0 end +
       case q8.a when 3 then 1 else 0 end +
       case q9.a when 3 then 1 else 0 end +
       case q10.a when 3 then 1 else 0 end +
       case q11.a when 3 then 1 else 0 end +
       case q12.a when 3 then 1 else 0 end +
       case q13.a when 3 then 1 else 0 end +
       case q14.a when 3 then 1 else 0 end +
       case q15.a when 3 then 1 else 0 end +
       case q16.a when 3 then 1 else 0 end +
       case q17.a when 3 then 1 else 0 end +
       case q18.a when 3 then 1 else 0 end +
       case q19.a when 3 then 1 else 0 end +
       case q20.a when 3 then 1 else 0 end c_count,
       case q1.a when 4 then 1 else 0 end +
       case q2.a when 4 then 1 else 0 end +
       case q3.a when 4 then 1 else 0 end +
       case q4.a when 4 then 1 else 0 end +
       case q5.a when 4 then 1 else 0 end +
       case q6.a when 4 then 1 else 0 end +
       case q7.a when 4 then 1 else 0 end +
       case q8.a when 4 then 1 else 0 end +
       case q9.a when 4 then 1 else 0 end +
       case q10.a when 4 then 1 else 0 end +
       case q11.a when 4 then 1 else 0 end +
       case q12.a when 4 then 1 else 0 end +
       case q13.a when 4 then 1 else 0 end +
       case q14.a when 4 then 1 else 0 end +
       case q15.a when 4 then 1 else 0 end +
       case q16.a when 4 then 1 else 0 end +
       case q17.a when 4 then 1 else 0 end +
       case q18.a when 4 then 1 else 0 end +
       case q19.a when 4 then 1 else 0 end +
       case q20.a when 4 then 1 else 0 end d_count,
       case q1.a when 5 then 1 else 0 end +
       case q2.a when 5 then 1 else 0 end +
       case q3.a when 5 then 1 else 0 end +
       case q4.a when 5 then 1 else 0 end +
       case q5.a when 5 then 1 else 0 end +
       case q6.a when 5 then 1 else 0 end +
       case q7.a when 5 then 1 else 0 end +
       case q8.a when 5 then 1 else 0 end +
       case q9.a when 5 then 1 else 0 end +
       case q10.a when 5 then 1 else 0 end +
       case q11.a when 5 then 1 else 0 end +
       case q12.a when 5 then 1 else 0 end +
       case q13.a when 5 then 1 else 0 end +
       case q14.a when 5 then 1 else 0 end +
       case q15.a when 5 then 1 else 0 end +
       case q16.a when 5 then 1 else 0 end +
       case q17.a when 5 then 1 else 0 end +
       case q18.a when 5 then 1 else 0 end +
       case q19.a when 5 then 1 else 0 end +
       case q20.a when 5 then 1 else 0 end e_count
  from 
  (select level a from dual connect by level <= 5) q1,
  (select level a from dual connect by level <= 5) q2,
  (select level a from dual connect by level <= 5) q3,
  (select level a from dual connect by level <= 5) q4,
  (select level a from dual connect by level <= 5) q5,
  (select level a from dual connect by level <= 5) q6,
  (select level a from dual connect by level <= 5) q7,
  (select level a from dual connect by level <= 5) q8,
  (select level a from dual connect by level <= 5) q9,
  (select level a from dual connect by level <= 5) q10,
  (select level a from dual connect by level <= 5) q11,
  (select level a from dual connect by level <= 5) q12,
  (select level a from dual connect by level <= 5) q13,
  (select level a from dual connect by level <= 5) q14,
  (select level a from dual connect by level <= 5) q15,
  (select level a from dual connect by level <= 5) q16,
  (select level a from dual connect by level <= 5) q17,
  (select level a from dual connect by level <= 5) q18,
  (select level a from dual connect by level <= 5) q19,
  (select level a from dual connect by level <= 5) q20)
  where 
  -- q1 Первый вопрос, ответ на который B, это вопрос: 1; 2; 3; 4; 5
  ((a1=2 and a1=1) or 
   (a1!=2 and a2=2 and a1=2) or 
   (a1!=2 and a2!=2 and a3=2 and a1=3) or 
   (a1!=2 and a2!=2 and a3!=2 and a4=2 and a1=4) or 
   (a1!=2 and a2!=2 and a3!=2 and a4!=2 and a5=2 and a1=5)) 
  -- q2 Единственные два последовательных вопроса с одинаковыми ответами это: 6 и 7; 7 и 8; 8 и 9; 9 и 10; 10 и 11
  and ((a6=a7 and a2=1) or 
       (a7=a8 and a2=2) or 
       (a8=a9 and a2=3) or 
       (a9=a10 and a2=4) or 
       (a10=a11 and a2=5))
  and (a1!=a2 and a2!=a3 and a3!=a4 and a4!=a5 and a5!=a6 and 
       a11!=a12 and a12!=a13 and a13!=a14 and a14!=a15 and a15!=a16 and 
       a16!=a17 and a17!=a18 and a18!=a19 and a19!=a20)
  -- q3 Количество вопросов с ответом E: 0; 1; 2; 3; 4;
  and (a3 = e_count+1)
  -- q4 Количество вопросов с ответом A: 4; 5; 6; 7; 8;
  and (a4 = a_count-3)
  -- q5 ответ на этот вопрос такой же, как и ответ на вопрос: 1; 2; 3; 4; 5
  and ((a5=a1 and a5=1) or 
       (a5=a2 and a5=2) or 
       (a5=a3 and a5=3) or 
       (a5=a4 and a5=4) or 
       (a5=a5 and a5=5))
  -- q6 Ответ на вопрос 17: C; D; E; ничего из перечисленного; все перечисленное
  and ((a17=3 and a6=1) or 
       (a17=4 and a6=2) or 
       (a17=5 and a6=3) or 
       (a17 in (1, 2) and a6=4) or 
       (a17=3 and a17=4 and a17=5 and a6=5))
  -- q7 В алфавите ответ на этот вопрос и ответ на следующий вопрос: отстоят на 4 буквы; на 3 буквы; на 2 буквы; на 1 букву; одинаковые
  and ((abs(a7-a8)=4 and a7=1) or 
       (abs(a7-a8)=3 and a7=2) or 
       (abs(a7-a8)=2 and a7=3) or 
       (abs(a7-a8)=1 and a7=4) or 
       (a7=a8 and a7=5))
  -- q8 Количество вопросов, чьи ответы - гласные: 4; 5; 6; 7; 8
  and (a8 = a_count + e_count-3)
  -- q9 Следующий вопрос с таким же ответом, как этот: 10; 11; 12; 13; 14
  and ((a9=a10 and a9=1) or 
       (a9=a11 and a10!=a9 and a9=2) or 
       (a9=a12 and a10!=a9 and a11!=a9 and a9=3) or 
       (a9=a13 and a10!=a9 and a11!=a9 and a12!=a9 and a9=4) or 
       (a9=a14 and a10!=a9 and a11!=a9 and a12!=a9 and a13!=a9 and a9=5))
  -- q10 Ответ на вопрос 16: D; A; E; B; C
  and ((a16=4 and a10=1) or 
       (a16=1 and a10=2) or 
       (a16=5 and a10=3) or 
       (a16=2 and a10=4) or 
       (a16=3 and a10=5))
  -- q11 Количество вопросов, предшествующих этому, с ответом B: 0; 1; 2; 3; 4
  and (a11 = b_count10+1)
  -- q12 Количество вопросов, чьи ответы - согласные: четное число; нечетное число; полный квадрат; простое число; делится на 5
  and ((20-a_count-e_count in (2,4,6,8,10,12,14,16) and a12=1) or 
       (20-a_count-e_count in (1,3,5,7,9,11,13,15) and a12=2) or 
       (20-a_count-e_count in (1,4,9,16) and a12=3) or 
       (20-a_count-e_count in (1,2,3,5,7,11,13,17,19) and a12=4) or 
       (20-a_count-e_count in (5,10,15) and a12=5))
  -- q13 Единственный вопрос с нечетным номером, чей ответ A: 9; 11; 13; 15; 17
  and ((a9=1 and a11!=1 and a13!=1 and a15!=1 and a17!=1 and a13=1) or 
       (a9!=1 and a11=1 and a13!=1 and a15!=1 and a17!=1 and a13=2) or 
       (a9!=1 and a11!=1 and a13=1 and a15!=1 and a17!=1 and a13=3) or 
       (a9!=1 and a11!=1 and a13!=1 and a15=1 and a17!=1 and a13=4) or 
       (a9!=1 and a11!=1 and a13!=1 and a15!=1 and a17=1 and a13=5))
  and (a1!=1 and a3!=1 and a5!=1 and a7!=1 and a19!=1)
  -- q14 Количество вопросов с ответом D: 6; 7; 8; 9; 10
  and (a14 = d_count-5)
  -- q15 Ответ на вопрос 12: A; B; C; D; E
  and (a15 = a12)
  -- q16 Ответ на вопрос 10: D; C; B; A; E
  and ((a10=4 and a16=1) or 
       (a10=3 and a16=2) or 
       (a10=2 and a16=3) or 
       (a10=1 and a16=4) or 
       (a10=5 and a16=5))
  -- q17 Ответ на вопрос 6: C; D; E; ничего из перечисленного; все перечисленное
  and ((a6=3 and a17=1) or 
       (a6=4 and a17=2) or 
       (a6=5 and a17=3) or 
       (a6 in (1, 2) and a17=4) or 
       (a6=3 and a6=4 and a6=5 and a17=5))
  -- q18 Количество вопросов с ответом A равняется количеству вопросов с ответом: B; C; D; E; ничего из перечисленного
  and ((a_count=b_count and a18=1) or 
       (a_count=c_count and a18=2) or 
       (a_count=d_count and a18=3) or 
       (a_count=e_count and a18=4) or 
       (a_count!=b_count and a_count!=c_count and a_count!=d_count and a_count!=e_count and a18=5))
  -- q19 Ответ на этот вопрос: A; B; C; D; E
  -- q20 Стандартизованный тест относится к интеллигентности как барометр к: температуре (только); скорости ветра (только); широте (только); долготе (только); все перечисленное

На вопрос 19 условий накладывать не требуется, а на 20 я не решился, так как вопрос несколько философский. В итоге получается четыре варианта ответа:

A1	A2	A3	A4	A5	A6	A7	A8	A9	A10	A11	A12	A13	A14	A15	A16	A17	A18	A19	A20
4	1	4	2	5	4	4	5	4	1	2	1	4	2	1	4	2	1	2	5
4	1	4	2	5	4	4	5	4	1	2	1	4	2	1	4	2	1	5	2
4	1	4	2	5	4	4	5	4	1	2	1	4	3	1	4	2	5	4	1
4	1	4	2	5	4	4	5	4	1	2	1	4	2	1	4	2	5	3	1

Если предположить, что на 20 вопрос “наиболее правильный” ответ “E” (5), то ответом на всю задачу является первая строка.

Выполнение запроса вместе с разбором и построением плана занимает 15..20 с. Повторное выполнение по уже имеющемуся плану — около 3 с.
Если посмотреть на план запроса, то видно, что выполняется не полный (5^20 вариантов), а оптимизированный перебор; по мере добавления переменных к ним сразу применяются ограничивающие условия, многократно ограничивая количество перебираемых вариантов.

Как показал мой опыт, решение подобной задачи на SQL оказалось проще, чем на императивном языке — достаточно было просто описать ограничения, накладываемые на множество вариантов. Оптимизацию Oracle провел самостоятельно, и вполне успешно.