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 🙂
Pchełka z życia wzięta i zastosowana w realu. Dzięki za pomoc a szczegóły u mnie.
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 n4+n5=19, to n6=8 (n4+n5+n6=27, bo w pierwszej kolumnie liczba 25 jest juz pewna).
Jezeli n6=8, to automatycznie n3=6, a wowczas n1+n2=45. Zatem lezaca na przekatnej n1 wynosi 21 lub 24, a n8 odpowiednio 7 lub 4 (n1+n8=28). Przygladamy sie teraz rzedowi czwartemu, zeby ustalic wartosc n8. W pierwszej kolumnie mamy juz wpisane 22, bo wyzej, w rzedzie trzecim, wpisalismy juz 25. Zatem n7+n8=12, a biorac pod uwage, ze n8 moze wynosic tylko 7 lub 4, to tym samym n7 moze wynosic 5 lub 8. Druga mozliwosc odpada, bo przeciez juz ustalilismy, ze n6=8 i 8-ka nie moze wystapic ponownie w n7. Stad wylaniaja sie kolejne pewne liczby n7=5, n8=7, n1=21, a n2=24.
Teraz patrzymy na czwarta kolumne. Tutaj wiemy juz, ze n5+n11=30 (bo n8=7). Z wczesniejszych rozwazan wiemy, ze n4+n5=19, czyli n5 wynosi 9 lub 10. Jednak sume n5+n11=30 mozemy uzyskac tylko jednym sposobem: 10+20 (9+21 odpada, bo n1=21), zatem n11=20, n5=10, a n4=9.
Teraz juz tylko pozostaje nam ustalenie kolejnosci liczb 18 i 19 w pierwszym rzedzie oraz 3 i 4 w rzedzie ostatnim (n9, n10). Dowodzimy przez sprzecznosc, ze jesli w drugiej kolumnie w pierwszym rzedzie wybierzemy 19, to n9=2 (bo n1=21, a n4=9). Zatem kolejnosc w pierwszym rzedzie to 18 w drugiej kolumnie, a 19 w trzeciej. Tym samym n9=3, a n10=4.
Wypelniony kwadrat wyglada tak:
1 18 19 16 11
2 21 24 12 6
25 9 13 10 8
22 14 5 7 17
15 3 4 20 23
No, jestem pod wrażeniem. Następną łamigłówkę od Pendragona przekieruję bezpośrednio do Ciebie 😉
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ś?
Zajelo mi to jakies 2 godzinki. Czyli udalo sie zrozumiale to opisac? 🙂
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.
Siedziałam nad tym jakieś 2-3 godzinki, z kartką (kartkami:) i długopisem.
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.
Najbardziej podoba mi się w powyższym rozumowaniu ten kawałek: "Odjęłam od 28 pięć, co mi nic nie dało"
😉
Skrót myślowy 😉
"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. 🙂
🙂
A ja znalazlem taki kwadrat magiczny rzedu 5:
25 ? 7 ? 15
? 5 ? 14 ?
? ? 13 ? 18
? 12 ? 19 ?
11 ? ? ? 3
Wynik:
25, 8, 7, 10, 1524, 5, 2, 14, 20
1, 17, 13, 16, 18
4, 12, 21, 19, 9
11, 23, 22, 6, 3
SQL:
-- b - brakujące:WITH b AS ( SELECT 1 n
UNION ALL SELECT 2
UNION ALL SELECT 4
UNION ALL SELECT 6
UNION ALL SELECT 8
UNION ALL SELECT 9
UNION ALL SELECT 10
UNION ALL SELECT 16
UNION ALL SELECT 17
UNION ALL SELECT 20
UNION ALL SELECT 21
UNION ALL SELECT 22
UNION ALL SELECT 23
UNION ALL SELECT 24 ) ,
kombinacje
AS ( SELECT b1.n n1, b2.n n2, b3.n n3, b4.n n4, b5.n n5, b6.n n6, b7.n n7
, b8.n n8, b9.n n9, b10.n n10, b11.n n11, b12.n n12, b13.n n13, b14.n n14
FROM b b1, b b2, b b3, b b4, b b5, b b6, b b7, b b8, b b9, b b10, b b11, b b12, b b13, b b14)
, permutacje AS (
SELECT k.n1, k.n2, k.n3, k.n4, k.n5, k.n6, k.n7, k.n8, k.n9, k.n10, k.n11, k.n12, k.n13, k.n14
FROM kombinacje k
WHERE n1 <> n2 AND n1 <> n3 AND n1 <> n4 AND n1 <> n5 AND n1 <> n6 AND n1 <> n7 AND n1 <> n8 AND n1 <> n9 AND n1 <> n10 AND n1 <> n11 AND n1 <> n12 AND n1 <> n13 AND n1 <> n14
AND n2 <> n3 AND n2 <> n4 AND n2 <> n5 AND n2 <> n6 AND n2 <> n7 AND n2 <> n8 AND n2 <> n9 AND n2 <> n10 AND n2 <> n11 AND n2 <> n12 AND n2 <> n13 AND n2 <> n14
AND n3 <> n4 AND n3 <> n5 AND n3 <> n6 AND n3 <> n7 AND n3 <> n8 AND n3 <> n9 AND n3 <> n10 AND n3 <> n11 AND n3 <> n12 AND n3 <> n13 AND n3 <> n14
AND n4 <> n5 AND n4 <> n6 AND n4 <> n7 AND n4 <> n8 AND n4 <> n9 AND n4 <> n10 AND n4 <> n11 AND n4 <> n12 AND n4 <> n13 AND n4 <> n14
AND n5 <> n6 AND n5 <> n7 AND n5 <> n8 AND n5 <> n9 AND n5 <> n10 AND n5 <> n11 AND n5 <> n12 AND n5 <> n13 AND n5 <> n14
AND n6 <> n7 AND n6 <> n8 AND n6 <> n9 AND n6 <> n10 AND n6 <> n11 AND n6 <> n12 AND n6 <> n13 AND n6 <> n14
AND n7 <> n8 AND n7 <> n9 AND n7 <> n10 AND n7 <> n11 AND n7 <> n12 AND n7 <> n13 AND n7 <> n14
AND n8 <> n9 AND n8 <> n10 AND n8 <> n11 AND n8 <> n12 AND n8 <> n13 AND n8 <> n14
AND n9 <> n10 AND n9 <> n11 AND n9 <> n12 AND n9 <> n13 AND n9 <> n14
AND n10 <> n11 AND n10 <> n12 AND n10 <> n13 AND n10 <> n14
AND n11 <> n12 AND n11 <> n13 AND n11 <> n14
AND n12 <> n13 AND n12 <> n14
AND n13 <> n14
)
SELECT TOP 1 *
FROM permutacje p
WHERE --- wiersze:
25 + 7 + 15 + p.n1 + p.n2 = 65
AND 5 + 14 + p.n3 + p.n4 + p.n5 = 65
AND 13 + 18 + p.n6 + p.n7 + p.n8 = 65
AND 12 + 19 + p.n9 + p.n10 + p.n11 = 65
AND 11 + 3 + p.n12 + p.n13 + p.n14
= 65--- kolumny:
AND 25 + 11 + p.n3 + p.n6 + p.n9 = 65
AND 5 + 12 + p.n1 + p.n7 + p.n12 = 65
AND 7 + 13 + p.n4 + p.n10 + p.n13 = 65
AND 14 + 19 + p.n2 + p.n8 + p.n14 = 65
AND 15 + 18 + 3 + p.n5 + p.n11 = 65
Witam,
nie pracowalem jeszcze w SQL, czy mozesz podac kompletny kod w/w rozwiazania i jak go wystartowac. Czy potrzebne jest SQL Software?
Potrzebny jest SQL Server, darmowy w wersji Developer. Do tego jakiś klient SQL, na przykład SSMS, darmowy ze strony Microsoftu. Z tym, że wyliczanie kwadratów magicznych za pomocą SQL to jakby odbierać jajka koparką. Są lepsze narzędzia.
O jakich lepszych narzedziach myslisz?
Matlab, R, Python, Rust, C#, Java, w zasadzie jakikolwiek porządny język programowania da radę. SQL jest bardzo wysokopoziomowy. Kwadraty 5×5 jeszcze udźwignie, ale z większymi może być kłopot.
Wlasnie myslalem o wiekszym rzedzie kwadratu i tzw bi- lub trimagicznych i w zaloszeniu, ze tylko pierwszy wiersz jest znany. Problemow jest jeszcze wiele w tej materii. Podales m.in. Java – idzie Ci o Java++ (nie Java Script)? Moja strona w tej dziedzinie to: http://www.number-galaxy.eu
Nie znam JavaScript ani Javy, ale jestem przekonany, że w obu się da wyrzeźbić co trzeba. Kwestia znajomości języka.
Nb strona może i fajna, ale nie na urządzenia mobilne. Próbowałeś ją otworzyć na telefonie?
Nie wyobrazam sobie na smartfonie otwierac przyklady kwadratow rzedu ponad 100. A takie przyklady wielokrotnie sa tam podane. Strona nie jest myslana w opcji mobilnej.
Zajrzałem. Kurdę, wielkie te kwadraty masz. Szacun.