Pchełki SQL. Odcinek 2: Magia kwadratów

Dziś przytrafiła mi się pchełka-perełka, czyli miniaturka SQL z życia wzięta.

Otóż nie dawniej jak parę dni temu jeden ze znajomych poprosił mnie o rozwiązanie zagadki, nad którą sam się biedzi od dwóch dni, a której rozwiązanie jest mu niezbędnie potrzebne, i to czym wcześniej tym lepiej.

Zagadką okazał się być niekompletny kwadrat magiczny, którego brakujące cyfry należy najpierw odgadnąć, a potem wpisać we właściwej kolejności w GPS-a, żeby znaleźć Skarb.

Niekompletny kwadrat wyglądał tak:

Dla przypomnienia: kwadrat magiczny to kwadrat liczbowy o następujących właściwościach:

1. Wszystkie elementy tworzą ciąg skończony arytmetyczny zaczynający się od jedynki, o różnicy jeden i liczbie elementów równej ilości pól kwadratu (tu: 25) ,

2. Suma liczb w każdym wierszu, każdej kolumnie oraz na obydwu przekątnych jest taka sama. W tym przypadku sumą tą jest 65, co wiemy stąd, że jedna z przekątnych jest już wypełniona. Ponadto, nawet jeżeli nie mielibyśmy do dyspozycji jednej pełnej przekątnej (czy też wiersza bądź kolumny), liczbę 65 łatwo wyznaczyć jako pięciokrotność środkowego elementu (środkowego czyli znajdującego się dokładnie pośrodku między liczbami 1 a 25). Elementem tym jest 13, 13*5=65.

Najpierw zauważamy, że suma liczb w lewej skrajnej kolumnie wynosi 18, a więc do 65 brakuje 47. Sumę 47 można uzyskać wyłącznie z liczb 22 i 25 (pozostałe kombinacje wymagają albo użycia liczby, która już istnieje w kwadracie, albo liczby większej od 25.

Analogicznie sprawa ma się z górnym skrajnym wierszem: brakująca suma to 37 i jedyna para liczb dająca tę sumę to 18 i 19 (podobnie jak w poprzednim przypadku, wszystkie inne pary wymagają albo powtórzenia albo użycia liczby większej niż 25).

Poniżej kwadrat z wpisanymi liczbami 22, 25, 18 i 19. Ponadto, pustym komórkom przypisałem zmienne ponumerowane od n1 do n11.

Nie wiemy wprawdzie czy 18 i 19 nie są zamienione miejscami (podobnie jak 22 i 25), ale dzięki nim liczba niewiadomych zredukowała się z 15 do zaledwie 11.

Można by teraz zaryzykować rozwiązanie układu dziewięciu równań pierwszego stopnia z jedenastoma niewiadomymi: mamy cztery sumy w poziomie, cztery w pionie i jedną przekątną. Niestety, przy podejściu „tradycyjnym” ilość przekształceń potrzebna przy dziewięciu równaniach oraz ich stopień komplikacji są zbyt duże, żeby dało się to sensownie przeprowadzić. Oczywiście można jeszcze sięgnąć do wiedzy ze studiów i rozwiązać to za pomocą macierzy, ale w moim przypadku wymagałoby to odświeżania zbyt dużej ilości materiału. Ponadto, mamy o dwa równania za mało, więc nie wiadomo, czy udałoby się je w ogóle rozwiązać.

Postanowiłem więc zastrzelić tę muchę z armaty zwanej SQL.

Najpierw wykombinowałem, że ilość permutacji jedenastu liczb to ponad 31 milionów, a trzeba to jeszcze przemnożyć przez cztery (ponieważ nie wiemy które kombinacje 18-19 oraz 22-25 są poprawne), czyli docelowo ponad 124 miliony kombinacji. Dla każdej z nich należałoby wyliczyć sumę w wierszach, w kolumnach i na przekątnej, i tam gdzie wyjdą same sześćdziesiątkipiątki, mamy rozwiązanie.

Generowanie 124 milionów kombinacji zajęłoby mi około 25 minut, jednak coś mi podpowiadało, że można prościej.

Końcem końców udało mi się rozwiązać problem za pomocą jednego, jedynego zapytania SQL, bez tworzenia żadnych tabel, operując wyłącznie na statycznych danych wpisanych w samo zapytanie.

Zapytanie wygląda następująco:

 

with

mn as
(select
3 as n union select 4 union select 5

union select 6 union select 7 union select 8

union select 9 union select 10 union select 20

union select 21 union select 24)

, komb
as (select mn1.n n1, mn2.n n2, mn3.n n3,

mn4.n n4, mn5.n n5, mn6.n n6,

mn7.n n7, mn8.n n8, mn9.n n9,

mn10.n n10, mn11.n n11

from mn mn1, mn mn2, mn mn3,

mn mn4, mn mn5, mn mn6,

mn mn7, mn mn8, mn mn9,

mn mn10, mn mn11)

select *

from komb

where

n1<>n2

and n1<>n3 and n2<>n3

and n1<>n4 and n2<>n4 and n3<>n4

and n1<>n5 and n2<>n5 and n3<>n5 and n4<>n5

and n1<>n6 and n2<>n6 and n3<>n6 and n4<>n6 and n5<>n6

and n1<>n7 and n2<>n7 and n3<>n7 and n4<>n7 and n5<>n7 and n6<>n7

and n1<>n8 and n2<>n8 and n3<>n8 and n4<>n8 and n5<>n8 and n6<>n8 and n7<>n8

and n1<>n9 and n2<>n9 and n3<>n9 and n4<>n9 and n5<>n9 and n6<>n9 and n7<>n9 and n8<>n9

and n1<>n10 and n2<>n10 and n3<>n10 and n4<>n10 and n5<>n10 and n6<>n10 and n7<>n10 and n8<>n10 and n9<>n10

and n1<>n11 and n2<>n11 and n3<>n11 and n4<>n11 and n5<>n11 and n6<>n11 and n7<>n11 and n8<>n11 and n9<>n11 and n10<>n11

and n1+n2+n3+2+12=65

and n4+n5+n6+25+13=65

and n7+n8+22+14+17=65

and n9+n10+n11+15+23=65

and n1+n4+n9+18+14=65

and n2+n7+n10+19+13=65

and n5+n8+n11+16+12=65

and n3+n6+11+17+23=65

and n1+n8+1+13+23=65;

Widać wyraźnie, że nie jest to jakiś Uniwersalny Rozwiązywacz Kwadratów Magicznych tylko konkretne narzędzie do tego jednego, konkretnego kwadratu. Niemniej jednak działa znakomicie – trzeba było tylko pokombinować z odpowiednim ustawieniem liczb 18, 19 22 i 25 (w powyższym kodzie są to linie 4, 5, 7 i 8 licząc od dołu).

Odrobina wyjaśnień: pierwsze CTE nazywa się mn (missing numbers, czyli brakujące liczby) i zwraca jednokolumnowy zestaw brakujących liczb. Kolejne CTE nazywa się komb i zwraca wszystkie jedenastoelementowe kombinacje (z powtórzeniami) tych brakujących liczb.

Wreszcie zapytanie właściwe wybiera spośród tych kombinacji takie, w których wszystkie elementy są różne (pierwszy blok w sekcji WHERE – ten z „trójkątnym” zestawem nierówności), oraz w których sumy wierszy (drugi blok), kolumn (trzeci blok) oraz przekątnej (ostania linijka) wynoszą 65.

Żeby zrozumieć skąd wzięły się te trzy ostatnie bloki warunku, proszę zerknąć jeszcze raz na kwadrat powyżej (ten z nazwami niewiadomych).

Ktoś mógłby teraz pomyśleć: „a jak długo się właściwie takie zapytanie wykonuje?” – bardzo słuszne pytanie. Otóż, przynajmniej teoretycznie, drugie CTE generuje 31 milionów wierszy, a więc powinno zeżreć mnóstwo pamięci i czasu procesora. Jednak SQL Server jest na tyle sprytny, że potrafi odfiltrować zbędne wiersze już na etapie ich generowania – pobieżna analiza planu wykonania tego zapytania wykazuje, że najliczniejszy podzbiór rekordów biorący udział w obliczeniach pośrednich to zaledwie 660. Stąd też czas wykonania zapytania w okolicach jednej sekundy.

A jaki jest wynik, zapytacie?

To już proszę sobie sprawdzić samemu 🙂

23
Dodaj komentarz

avatar
4 Comment threads
19 Thread replies
1 Followers
 
Most reacted comment
Hottest comment thread
7 Comment authors
magicxpilmagicxbwxpil Recent comment authors
  Subscribe  
najnowszy najstarszy oceniany
Powiadom o
pendragon
Gość
pendragon

Pchełka z życia wzięta i zastosowana w realu. Dzięki za pomoc a szczegóły u mnie.

Maciek
Gość
Maciek

Ja wole bardziej humanitarne rozwiazanie. 🙂 Oto ono. Na przekatnej 1-13-23 brakuje nam w sumie 28 (65-1-13-23=28). 28 z dwoch liczb (n1+n8) mozemy uzyskac tylko na trzy dostepne sposoby: 20+8, 21+7 i 24+4. W zaleznosci od tego, czy w czwartym rzedzie w pierwszej kolumnie wpiszemy 22, czy 25, to z pozostalych dwoch liczb (n7 i n8) musimy uzyskac sume 12 badz 9. Oznacza to, ze n8 (lezaca na przekatnej) moze byc rowna tylko mniejszej z liczb z wymienionych wczesniej kombinacji. Czyli n8 = 4, 7 lub 8, a tym samym n1 = 24, 21 lub 20. W zaleznosci od wartosci n1, pozostala suma w drugim wierszu to 27, 30 badz 31, ktora musimy uzyskac z dwoch liczb (n2+n3). Zatem jedna z tych liczb rowniez musi pochodzic ze zbioru {20, 21, 24}, aby bylo to mozliwe. Czyli musimy rozpatrzec mozliwe kombinacje liczb n1, n2 i n3, gdzie dwie z tych trzech liczb pochodza ze zbioru {20, 21, 24}, a trzecia dopelnia sume do 51 (n1+n2+n3=51, bo tyle nam brakuje w drugim rzedzie). Mamy 6 mozliwych kombinacji: 20+21+10=51 20+24+7=51 21+20+10=51 21+24+6=51 24+20+7=51 24+21+6=51 Zauwazmy, ze w piatej kolumnie brakuje nam w sumie tylko 14 (n3+n6=14). Zatem wiemy, ze najmniejsza liczba z powyzej wymienionynch kombinacji, to n3. Ponadto mozemy wyeliminowac dwie kombinacje z uzyciem 7-ki, bo gdyby n3=7, to rowniez n6=7 (n3+n6=14, jak pamietamy), a nie mozemy uzyc tej samej liczby dwa razy. Zatem zostaja nam cztery kombinacje i stad n3 = 10 lub 6, a n6 = 4 lub 8. Przyjrzyjmy sie teraz rzedowi trzeciemu. W zaleznosci od tego, czy w pierwszej kolumnie bedzie 22, czy 25, to brakujaca suma (n4+n5+n6) wynosi 30 lub 27. Jezeli dodamy do tego to, ze wiemy juz, ze n6 = 4 lub 8, to pozostala suma n4+n5 moze wynosic 19 (=27-8), 22 (=30-8), 23 (=27-4) albo 26 (=30-4). Zauwazmy, ze w zadnym wypadku nie jestesmy w stanie uzyskac sumy 22 z dostepnych liczb, wiec od razu ta mozliwosc odpada. Przypuscmy teraz, ze w pierwszej kolumnie wpiszemy jednak 22, a nie 25. Wowczas n4+n5+n6=30, a poniewaz sume n4+n5=22 odrzucilismy, to pozostaje nam tylko suma n4+n5=26, a stad n6=4. To pociaga za soba, ze n3=10 (bo n3+n6=14), a to z kolei oznacza, ze z kombinacji dla rzedu drugiego (n1,n2,n3) zostaja nam dwie kombinacje i w obu z nich uzywamy liczb 20 i 21. Zatem, wracajac do rzedu trzeciego, bez tych dwoch liczb, w zadnym wypadku nie uda uzyskac sie sumy 26, co prowadzi do sprzecznosci. Zatem jestesmy juz pewni, ze w pierwszej kolumnie w trzecim rzedzie nalezy wpisac 25, a pod nia, w rzedzie czwartym, 22. Wciaz jednak nie wiemy, czy n6 wynosi 4, czy 8. Jesli zalozymy, ze n6=4, to ponownie pozostaja nam tylko dwie kombinacje w rzedzie drugim z uzyciem liczb {10, 20, 21}. W takim wypadku niemozliwe jest otrzymanie sumy n4+n5=23 w rzedzie trzecim. Zatem okazuje sie, ze n4+n5 musi wynosic 19 (sume ta mozemy uzyskac tylko z 9-ki i 10-ki), przy niemozliwosci uzyskania sum 22, 23, 26. To doprowadza nas do wniosku, ze jezeli… Więcej »

xpil
Gość
xpil

No, jestem pod wrażeniem. Następną łamigłówkę od Pendragona przekieruję bezpośrednio do Ciebie 😉

pendragon
Gość
pendragon

Następnym razem posiedzę nad tym nie 2 dni tylko 4, bo taka metoda jest zupełnie w zasięgu i rzeczywiście "humanitarna". W szkole chyba to mieli na myśli mówiąc zdolny ale leniwy. Tak z ciekawości – Maciek długo nad tym siedziałeś?

Maciek
Gość
Maciek

Zajelo mi to jakies 2 godzinki. Czyli udalo sie zrozumiale to opisac? 🙂

xpil
Gość
xpil

Dość zrozumiale. Tak naprawdę to proste drzewo decyzyjne, tylko trzeba do niego solidnie przysiąść. Ja byłem do tego za leniwy (napisanie zapytania SQL zajęło mi jakieś 30 minut), a Pendragon z kolei – za leniwy.

xbw
Gość
xbw

Siedziałam nad tym jakieś 2-3 godzinki, z kartką (kartkami:) i długopisem.

xbw
Gość
xbw

Najpierw ustaliłam "wolne" cyfry i liczby. Odjęłam 18 i 19 oraz 22 i 25, bo na pewno zajmowały kratki, odpowiednio, w pierwszym rzędzie od góry, i w pierwszej kolumnie od lewej, choć na razie nie wiadomo, w jakiej kolejności. W kolumnie pierwszej z prawej wolne pola dają sumę 14, to daje 3 opcje w dwóch wariantach każda (4-10, 5-9, 6-8 i w drugą stronę). W dolnym rzędzie suma trzech wolnych pól musi wynosić 27. Z puli cyfr i liczb "do wzięcia" pozostaje jedynie trójka: 20 – 3 – 4, i jedyne warianty dla prawej kolumny 6-8/8-6 lub 5-9/9-5, 4-10/10-4 odpada, bo nijak nie da się pogodzić z tym 27 na dole. Teraz z "wolnej puli" wyrzucam więc także 20, 3 i 4. Dla drugiego rzędu od dołu przygotowałam dwie alternatywne wersje, wiedząc, że po lewej stronie będzie albo 22 albo 25. Po "zagospodarowaniu" 20, 3 i 4 dla drugiego rzędu od dołu wyłoniła się tylko jedna opcja, mianowicie 5-7/7-5, też dwa warianty, ale już dwie kolejne cyferki z "wolnej puli" mniej. Przy okazji można było już ustalić na pewno położenie dla 22 i 25. W prawej kolumnie po "wyrzuceniu" 5 pozostała jedna opcja w 2 wariantach 6-8/8-6. Teraz wzięłam się za drugą przekątną. Suma pól wolnych w niej to 28. Odjęłam od 28 pięć, co mi nic nie dało, więc odjęłam siedem ustalając na stałe pozycję 7 i 5, a także 21, bo tylko 21 z wolnych dawało potrzebną sumę. A końcówka to już się "sama" uzupełniła. Metodą gospodarczą, ale nie mam żadnego przygotowania, by się zagłębiać w "nauki". A wszystko przez pomysły Pendragona. Uff. Para mi przez uszy wylatuje. Pozdrawiam.

xpil
Gość
xpil

Najbardziej podoba mi się w powyższym rozumowaniu ten kawałek: "Odjęłam od 28 pięć, co mi nic nie dało"

😉

xbw
Gość
xbw

Skrót myślowy 😉

Maciek
Gość
Maciek

"W dolnym rzędzie suma trzech wolnych pól musi wynosić 27. Z puli cyfr i liczb “do wzięcia” pozostaje jedynie trójka: 20 – 3 – 4"

Niestety to nie do konca prawda, bo jest jeszcze mozliwosc 10+9+8=27, ktora nalezy odrzucic. Jednak z racji tego, ze kazda z tych liczb wystepuje w ktorejs z kombinacji 4+10, 5+9, 6+8, to nigdy nie bedziemy mieli ich wszystkich trzech do dyspozycji. 🙂

pendragon
Gość
pendragon

🙂

magic
Gość

A ja znalazlem taki kwadrat magiczny rzedu 5:
25 ? 7 ? 15
? 5 ? 14 ?
? ? 13 ? 18
? 12 ? 19 ?
11 ? ? ? 3