Cyfrowanka
Po zatytułowaniu tego wpisu zacząłem się zastanawiać, czy cyfrowanki już kiedyś nie było. Sprawdziłem i okazało się, że tak, ale dotyczyła zadania nieco innego niż poniższe. W gruncie rzeczy każdą łamigłówkę, w której do pól diagramu wpisuje się liczby jednocyfrowe można by tak nazwać, a na pierwszy ogień poszłoby kakuro – dziś już prawie zapomniane, choć czasem wskrzeszane, ostatnio np. w ramach eliminacji do tegorocznych XXIII Mistrzostw Polski w Łamigłówkach.
Nazwa cyfrowanka kojarzy się jednak z czymś małym, jakby bibelotem. Oto więc przykład takiego cacka.
W każdym polu jasnego kwadratu 4×4 powinna znaleźć się cyfra. Cztery są już na swoich miejscach. Zadanie polega na wpisaniu dwunastu pozostałych – żadna nie może być zerem. Kluczem do rozwiązania są liczby przy brzegu – każda oznacza sumę czterech cyfr w danym rzędzie lub kolumnie, zaś liczby przy rogach równe są sumom cyfr na przekątnych.
Do przemyślenia: czy bez podanych sum cyfr na przekątnych (17 i 20), albo chociaż bez jednej z nich, rozwiązanie także byłoby jedno.
A na deser żartobliwy drobiazg z całkiem innej beczki: które zwierzę po przyprawieniu mu ogonka zmienia się w wielkość fizyczną?
Komentarze
kret -> kręt
http://pokazywarka.pl/cyfrowanka/
Po usunięciu jednej z sum przekątnych jest wiele rozwiązań.
http://pokazywarka.pl/zwierz/
Mól, gdy mu zabrać ogonek (czy mole mają ogonki, hm), staje się molem.
Odwrotnej sytuacji na razie nie kojarzę 🙂
8916
2723
2511
7441
Do przemyślenia: nie. Najłatwiej znaleźć sub-rozwiązanie spełniające tylko warunki wierszowe i kolumnowe a naruszające przekątne. Potem można je poprawić aby naruszało tylko jeden warunek przekątnej, a wreszcie poprawić do rozwiązania (które wydaje się jednoznaczne jeśli nie dopuszczamy zer).
Cyfrowanka to bibelot szlachetny w swoim stylu i prostocie.
Czy można naszkicować jakiś algorytm jej rozwiązywania?
Kret z drugim ogonkiem (jeden własny i tak ma) to moment pędu czyli kręt
1)
8 9 1 6
2 7 2 3
2 5 1 1
7 4 4 1
Brak którejkolwiek z sum dla przekątnych spowoduje rozmnożenie rozwiązań.
2)
Szukanym zwierzęciem jest stworzenie przyprawiające o ból głowy niejednego działkowicza.
@ Markoniusz
„Czy można naszkicować jakiś algorytm jej rozwiązywania”?
Obawiam się, że ścisłego nie można. Formalnie rzecz biorąc, na przykładzie tego zadania, mamy 10 równań z 12 niewiadomymi, co raczej przesądza sprawę.
Praktyczny algorytm musi się więc opierać na maksymalnie zredukowanej metodzie prób i błędów. W tym zadaniu łatwo jest wyodrębnić zaledwie 5 przypadków do rozważenia i szybko otrzymać rozwiązanie. Miałem szczęście, gdyż już pierwszy z nich dał poprawny (mam nadzieję) rezultat. Pozostałych nawet nie sprawdzałem, gdyż zaufałem Gospodarzowi w kwestii istnienia tylko jednego rozwiązania. 🙂
@ OlaGM
Pewien Jarosław, mądra głowa,
przewidział wir – to rzecz nie nowa.
Lecz zrzędził
i kręcił,
że cyklon, to rzecz, w momentach niezdrowa.
Ot, taki pseudo-limeryk, jako podpowiedź do „żartobliwego drobiazgu”. Zamiast moli (móli).
Kręt/kret.
@ xswedc
Suma czterech wierszy musi być równa sumie czterech kolumn. A stąd wniosek, że niezależnych równań mamy nie 10 tylko 9. Ale ponieważ są to równania „bardziej niż diofantyczne” (bo liczby nie tylko muszą być całkowite, ale muszą być to liczby całkowite z przedziału od 1 do 9), to liczba rozwiązań musi być skończona.
Faktycznie mamy do rozważenia 5 przypadków, bo wiersz 3 to równanie z trzema niewiadomymi, które ma tylko 3 rozwiązania. Podobnie jest z trzecią kolumną. Jeżeli skojarzymy te dwa równania, to mamy 5 niewiadomych ale układów rozwiązań tylko 5. Po wyeliminowaniu tych dwóch równań i pięciu niewiadomych mamy 7 równań z 7 niewiadomymi. Tak więc mamy do odwrócenia tylko 5 macierzy 7 na 7. 🙂
@ Michał S
Napisałeś: „Faktycznie mamy do rozważenia 5 przypadków”.
Ja napisałem: „W tym zadaniu łatwo jest wyodrębnić zaledwie 5 przypadków”.
Pełna zgoda… Rozważyliśmy to samo, ale opisaliśmy innym językiem.
Markoniuszowi (i mnie) chodziło jednak o sformułowanie ogólnej zasady istnienia algorytmu – dla dowolnego zadania tego typu.
Od dawna kultywuję pewien obrządek: na Wielkanoc przyrządzam Coq au vin, czyli koguta w winie. Delicje… Cała radość, oprócz degustacji potrawy, polega na tym, że kucharz (czyli w tym przypadku ja) podczas duszenia ptaka, cały czas i bez przerwy, musi 🙂 sprawdzać jakość wina, w którym ów kogut się pitrasi. Robi to wypijając extra butelkę w celach, rzecz jasna, naukowo-poznawczych. Jest to niemal konieczne, gdyż, jak mówią tubylcy w jednym z regionów Francji: najlepsze pomysły przychodzą do głowy podczas przyrządzania coq au vin. Nie bez powodu.
W naszych, polskich warunkach czasem się ta metoda sprawdza, czasem nie. W tym roku, będąc już mocno zaawansowany w duszeniu koguta (znaczy, w testowaniu wina), napisałem dwa smutne teksty. Jeden z nich to pseudo-limeryk, drugi to pseudo-dowcipny tekst do Gospodarza. Ale bywały lata lepsze. Właśnie wyszukałem w moim archiwum rebus, który ułożyłem niemal dokładnie dziesięć lat temu, właśnie podczas przyrządzania mojego, wtedy pierwszego, wielkanocnego koguta:
http://pokazywarka.pl/rebus_wielkanocny/
Prosty, ale, moim zdaniem, pomysłowy. Proszę spróbować. Rebus wiązany to rzadka odmiana tego zadania. Ale to jest Łamiblog, więc nie będę objaśniał jego zasad.
Druga „kogucia” rzecz, która mi wyszła: napisałem programik do sprawdzania liczby rozwiązań zadania typu 100+13. Zmotywowała mnie kompletna porażka przy próbie „ręcznego” ułożenia takiego zadania. Okazało się, że ma ono aż 56 rozwiązań! Kiedy dopracuję szczegóły programu, być może opublikuję jeszcze raz taką łamigłówkę, tym razem z jednym – już na pewno – rozwiązaniem. Jeśli będą chętni – to udostępnię program.
Pozdrawiam, jeszcze świątecznie (23:59)
xswedc
Uwalniam wyjątkowo. Administrowanie blogiem (w dodatku półkulinarnym) w blogu jakoś mi się nie uśmiecha.
mp
Ha! Jeszcze jedna zagadka!
W powyższym poście napisałem godzinę ukończenia pisania (23:59), kliknięcie w „opublikuj komentarz” o 00:01, ale opublikowanie nastąpiło (według czasu w nagłówku postu) o godzinie 23:01!
Mój zegarek pokazuje godzinę już po północy, ale strona
http://pl.thetimenow.com/gmt/greenwich_mean_time
mówi mi, że jest po 22.
Jaki więc czas pokazuje strona blogów Polityki???
@xswedc
Gdyby ogólny algorytm istniał, oznaczałoby to, że istnieje ogólny algorytm rozwiązywania pewnej klasy układów równań diofantycznych, a o tym, że tak nie jest, świadczy negatywna odpowiedź na dziesiąty problem Hilberta.
Spróbujmy rozwiązać zadanie bez warunków dla przekątnych.
Do trzeciej kolumny można wpisać tylko cyfry 1 i 2, a największą cyfrą w kolumnie czwartej może być 6. Żeby spełniony był warunek dla pierwszego wiersza, na pozycji drugiej musi być co najmniej 8. Tak więc w wierszu pierwszym muszą być kolejno cyfry 8 lub 9, 1 lub 2 oraz 5 lub 6, przy czym z tych trzech par trzeba wziąć dwie większe cyfry i jedną mniejszą.
Jeżeli pierwszy wiersz ma postać 8916, to mamy dwie możliwości dla wiersza trzeciego: 2511 i 1521. Dla obu trzecia i czwarta kolumna daje się wyznaczyć i zostają po dwie pierwsze cyfry w wierszach drugim i czwartym. Mamy więc cztery równania i cztery niewiadome, ale ponieważ równania te nie są niezależne, mamy w obu przypadkach po 8 rozwiązań. Podobna sytuacja jest dla pierwszego wiersza 8925 (również dwie wersje wiersza trzeciego: 1512 oraz 2511 i też po 8 rozwiązań dla obu przypadków). Dla pierwszego wiersza 8826 jest tylko jedna możliwość dla trzeciego wiersza – 2511, a cztery cyfry na początkach wierszy drugiego i czwartego można wybrać na 7 sposobów. Bez przekątnych mamy zatem 39 rozwiązań.
Jeżeli dodamy warunek na przekątną, zaczynającą się od lewego górnego narożnika, to dla każdego z pięciu układów wierszy pierwszego i trzeciego mamy jedno rozwiązanie. Podobnie jest, gdy dodamy warunek dla drugiej przekątnej. Ale tylko jedno rozwiązanie jest wspólne dla obu warunków na przekątne:
8916
2723
2511
7441
8,9,1,6
2,7,2,3
2,5,1,1
7,4,4,1
Cyfrowanka dopuszcza jako rozwiązania tylko liczby dodatnie 1-cyfrowe oraz narzuca tylko wyrazy wolne równań (wszystkie współczynniki = 1). Jest więc szczególnym zadaniem diofantycznym, nie ogólnym.
Myślę że cyfrowankę tej postaci zawsze można rozwiązać metodą kolejnych przybliżeń, którą naszkicuję.
Zaczynamy od zastąpienia docelowych sum (w dolnym wierszu i prawej kolumnie) formułami, które liczą różnicę między aktualnymi sumami i docelowymi (mierzą odchylenie od rozwiązania – ujemne na starcie). Stosownie do układu tych sum jedną z przekątnych potraktujemy jak wiersz, drugą jak kolumnę. Możemy też od razu wpisać jedynki do pustych komórek jako pierwsze przybliżenie rozwiązania.
Następnie wykonujemy ciąg takich kroków:
A) znajdujemy największe (co do modułu) odchylenie w wierszu (lub kolumnie) sum i odpowiadające mu największe odchylenie w kolumnie (lub odp. wierszu)
B) na przecięciu ekstremalnych odchyleń lokalizujemy komórkę, której wartość zwiększamy dotąd, aż zajdzie co najmniej jedna z opcji:
B1) odchylenie w wybranym wierszu spadnie poniżej drugiego z kolei tj.
przestanie być największe;
B2) osiągniemy graniczną wartość wpisu tj. 9;
B3) wyzerujemy odchylenie w kolumnie;
Uwaga: jeśli zlokalizowana komórka zawiera zadaną wartość startową, to przesuwamy się do następnego z kolei odchylenia w kolumnie (wierszu) i odpowiadającej mu komórki.
Po każdym takim kroku maleje suma odchyleń i znowu typujemy komórkę odpowiadającą za największe odchylenia i zwiększamy odp. jej wartość.
Może się zdarzyć, że likwidując ostatnie odchylenia przestrzelimy tą metodą inne sumy produkując odchylenia dodatnie (na skutek powiązań przekątnych). Wtedy dokonujemy korekty przesuwając wartości między wierszami lub kolumnami lub przekątnymi, aby naprawić jedną parę sum nie psując pozostałych.
W ten sposób rozwiązałem zadaną cyfrowankę oraz inną (tych samych wymiarów), którą ułożyłem sobie do testów.
@Markoniusz
Czy możesz opublikować szkielet Twojej testowej cyfrowanki ?
Chcę przetestować heurystyczną metodę na przykładzie dla którego nie znam rozwiązania.
Zadanie zadane rozwiązałem tym sposobem błyskawicznie, więc chcę sprawdzić czy to był tylko przypadek 🙂
@ Spytko z Melsztyna
Do celów testowania heurystyk może się przydać następująca informacja:
po zamianie 8 (z jasnego kwadratu 4×4) na 7, oryginalne zadanie ma jedno rozwiązanie.
Algorytm Markoniusza jest prawdopodobnie skuteczny, ale dość powolny (oczywiście, gdy stosuje go człowiek, a nie komputer). W analizowanym zadaniu suma wierszy jest równa 63 (suma kolumn oczywiście też). Po wpisaniu do pustych kratek jedynek, suma liczb w diagramie to 32. A zatem przy zwiększaniu za każdym razem wartości w jednej kratce o 1, musimy wykonać 31 kroków, aby dojść do rozwiązania.