Recursive Logic Puzzle Solution in Oracle SQL
Once on a blog a colleague posted a picture:
Remembering about the article The Problem of the Eight Queens on Oracle SQL , I decided to try to solve it in a similar way.
First, I describe the original Cartesian product of all possible answers:
Then, for convenience, I rename the answers by numbers a1..a20 and count the number of answer options that are necessary for some conditions - the number of answers “A” (1), the number of answers “B” from the first to tenth questions, the number of answers “B” in total, etc:
And finally, I impose all the conditions and print the result:
It is not necessary to impose conditions on question 19, but on 20 I did not dare, since the question is somewhat philosophical. The result is four possible answers:
If we assume that the “most correct” answer is “E” (5) to question 20, then the answer to the whole problem is the first line.
Fulfillment of the request together with analysis and construction of the plan takes 15..20 s. Repeated execution according to the existing plan - about 3 s.
If you look at the query plan, you can see that it is not complete (5 ^ 20 options), but optimized enumeration; as variables are added to them, restrictive conditions are immediately applied to them, repeatedly limiting the number of options being searched.
As my experience has shown, solving such a problem in SQL turned out to be simpler than in an imperative language - it was enough to simply describe the restrictions imposed on many options. Oracle conducted the optimization on its own, and quite successfully.
Remembering about the article The Problem of the Eight Queens on Oracle SQL , I decided to try to solve it in a similar way.
First, I describe the original Cartesian product of all possible answers:
(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
Then, for convenience, I rename the answers by numbers a1..a20 and count the number of answer options that are necessary for some conditions - the number of answers “A” (1), the number of answers “B” from the first to tenth questions, the number of answers “B” in total, etc:
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
And finally, I impose all the conditions and print the result:
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 Стандартизованный тест относится к интеллигентности как барометр к: температуре (только); скорости ветра (только); широте (только); долготе (только); все перечисленное
It is not necessary to impose conditions on question 19, but on 20 I did not dare, since the question is somewhat philosophical. The result is four possible answers:
| 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 |
If we assume that the “most correct” answer is “E” (5) to question 20, then the answer to the whole problem is the first line.
Fulfillment of the request together with analysis and construction of the plan takes 15..20 s. Repeated execution according to the existing plan - about 3 s.
If you look at the query plan, you can see that it is not complete (5 ^ 20 options), but optimized enumeration; as variables are added to them, restrictive conditions are immediately applied to them, repeatedly limiting the number of options being searched.
As my experience has shown, solving such a problem in SQL turned out to be simpler than in an imperative language - it was enough to simply describe the restrictions imposed on many options. Oracle conducted the optimization on its own, and quite successfully.