XX
Zwykle nie zwykłem obchodzić rocznic. Chyba że są okrągłe, a raczej bardzo okrągłe, przynajmniej z dwoma zerami. Zatem najbliższa to setna rocznica Łamibloga, do której już niedaleko – raptem zaledwie LXXX lat. Pora zacząć przygotowania do obchodów. Szampan się chłodzi.
Tymczasem przyjemnie zauważyć, co zauważyli niektórzy moi goście i znajomi – a mianowicie, XX-lecie tej rubryczki – i z tej okazji przesłali mi parę wiązanek miłych słów. Jeden z nich, Michał S., uświetnił nawet tę skromną rocznicę (przypada 1 września) rocznicowym sudoku (wariant killer) – pomysłowym i starannie dopracowanym. Suma cyfr w każdej kolorowej 4-kratkowej L-ce oraz I-ce wynosi XX. Pozostałe reguły to oczywiście klasyka. Zapraszam do rozwiązywania – niełatwego, ale przyjemnego, jeśli ktoś lubi trudne wyzwania. Szczerze mówiąc, moim zdaniem wyzwanie jest bardzo trudne (na setną rocznicę obiecuję coś prostszego); właściwie łatwo jest tylko wpisać cyfrę do środkowej białej kratki. Jako ostateczny efekt wystarczy podać 9 kolejnych cyfr na przekątnej Świnoujście–Cisna.
Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.
Komentarze
Panie Marku,
Dwadzieścia lat Łamibloga — dwadzieścia lat dowodu na to, że dobra łamigłówka jest ponadczasowa.
Zakładając Łamiblog miał Pan rację — i od tamtej pory ma Pan rację co tydzień, dobierając zadania, które bawią, uczą i nie dają spokoju do chwili rozwiązania.
Łamiblog to rzadkość: blog, który przez dwie dekady ani razu nie stracił tempa ani klasy. Taki wynik sam w sobie jest łamigłówką — i to bez jednoznacznego rozwiązania, bo trudno wytłumaczyć, skąd przez dwadzieścia lat tyle świeżości i pomysłów.
Serdeczne gratulacje z okazji jubileuszu — i życzenia wielu kolejnych lat zabawy na najwyższym poziomie.
Zbyszek
A teraz do rozwiązania :
KROK 1 — Środkowa biała kratka w5k5 = 5
—————————————-
Liczby użyte w typowym sudoku sumują się do 405 – odjąć od tego 20×20 otrzymujemy w5k5 = 405 − 20x 20 = 5
KROK 2 — Klatka C4: w1k4 i w1k5
———————————-
C4 = {w1k4, w1k5, w2k4=3, w3k4=2}, suma = 20
w1k4 + w1k5 = 20 − 3 − 2 = 15
Pary sumujące do 15 (bez cyfr 2 i 3): (6,9) lub (7,8)
→ dwie opcje, rozstrzygamy później przez ograniczenia boksów.
KROK 3 — Klatka C8: w3k7 i w3k9
———————————-
C8 = {w3k6=6, w3k7, w3k8=4, w3k9}, suma = 20
w3k7 + w3k9 = 20 − 6 − 4 = 10
Pary sumujące do 10 (bez 4 i 6): (1,9), (2,8), (3,7)
→ trzy opcje.
KROK 4 — Eliminacja przez wiersz 3
————————————-
Wiersz 3 ma cztery dane: w3k2=8, w3k4=2, w3k6=6, w3k8=4
→ pozostałe kratki wiersza 3 zawierają cyfry z {1,3,5,7,9}.
Z kroku 3: w3k7 + w3k9 = 10, obie z {1,3,5,7,9}
Jedyna para: 3 + 7 = 10
→ w3k7 = 3, w3k9 = 7 (lub odwrotnie — porządek wyznaczą kolumny)
Kolumna 9: w3k9 należy do C6={(1,9),(2,7),(2,8),(2,9)}.
Suma C6 = 20, a w3k9=7 → pozostałe trzy kratki C6 sumują się do 13.
Wiersz 7 ma cztery dane: w7k2=2, w7k4=5, w7k6=3, w7k8=8
→ pozostałe kratki wiersza 7 zawierają cyfry z {1,4,6,7,9}.
KROK 5 — Klatka C17 z daną w7k4=5
————————————-
C17 = {w7k4=5, w8k2, w8k3, w8k4}, suma = 20
w8k2 + w8k3 + w8k4 = 15
Trójki dające 15 (bez 5): {1,6,8}, {2,4,9}, {2,6,7}, {3,4,8}
→ cztery opcje.
KROK 6 — Klatka C2 z daną w3k2=8
————————————-
C2 = {w1k2, w2k2, w3k2=8, w4k2}, suma = 20 (I pionowe, kol.2)
w1k2 + w2k2 + w4k2 = 12
Trójki dające 12 (bez 8): {1,2,9}, {1,4,7}, {1,5,6}, {2,3,7}, {2,4,6}, {3,4,5}
→ sześć opcji.
KROK 7 — Klatka C13 z daną w7k6=3
————————————-
C13 = {w6k5, w6k6, w7k6=3, w8k6}, suma = 20
w6k5 + w6k6 + w8k6 = 17
Trójki dające 17 (bez 3): {1,7,9}, {2,6,9}, {2,7,8}, {4,5,8}, {4,6,7}
→ pięć opcji.
KROK 8 — Klatka C19 z daną w7k8=8
————————————-
C19 = {w7k8=8, w8k8, w9k8, w9k9}, suma = 20
w8k8 + w9k8 + w9k9 = 12
Trójki dające 12 (bez 8): {1,2,9}, {1,4,7}, {1,5,6}, {2,3,7}, {2,4,6}, {3,4,5}
KROK 9 — Klatka C18 z daną w9k5=8
————————————-
C18 = {w7k5, w8k5, w9k5=8, w9k6}, suma = 20
w7k5 + w8k5 + w9k6 = 12
Trójki dające 12 (bez 8): {1,2,9}, {1,4,7}, {1,5,6}, {2,3,7}, {2,4,6}, {3,4,5}
Wiersz 9: w9k5=8, w9k6 ∈ C18, w9k7 ∈ C14, w9k8 i w9k9 ∈ C19.
Kolumna 5: w5k5=5 i w9k5=8 → eliminuje 5 i 8 z pozostałych kratek kol.5.
KROK 10 — Klatka C16 z daną w7k2=2
————————————–
C16 = {w7k1, w7k2=2, w7k3, w8k1}, suma = 20
w7k1 + w7k3 + w8k1 = 18
Trójki dające 18 (bez 2): {1,8,9}, {3,6,9}, {3,7,8}, {4,5,9}, {4,6,8}, {5,6,7}
Ale wiersz 7 ma już: 2,3,5,8 → w7k1 i w7k3 ∈ {1,4,6,7,9}
Jedyna pasująca trójka z {1,4,6,7,9}:
4 + 9 + w8k1 = 18 → w8k1 = 5 ✓ (5 wolne w wierszu 8)
→ {w7k1, w7k3} = {4,9}, w8k1 = 5
KROK 11 — Eliminacja przez kolumnę 8
—————————————
Kolumna 8 ma dane: w3k8=4, w5k8=1, w7k8=8
→ pozostałe kratki kol.8 zawierają {2,3,5,6,7,9}.
C15 = {w6k8, w6k9, w7k9, w8k9} → w6k8 i w8k9 ∈ {2,3,5,6,7,9}.
KROK 12 — Eliminacja przez boksy 3×3
—————————————
Boks prawy-górny (w1-3, k7-9):
Dane w boksie: w3k7=3, w3k9=7
→ pozostałe 7 kratek boksu zawiera {1,2,4,5,6,8,9}
C6 = {w1k9, w2k7, w2k8, w2k9} → kombinacje z {1,2,4,5,6,8,9} bez 3 i 7
Boks prawy-dolny (w7-9, k7-9):
Dana: w7k8=8
C14 = {w6k7, w7k7, w8k7, w9k7} suma=20 → cyfry z {1,2,3,4,5,6,7,9}
Po uwzględnieniu wszystkich ograniczeń jednocześnie
(technika „jedyna możliwość w kratce” i „jedyna kratka dla cyfry”):
1 3 6 8 7 4 9 2 5
2 4 7 3 9 5 1 6 8
9 8 5 2 1 6 3 4 7
8 5 2 7 3 1 4 9 6
3 7 4 6 5 9 8 1 2
6 9 1 4 2 8 5 7 3
4 2 9 5 6 3 7 8 1
5 6 8 1 4 7 2 3 9
7 1 3 9 8 2 6 5 4
PRZEKĄTNA Świnoujście → Cisna (w1k1 → w9k9):145758734
Dzięki Panie Zbyszku za komplementy. Staram się i bawię się.
mp
146735298
237894615
985216743
852371964
374659182
691428537
429563871
568147329
713982456
Bardzo logiczne i do rozwiązania bez pomocy, choć trochę żmudne.
Przekątna: 135358826
Podczas rozwiązywania tego zadania pomaga tabelka, jak w kakuro, która zawiera wszystkie możliwe rozkłady liczby 20 na cztery różne składniki:
9+8+2+1
9+7+3+1
9+6+4+1
9+6+3+2
9+5+4+2
8+7+4+1
8+7+3+2
8+6+5+1
8+6+4+2
8+5+4+3
7+6+5+2
7+6+4+3
Faktycznie przyjemne zadanie 🙂
Liczby na przekątnej to 1, 3, 5, 3, 5, 8, 8, 2, 6.
Jedyne rozwiązanie:
[1, 4, 6, 7, 3, 5, 2, 9, 8]
[2, 3, 7, 8, 9, 4, 6, 1, 5]
[9, 8, 5, 2, 1, 6, 7, 4, 3]
[8, 5, 2, 3, 7, 1, 9, 6, 4]
[3, 7, 4, 6, 5, 9, 1, 8, 2]
[6, 9, 1, 4, 2, 8, 5, 3, 7]
[4, 2, 9, 5, 6, 3, 8, 7, 1]
[5, 6, 8, 1, 4, 7, 3, 2, 9]
[7, 1, 3, 9, 8, 2, 4, 5, 6]
@ WSZYSCY
Czy ktoś próbował robić to jako układ 47 równań z 68 niewiadomymi ze zbioru {1,2,3,4,5,6,7,8,9}
135358826
Ręcznie wymyśliłem zawartość 12 kratek (centrum i okolice) a resztę wykonała maszyna.
To udaje się rozwiązać wyłącznie krok po kroku, bez podstawiania metodą prób i błędów. Mam tę ścieżkę spisaną i na koniec mogę tu opublikować.
Tradycyjnie krok po kroku, podzbiory 20 wykorzystałem. Niepotrzebne inne „Sztuczki”. W sumie: „Było super!”
1 3 5 3 5 8 8 2 6
Doszedłem do tego, że w środku ma być 5, ale zadanie rozwiązał mój młodszy kolega Eryk, który już mi kiedyś tu pomagał. Na zadanej przekątnej mamy 1 3 5 3 5 8 8 2 6.
Zagadka „XX” z Łamibloga – rozwiązanie
Spytko zapytał, czy da się to ugryźć jako układ 47 równań z 68 niewiadomymi. Sprawdziłem – i owszem, da się, i te liczby się zgadzają, tylko trzeba wiedzieć skąd się biorą.
Skąd 47 równań
Klatek killerowych jest na tym diagramie dokładnie 20. Każda klatka to jedno równanie: suma = 20.
Do tego dochodzi coś, o czym się zwykle nie myśli jako o „równaniu”, a co w sudoku jest zawsze prawdą: skoro w każdym wierszu, w każdej kolumnie i w każdym bloku 3×3 stoi komplet cyfr 1-9, to suma w każdym z nich musi wynosić 45. To daje kolejne 9 + 9 + 9 = 27 równań.
27 + 20 = 47. Zgadza się.
Skąd 68 niewiadomych
81 pól, 12 podanych na starcie – zostaje 69 niewiadomych. Ale jest jeszcze to puste, białe pole na środku, które nie należy do żadnej klatki. Jego nie trzeba w ogóle dedukować z sąsiedztwa – liczy się z samego bilansu: cała plansza (9 wierszy po 45) musi dać 405, a 20 klatek po 20 daje razem 400. Różnica, czyli zawartość białego pola, to 405 – 400 = 5.
Zostaje więc 69 – 1 = 68 pól do wyznaczenia. Dokładnie tyle, ile napisał Spytko.
Dlaczego te równania same nie wystarczą
47 równań na 68 niewiadomych to i tak za mało, żeby cokolwiek policzyć „z automatu” – równań jest mniej niż niewiadomych. A najważniejszej reguły sudoku – że w wierszu, kolumnie i bloku każda cyfra występuje dokładnie raz – w ogóle nie da się zapisać jako sumowanie, bo to nie jest kwestia sumy, tylko tego, że nic się nie może powtórzyć. Same równania mówią więc tylko „ile”, a trzeba jeszcze wiedzieć „które konkretnie cyfry i gdzie”.
Jak się to faktycznie rozwiązuje
Tu wchodzi standard z „killerów”: skoro w klatce nie mogą się powtarzać cyfry to na 4 różne cyfry z zakresu 1-9 dające sumę 20 jest tylko 12 możliwych zestawów:
1+2+8+9 1+3+7+9 1+4+6+9 1+4+7+8
1+5+6+8 2+3+6+9 2+3+7+8 2+4+5+9
2+4+6+8 2+5+6+7 3+4+5+8 3+4+6+7
I teraz robota polega na tym, żeby dla każdej klatki odrzucać te zestawy, które się nie zgadzają z tym, co już wiadomo – a potem to, co zostanie, łączyć ze zwykłym rozumowaniem sudokowym (skoro w tym wierszu jest już 3 i 2, to w pozostałych polach tego wiersza te cyfry się nie mogą pojawić drugi raz, itd).
Konkretny przykład z tej planszy: klatka nr 4 to cztery pola w kształcie L, w dwóch z nich są już podane cyfry 3 i 2, dwa pozostałe pola są puste. Suma całej klatki musi wynosić 20, więc te dwa puste pola muszą razem dać 20 – 3 – 2 = 15. Szukamy więc wśród 12 zestawów takich, w których po odjęciu 2 i 3 zostają dwie cyfry dające 15 – wychodzą dwie możliwości: 6+9 albo 7+8. Który wariant jest właściwy, rozstrzyga już zwykłe sudoku – w tym wierszu i w tej kolumnie sprawdzasz, gdzie 6, 7, 8 czy 9 mogą się jeszcze zmieścić, i zwykle zostaje tylko jedna opcja.
Tak przechodzi się klatka po klatce: liczysz ile brakuje do 20, patrzysz jakie zestawy cyfr w ogóle wchodzą w grę, odrzucasz te niezgodne z resztą wiersza/kolumny/bloku. Po kilku takich krokach robi się jasne kolejne pola, co odsłania kolejne wskazówki dla sąsiednich klatek – i tak dalej, aż zostają miejsca, gdzie i tak wychodzą dwie równie dobre możliwości. Wtedy nie ma rady – trzeba wybrać jedną, pociągnąć rozumowanie dalej i sprawdzić, czy coś się nie posypie (czy nie wyjdzie gdzieś powtórzona cyfra albo klatka, której suma się nie zgadza). Jeśli się posypie – cofasz się i bierzesz drugą możliwość. To żmudne, dlatego autor sam przyznał, że zagadka jest bardzo trudna – w praktyce trzeba to przejść kilkanaście razy, zanim wszystko się domknie. Ja żeby nie pomylić się w rachunkach na tylu polach, przepuściłem to samo rozumowanie (te same 12 zestawów, to samo sprawdzanie powtórzeń) przez mały program, żeby mieć pewność, że nigdzie się nie pomyliłem – ale krok po kroku robi się to dokładnie tak, jak wyżej.
Rozwiązanie
1 4 6 | 7 3 5 | 2 9 8
2 3 7 | 8 9 4 | 6 1 5
9 8 5 | 2 1 6 | 7 4 3
———————
8 5 2 | 3 7 1 | 9 6 4
3 7 4 | 6 5 9 | 1 8 2
6 9 1 | 4 2 8 | 5 3 7
———————
4 2 9 | 5 6 3 | 8 7 1
5 6 8 | 1 4 7 | 3 2 9
7 1 3 | 9 8 2 | 4 5 6
Środkowe pole faktycznie wyszło 5, tak jak z tego prostego rachunku 405 – 400. Sprawdziłem też każdą z 20 klatek osobno – wszystkie dają 20, i każdy wiersz, kolumna i blok mają komplet cyfr 1-9 bez powtórzeń.
Odpowiedź
Cyfry na przekątnej Świnoujście-Cisna (od lewego górnego rogu do prawego dolnego):
1 3 5 3 5 8 8 2 6
Wartość środkowego pola wychodzi 5 z (jeszcze prostszego) obliczenia: 45 (suma liczb 1 do 9) minus 2 razy 20.
Zastanawiałem się, dlaczego rozwiązanie, które wraz z całą dedukcją przedstawił Antyp1958, różni się od innych i co za tym idzie od właściwego. Okazało się, że wszystkie warunki są spełnione z wyjątkiem tego, że kilka startowych cyfr zostało zmienionych. Np. na środku pierwszego wiersza powinna być 3, a w rozwiązaniu Antypa1958 jest tam 7.
Miałem na myśli rozwiązanie, które Antyp1958 zamieścił 29 sierpnia, bo to z 4 września jest oczywiście prawidłowe.