📜 ⬆️ ⬇️

The eight queen problem on Oracle SQL (another solution)

In response to this decision , I would like to indicate my own, which is somewhat simpler for perception.

As well as the author, I initially made a selection of all possible combinations of queens' positions:

select * from (select level as A from Dual connect by level<=8) A cross join (select level as B from Dual connect by level<=8) B cross join (select level as C from Dual connect by level<=8) C cross join (select level as D from Dual connect by level<=8) D cross join (select level as E from Dual connect by level<=8) E cross join (select level as F from Dual connect by level<=8) F cross join (select level as G from Dual connect by level<=8) G cross join (select level as H from Dual connect by level<=8) H; 


But then I decided to move a little more simple method. Having formed an array by this method, we, yes, got boards, where there is one queen in each vertical. Accordingly, it is necessary to filter only the horizontal and diagonal. And here I decided to use the construction not x in (y,z) . For horizontals, everything is simple:
')
 where not A in (B,C,D,E,F,G,H) and not B in (A,C,D,E,F,G,H) ... and not H in (A,B,C,D,E,F,G) 


This construction can also be reduced, since not A in (B) = not B in (A) , etc., we obtain:

 where not A in (B,C,D,E,F,G,H) and not B in (C,D,E,F,G,H) ... and not G in (H) 


Minus one line, and generally half as many comparisons.

Further, the diagonals are the same method, taking into account the line shift:

 where not A in (B+1,C+2,D+3,E+4,F+5,G+6,H+7) and not B in (A-1,C+1,D+2,E+3,F+4,G+5,H+6) ... and not H in (A-7,B-6,C-5,D-4,E-3,F-2,G-1) 


And also, because not A in (B+1) = not B in (A-1) remove unnecessary comparisons:

 where not A in (B+1,C+2,D+3,E+4,F+5,G+6,H+7) and not B in (C+1,D+2,E+3,F+4,G+5,H+6) ... and not G in (H+1) 


To filter out the second diagonal, simply duplicate the code of the first diagonal with a complete replacement of the sign with the opposite one:

 where not A in (B-1,C-2,D-3,E-4,F-5,G-6,H-7) and not B in (C-1,D-2,E-3,F-4,G-5,H-6) ... and not G in (H-1) 


Thus, we obtained three sets of conditions that must be met to solve the problem.

So that everything looks optimal and without zatroeniya in where I grouped all the conditions:

 where not A in (B,C,D,E,F,G,H,B+1,C+2,D+3,E+4,F+5,G+6,H+7,B-1,C-2,D-3,E-4,F-5,G-6,H-7) and not B in (C,D,E,F,G,H,C+1,D+2,E+3,F+4,G+5,H+6,C-1,D-2,E-3,F-4,G-5,H-6) and not C in (D,E,F,G,H,D+1,E+2,F+3,G+4,H+5,D-1,E-2,F-3,G-4,H-5) and not D in (E,F,G,H,E+1,F+2,G+3,H+4,E-1,F-2,G-3,H-4) and not E in (F,G,H,F+1,G+2,H+3,F-1,G-2,H-3) and not F in (G,H,G+1,H+2,G-1,H-2) and not G in (H,H+1,H-1) 


And in the end, we format the output according to the requirements in the condition and add sorting so that the answer looks decent:

 select 'a' || AA, 'b' || BB, 'c' || CC, 'd' || DD, 'e' || EE, 'f' || FF, 'g' || GG, 'h' || HH from (select level as A from Dual connect by level<=8) A cross join (select level as B from Dual connect by level<=8) B cross join (select level as C from Dual connect by level<=8) C cross join (select level as D from Dual connect by level<=8) D cross join (select level as E from Dual connect by level<=8) E cross join (select level as F from Dual connect by level<=8) F cross join (select level as G from Dual connect by level<=8) G cross join (select level as H from Dual connect by level<=8) H where not A in (B,C,D,E,F,G,H,B+1,C+2,D+3,E+4,F+5,G+6,H+7,B-1,C-2,D-3,E-4,F-5,G-6,H-7) and not B in (C,D,E,F,G,H,C+1,D+2,E+3,F+4,G+5,H+6,C-1,D-2,E-3,F-4,G-5,H-6) and not C in (D,E,F,G,H,D+1,E+2,F+3,G+4,H+5,D-1,E-2,F-3,G-4,H-5) and not D in (E,F,G,H,E+1,F+2,G+3,H+4,E-1,F-2,G-3,H-4) and not E in (F,G,H,F+1,G+2,H+3,F-1,G-2,H-3) and not F in (G,H,G+1,H+2,G-1,H-2) and not G in (H,H+1,H-1) order by A, B, C, D, E, F, G, H; 


PS It is a pity that I did not participate in this competition.

PPS The decision was made after reading the conditions of the problem, before writing his own to the author did not peep.

Source: https://habr.com/ru/post/228373/


All Articles