こんにちは、Habrolyudi！
5月、モスクワはIT Planet Olympiadを主催しました。その指名の1つは「Oracle DBMSプログラミング」でした。 タスクは面白くて難しかったので、いくつかのソリューションを共有したいと思います。
私が議論する最初のタスクは8人の女王の問題です。SQLのみを使用してそれを解決する必要があり、最初はこのタスクを解決しようとしているもののリストから削除しましたが、最後の1時間で解決しました。これにより、ロシア連邦のテレコムおよびマスコミュニケーションの大臣の手から1位と卒業証書が得られました。
そのため、タスクが発表され、答えは次の形式で提示する必要があります。
A B C D E F G H
--- --- --- --- --- --- --- ---
a7 b4 c2 d8 e6 f1 g3 h5
これはどのように解決されますか：
最初に行う必要があるのは、クイーンを配置したチェス盤を再現するクエリを作成することです。その後、間違った決定を除外できます。
Oracle階層クエリ（具体的には、レベルごとに接続）を使用して、1〜8の数字を発行するクエリを作成します。
select level a from dual connect by level <= 8
* This source code was highlighted with Source Code Highlighter .
これらは、A上の女王の可能な位置です（A1、A2、...）
このような8つのクエリのクロスジョインを作成します。明確にするために次の各文字を変更します。
select level a from dual connect by level <= 8
cross join
( select level b from dual connect by level <= 8)
cross join
( select level c from dual connect by level <= 8)
cross join
( select level d from dual connect by level <= 8)
cross join
( select level e from dual connect by level <= 8)
cross join
( select level f from dual connect by level <= 8)
cross join
( select level g from dual connect by level <= 8)
cross join
( select level h from dual connect by level <= 8)
* This source code was highlighted with Source Code Highlighter .
この方法で構築されたクエリは、16777216オプションを提供します。 2つのクイーンが同じ垂直に配置されている場合のオプション。 次に、同じ水平線上および対角線上の2つのクイーンを除外する必要があります。
問題を解決して、最初にすべてを垂直から削除しました：
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 a, b, c, d, e, f, g, h ,
case when a = b or a = c or a = d or a = e or a = f or a = g or a = h
then 0
else case when b = c or b = d or b = e or b = f or b = g or b = h
then 0
else case when c = d or c = e or c = f or c = g or c = h
then 0
else case when d = e or d = f or d = g or d = h
then 0
else case when e = f or e = g or e = h
then 0
else case when f = g or f = h
then 0
else case when g = h
then 0
else 1
end
end
end
end
end
end
end chk
from
( select level a from dual connect by level <= 8)
cross join
( select level b from dual connect by level <= 8)
cross join
( select level c from dual connect by level <= 8)
cross join
( select level d from dual connect by level <= 8)
cross join
( select level e from dual connect by level <= 8)
cross join
( select level f from dual connect by level <= 8)
cross join
( select level g from dual connect by level <= 8)
cross join
( select level h from dual connect by level <= 8)
)
where chk = 1
* This source code was highlighted with Source Code Highlighter .
これで最後の段階が残り、対角線からすべてを削除しました。
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 a, b, c, d, e, f, g, h ,
case when a = b or a = b - 1 or a = b + 1 or a = c or a = c - 2 or a = c + 2 or a = d or a = d - 3 or a = d + 3 or a = e or a = e - 4 or a = e + 4 or a = f or a = f - 5 or a = f + 5 or a = g or a = g - 6 or a = g + 6 or a = h or a = h - 7 or a = h + 7
then 0
else case when b = c or b = c - 1 or b = c + 1 or b = d or b = d - 2 or b = d + 2 or b = e or b = e - 3 or b = e + 3 or b = f or b = f - 4 or b = f + 4 or b = g or b = g - 5 or b = g + 5 or b = h or b = h - 6 or b = h + 6
then 0
else case when c = d or c = d - 1 or c = d + 1 or c = e or c = e - 2 or c = e + 2 or c = f or c = f - 3 or c = f + 3 or c = g or c = g - 4 or c = g + 4 or c = h or c = h - 5 or c = h + 5
then 0
else case when d = e or d = e - 1 or d = e + 1 or d = f or d = f - 2 or d = f + 2 or d = g or d = g - 3 or d = g + 3 or d = h or d = h - 4 or d = h + 4
then 0
else case when e = f or e = f - 1 or e = f + 1 or e = g or e = g - 2 or e = g + 2 or e = h or e = h - 3 or e = h + 3
then 0
else case when f = g or f = g - 1 or f = g + 1 or f = h or f = h - 2 or f = h + 2
then 0
else case when g = h or g = h - 1 or g = h + 1
then 0
else 1
end
end
end
end
end
end
end chk
from
( select level a from dual connect by level <= 8)
cross join
( select level b from dual connect by level <= 8)
cross join
( select level c from dual connect by level <= 8)
cross join
( select level d from dual connect by level <= 8)
cross join
( select level e from dual connect by level <= 8)
cross join
( select level f from dual connect by level <= 8)
cross join
( select level g from dual connect by level <= 8)
cross join
( select level h from dual connect by level <= 8)
)
where chk = 1
* This source code was highlighted with Source Code Highlighter .
対角線から余分なものを取り除くことはあまりエレガントではなく、absを使用できますが、オリンピックのラッシュでは、特に時間の終わりの2分前に回答を送信したため、それは起こりませんでした。
このソリューションは絶対に合法であり、この問題に対する92のソリューションすべてを提供します。
UPD：「異常なプログラミング」に移動