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

In Pchełki SQL by xpil23 Comments

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 🙂

Dodaj komentarz

23 komentarzy do "Pchełki SQL. Odcinek 2: Magia kwadratów"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
pendragon
Gość

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

Maciek
Gość
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… Więcej »
xpil
Gość

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

pendragon
Gość

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ść

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

xpil
Gość

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ść

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

xbw
Gość
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,… Więcej »
xpil
Gość

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

😉

xbw
Gość

Skrót myślowy 😉

Maciek
Gość

"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ść

🙂

magic
Gość

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

wpDiscuz