Das Acht-Königinnen-Problem unter Oracle SQL (eine andere Lösung)

Als Antwort auf diese Entscheidung möchte ich meine eigene angeben, die etwas einfacher wahrzunehmen ist.

Wie der Autor habe ich zunächst eine Auswahl aller möglichen Kombinationen von Königinnen getroffen:

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;


Aber dann habe ich mich entschlossen, etwas einfacher umzuziehen. Nachdem wir mit der angegebenen Methode ein Array gebildet haben, haben wir Bretter, auf denen sich in jeder Vertikalen eine Dame befindet. Dementsprechend ist es notwendig, nur die horizontalen und diagonalen Linien herauszufiltern. Und hier habe ich mich für das Design entschieden not x in (y,z). Bei Konturen ist alles einfach:

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)


Diese Konstruktion kann auch reduziert werden, da not A in (B) = not B in (A) usw. erhalten wir:

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)


Abzüglich einer Zeile und in der Regel der Hälfte der Vergleiche.

Weitere Diagonalen - in gleicher Weise unter Berücksichtigung der Linienverschiebung:

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)


Und genauso not A in (B+1) = not B in (A-1) unnötige Vergleiche entfernen:

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)


Um auch die zweite Diagonale zu filtern, duplizieren Sie einfach den Code der ersten Diagonale und ersetzen Sie das Zeichen durch das Gegenteil:

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)


Somit haben wir drei Sätze von Bedingungen, die beachtet werden müssen, um das Problem zu lösen.

Machen Sie es sehen optimal und ohne zatroeniya in whereich alle Bedingungen gruppiert:

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)


Und am Ende formatieren wir die Ausgabe gemäß den Anforderungen in der Bedingung und fügen eine Sortierung hinzu, damit die Antwort anständig aussieht:

select 'a' || A A, 'b' || B B, 'c' || C C, 'd' || D D, 'e' || E E, 'f' || F F, 'g' || G G, 'h' || H H
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 Schade, dass ich nicht an dieser Olympiade teilgenommen habe.

PPS Die Entscheidung wurde getroffen, nachdem die Bedingungen des Problems gelesen worden waren, bevor sein Autor schriftlich nicht nachgesehen hatte.

Jetzt auch beliebt: