Sześcioraczki
W lipcowym Świecie nauki zamieszczone było bardzo trudne, a ściślej – niezwykle żmudne zadanie, którego poprawne rozwiązanie nadesłała tylko jedna osoba. Postanowiłem przedstawić je także w Łamiblogu, bo być może komuś uda się znaleźć sprytny sposób uporania się z nim, czyli okaże się, że nie jest ono aż tak benedyktyńskie. Oczywiście za sposób nie uważam napisania programu komputerowego, choć wydaje się, że to także nie jest zbyt proste.
Wypełnienie prostokąta 6×5 cyframi od 1 do 5 jest częściowo magiczne: każdą kolumnę tworzy pięć różnych cyfr, a suma cyfr w każdym wierszu jest taka sama, równa 18. Prostokąt ten należy podzielić wzdłuż linii przerywanych na sześć pentomin, czyli figur (wielokątów) złożonych z pięciu kratek – tak, aby w każdym pentominie znalazło się pięć różnych cyfr. Gdyby to był koniec zadania, byłoby ono dziecinnie proste, bo sposobów takiego podziału jest mnóstwo, zaczynając od trywialnego – na pięć (poprawka: sześć) pasków-kolumn. Dodatkowy warunek, który czyni zadanie „sadystycznym”, brzmi: kształt każdego pentomina powinien być inny (kształty, które są względem siebie odbiciami lustrzanymi, uważamy za jednakowe).
Sposobów podziału jest więcej niż jeden. Wystarczy podać ile, ale mile widziane będzie przedstawienie w jakiejś formie konkretnych podziałów.
Komentarze
Znalazłem dwa rozwiązania (i wykluczyłem pozostałe możliwości). Czas dłubania: ok. godziny. Możliwość pomyłki: jak zwykle, spora 🙂
Zacząłem od wybrania jednego pola gdzieś w środku diagramu, z którego wyznaczam wszystkie możliwe pentomina (będzie ich kilka, prawie na pewno mniej niż 10). Teraz dla każdej możliwości zaczynam dłubaninę, ale wybór figury w środku diagramu powoduje, że liczba kombinacji nie jest zbyt wielka (istniejący kształt wymusza kolejne pentomino, albo sobie zablokowałem połączenia między niektórymi cyframi, albo kształty się powtarzają).
Cyfra oznacza numer figury:
112223
412253
411653
446653
466553
111116
222266
344256
334456
334555
Wszystkich możliwych podziałów (bez warunku o innym kształcie) jest 125.
Z różnymi pentominami są trzy podziały.
http://pokazywarka.pl/hvc8ur/
Znalazłem programistycznie 3 rozwiązania .
Korzystając ze strony https://isomerdesign.com/Pentomino/5×6/index.html
Pobrałem 541 możliwych rozwiązań dla prostokątu 5×6.
Po uwzględnieniu obrotu i odbić lustrzanych do sprawdzenia jest 2164 układów.
Być może, że gdzieś mam błąd i jednak jest ich więcej 🙁
Teraz myślę, jak to zrobić sprytnie.
Poniżej rozwiązania
IIIIIY
LLLLYY
PFFLTY
PPFFTY
PPFTTT
———-
IIIIIY
LLLLYY
PPPLTY
PPNNTY
NNNTTT
———-
ZZPPPI
YZPPLI
YZZWLI
YYWWLI
YWWLLI
Znalazłem trzy rozwiązania:
(Każda litera oznacza osobne pentomino)
1.
ABBCCD
ABCCDD
ABCEED
ABFFED
AFFFEE
2.
AAAAAB
CCCCBB
DDDCEB
DDFFEB
FFFEEE
3.
AAAAAB
CCCCBB
DEECFB
DDEEFB
DDEFFF
Dla porządku:
w treści zadania znalazł się drobny błąd.
Jest:
„zaczynając od trywialnego – na pięć pasków-kolumn”
powinno być:
„zaczynając od trywialnego – na SZEŚĆ pasków- kolumn”
Zadanie „Dla wodniaków” przegapiłem z powodu pobytu „u wód”.
Ale już cieszę się na jego rozwiązywanie 🙂
Rozwiazalam metodą próbować do skutku. Skutek wyszedł taki:
AABBBC
DABBEC
DAAFEC
DDFFEC
DFFEEC
Początkowo wpis otworzył mi się bez ilustracji, czyli bez diagramu (mam słabą komórkę). Myślałam zatem, że zadanie polega na tym, żeby ułożyć diagram do rozwiązania. Ułożyłam w kilka minut:
123435
251244
345123
414351
532512
Juz chciałam go wysłać, gdy odsłonił mi się tamten. Trudny faktycznie, dwa dni do niego podchodziłam, zanim się udało. A jaki jest ten mój? Rozwiąże ktoś?
Pozdravy z Moraw Południowych 🙂
Olu bez warunku o różnych kształtach pentomin Twoje zadanie ma 35 różnych rozwiązań. Z tym warunkiem są tylko dwa rozwiązania.
Układając od lewej strony są to pentomina:
1. I P W Y V N
2. I T W L P N
Pozdrowienia ze (z)Dolnego Śląska.
Napisanie programu okazało się nietrudne (przy wykorzystaniu w pewnym stopniu dorobku ludzkości).
Pozwoliło to zweryfikować pewne kwestie.
Otóż odpowiedź na propozycję OlaGm to:
ABBBCD
ABBCCD
AECCDD
AEFFFD
AEEEFF
Z kolei mój układ (1.) z wcześniejszego komentarza jest błędny, ale reszta się broni 🙂
@Antyp: najbardziej z tym warunkiem. Zaczęłam od narysowania figur, tych oznaczonych u Ciebie jako 2.
…i @Apartado:
Pytam z ciekawości: zawsze piszecie program, zamiast rozwiązywać ołówkiem? To jest bardziej emocjonujące?
Napisałem program i okazało się, że przegapiłem jedno rozwiązanie:
111116
222266
333256
334456
444555
I przy okazji potwierdzam rozwiązania Antypa z 192101 😉
A w programie trudniej chyba wyszukać różne pentomina, niż później już z nich złożyć całą planszę. Przy takim rozmiarze program działa momentalnie.
@OlaGM:
Pozwolę sobie odpowiedzieć na pytanie: dla kogoś, kto lubi programować (a taką osobą jestem), obydwa sposoby są emocjonujące. Przy czym często sam program jest celem, a nie jego wyniki 😉 Zawsze zaczynam od rozwiązywania samemu, a później dopiero program (nie zawsze, zależy od problemu). Jeśli nie uda się samemu, to jest większa motywacja do pisania. Najlepiej jeśli uda się zrobić jedno i drugie, a jeśli na dodatek oba sposoby dadzą te same rezultaty, to już pełnia szczęścia. Jak się okaże po uwolnieniu komentarzy, pełni szczęścia nie osiągnąłem tym razem 😉
@OlaGM
„Sześcioraczki” zrobiłem najpierw ręcznie, ale potem (po małym rozpoznaniu w necie) napisałem program – często daje to jakieś dodatkowe, ciekawe obszary do penetracji.
Ogólnie łamigłówki robię długopisem (nie lubię metody „prób i błędów”, więc ołówek i gumka nie dla mnie) – mam za sobą w ostatnich dniach sporo nurikabe – na kilku poległem i cała przyjemność po mojej stronie.
Program znalazł 3 rozwiązania:
AAAAAB
CCCCBB
DDDCEB
DDFFEB
FFFEEE
AAAAAB
CCCCBB
DEECFB
DDEEFB
DDEFFF
AABBBC
DABBEC
DAAFEC
DDFFEC
DFFEEC
@OlaGM:
Pisanie programów, które rozwiązują łamigłówki samo w sobie jest łamigłówką. Trzeba zdecydować, jak reprezentować dane łamigłówki w pamięci komputera, trzeba napisać funkcje obsługujące transformacje stanów łamigłówki zgodnie z jej regułami. Trzeba zadbać o wydajność programu, aby dał on efekty w sensownym czasie, bowiem dość często algorytmy brute-force, czyli sprawdzanie wszystkich możliwości po kolei, potrafią działać godzinami/dniami/latami (*oczywiście niecierpliwy programista po godzinie działania programu przerywa go, bo to już za długo). Trzeba zadbać o sensowne odcinanie częściowych rozwiązań, których nie ma sensu rozpatrywać (bo np. rozważają sytuację symetryczną do już obsłużonej albo częściowe rozwiązanie na gołe oko nie doprowadzi do lepszej odpowiedzi niż już wcześniej znalezione).
Jest wiele aspektów, o które trzeba zadbać, a przy okazji dobrze napisany program pomaga zweryfikować ręczne rozwiązanie otrzymane za pomocą kartki i ołówka.
Panowie i Panie programiści.
Od jakiegoś już czasu chciałem utworzyć repozytorium do zbierania efektów Waszych programistycznych prac związanych z Łamiblogiem. Udało się:
https://github.com/miodziu/penszko-lamiblog
Zachęcam Was do wrzucania tam swoich kodów programów. Wtedy mają szansę one przetrwać nieco dłużej niż tylko na czas aktualnego wpisu na Łamiblogu…
@miodziu
Jakiś czas temu Nasz Miły Gospodarz napisał, że Łamiblog nie jest Projektem Euler i ja też wolę poświęcić czas/uwagę na kwestie ręcznego rozwiązywania łamigłówek.
(ale jeśli czasem w wyniku działania programu pojawi się jakaś ciekawostka, to się nią tutaj podzielę ku ogólnej radości).
Niech mi będzie wolno zakrzyknąć:
„Panie i Panowie długopisy w dłoń!”.
„Długopisy”, bo tak jak napisałem wcześniej: gumować ołówka nie lubię.
Panie Gospodarzu, bawiłem się trochę programem i wpadła mi w oko taka ciekawostka.
P P T T T
P P P T Y
U U F T Y
U F F Y Y
U U F F Y
Startujemy z dowolnego pola i ruchem Króla szachowego odwiedzamy pozostałe pola i wstawiamy kolejne liczby naturalne 1-25.
Po wstawieniu wszystkich sumujemy liczby w poszczególnych pentominach.
Należy znaleźć trasę, dla której każda suma jest większa od 60.