Solving a recursive logic puzzle in Oracle SQL

Once a colleague posted a picture on his blog:


Recalling the eight-queens problem article 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 the numbers a1..a20 and count the number of response options that are necessary for some conditions - the number of answers “A” (1), the number of answers “B” from the first to the tenth question, the number of answers “B” total, and so on:

 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 conditions and deduce 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        :  ();   ();  ();  ();   

There is no need to impose conditions on question 19, but I did not dare at 20, 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
four	one	four	2	five	four	four	five	four	one	2	one	four	2	one	four	2	one	2	five
four	one	four	2	five	four	four	five	four	one	2	one	four	2	one	four	2	one	five	2
four	one	four	2	five	four	four	five	four	one	2	one	four	3	one	four	2	five	four	one
four	one	four	2	five	four	four	five	four	one	2	one	four	2	one	four	2	five	3	one

If we assume that the answer to question 20 is the “most correct” answer “E” (5), then the answer to the entire problem is the first line.

Fulfillment of a request along with analysis and construction of a plan takes 15..20 s. Repeated execution according to the already existing plan - about 3 seconds.
If you look at the query plan, you can see that not full (5 ^ 20 variants) is being executed, but optimized brute force; as variables are added, restrictive conditions are immediately applied to them, repeatedly limiting the number of enumerated variants.
')
As my experience has shown, solving a similar problem in SQL turned out to be simpler than in an imperative language - it was enough just to describe the limitations imposed on many options. Oracle has carried out optimization independently, and quite successfully.