Polska kwadratowa
Znajoma namówiła mnie do zamieszczenia poniższego zadania, co czynię z pewną taką wstrzemięźliwością, bo jest ono tzw. optimizerem, czyli dłubaniną dla wybrańców lub dla komputerów. Znajoma zmaga się z nim od pewnego czasu i chciałaby mieć pewność, że osiągnęła najlepszy – w tym przypadku najmniejszy – wynik.
Oto mamy Polskę pokratkowaną, czyli podzieloną na małe kwadraciki, a praktycznie narysowaną z grubsza, czyli z „kanciastymi” granicami, na kartce w kratkę.
Czarne kratki to największe miasta wojewódzkie.
Tę Polskę (całą) należy rozparcelować na kwadraty. Dzielić należy oczywiście tylko wzdłuż oznaczonych linii. A najważniejsze jest to, aby kwadratów było jak najmniej. Miasta powinny się znaleźć poza kwadratami, a więc pozostaną kwadracikami 1×1, ale nie są wliczane do końcowego minimum.
Żeby było ciekawiej i dziwniej dodam, że zadanie pochodzi z łamigłówkowych mistrzostw Francji. Dlaczego Francuzi dzielili Polskę – nie powiem. Nie podam także wyniku znajomej, ale jeśli w komentarzach pojawią się gorsze, czyli większe rozwiązania (wystarczy podać liczbę kwadratów), będę je uwalniał bezzwłocznie.
Komentarze
65
Napisałem program i uruchomiłem. Program oczywiście przeszukuje wszystkie możliwe podziały mapy na kwadraty, więc na pewno nie pominie najlepszego rozwiązania. Natomiast dzięki optymalizacji mam nadzieję, że program dość szybko będzie odcinał przeszukiwanie gałęzi, które nie mają szans wygenerować rozwiązania lepszego od już znalezionych.
W chwili obecnej najlepszy znaleziony podział zawiera 63 kwadraty (+ 7 kwadratów symbolizujących miasta). Nie potrafię ocenić, kiedy program skończy swe działanie.
PS. Pełny podział mapy przedstawię później, bo zakładam, że mogą pojawić się jeszcze lepsze rozwiązania.
Mam rozwiązanie z 60 kwadratami 🙂
Ooo… jak pisałem komentarz, to pojawiło się rozwiązanie z 57 kwadratami 😀
Ech… Cofam poprzednie dwa komentarze, bo przeoczyłem subtelny fakt, że w drugiej wersji programu dodałem wypisywanie wyniku, które nie uwzględnia już istniejących 7 miast.
Zatem mój obecny wynik, to 63 kwadraty 🙁
Nie uwalniam zawczasu Pańskich komentarzy, choć wyniki są za duże, bo informacja, że w szranki stanął komputer, mogłaby zniechęcić „pieszych” rozwiązywaczy.
Nawiasem mówiąc, mam wątpliwości, czy dożyję chwili, gdy komputer zakończy pracę :).
mp
Hehe… Rozumiem. Komputer pracuje, a ja co chwila wymyślam kolejne optymalizacje 🙂
Oczywiście, jako doświadczony algorytmik, życzę Panu, aby przeżył Pan ten program z nawiązką 🙂
PS. Tym razem mam już 58 kwadratów 🙂
55
Mam troszkę niżej: 58.
Mógłby Pan podpowiedzieć, do czego dążyć – może na przykład wyników powyżej 40 nie ma co podawać? A może ma wyjść 49 województw jak za starych czasów? 🙂
Antyp1958 jest już blisko minimum, które znam.
mp
15
Nie uwalniam, bo to chyba żart albo rozwiązanie innego zadania (może coś niejasno napisałem).
mp
Uwolniłem po wyjaśnieniach.
Może źle zrozumiałem reguły zadania, przeczytałem jeszcze raz i…. wszystko sie zgadza. Oto link do mojego rozwiązania (zajeło mi 5 minut, może jest lepsze jeszcze).
Z lenistwa, nie zaznaczałem kwadratów jednokratkowych… bo sa już zaznaczone:
http://s15.postimg.org/86se02g0b/Pok_1_1024x934_kl.jpg
Czytam i czytam… i chyba wiem już gdzie tkwi mój błąd, nie liczonymi kwadracikami 1×1 mogą być tylko miasta.
Ale swoja drogą powstało inne zadanie 🙂
„Wpisz w Polskę jak najmniej kwadratów tak, aby nie pozostał żaden większy niż 1×1” – chyba tak brzmi nowe zadanie z rozwiązaniem 15.
mp
Wbrew pozorom instrukcja do ‚mojego’ zadania nie jest trywialna.
Zasugerowałbym taką:
‚Wypełnij cała mapę kwadratami większymi od 1×1, tak by ich liczba była jak najmniejsza’.
P.S. Wiedząc o co chodzi, nie potrafię jednak ocenić, czy ta definicja jest optymalna 🙂
A może to podział na JOW-y?
W pierwszym podejściu mam 62, czyli powiedzmy średnio 😀
53
No dobra, poddaję się. Mam 57 kwadratów, mniej mi nie chce wyjść 🙁
52
Pani Olu, czy Pani uprawia „strzelectwo”:)?
mp
http://pokazywarka.pl/d53irr/
Śliczności:)
mp
PS Pani Olu, społeczeństwo się pyta, co oznacza gruba pionowa zielona kreska.
Nic takiego 🙂 To pozostałość po roboczym dzieleniu Polski na sektory. Ułatwiała mi pracę i liczenie, ile mam kwadratów w danym sektorze po poprawkach. Dzięki takim liniom (było ich więcej) nie musiałam liczyć wszystkiego od nowa.
Napisał Pan w jednym z komentarzy „minimum, które znam” – jakie jest to minimum?
Właśnie Pani, jako jedyna, osiągnęła to minimum.
Dodam, że jest kilka (nie wiem dokładnie ile – chyba koło 10) sposobów podziału Polski na 52 kwadraty. We wszystkich podziały płd. Polski są takie same, różnice występują tylko na Pomorzu :). Na mam pewności, czy podział na mniej niż 52 kwadraty jest niemożliwy.
mp
Też miałem 52 kwadraty. Jedno z możliwych jest poniżej
http://pokazywarka.pl/zru9wb/
Ponieważ znalazłem kilkanaście rozwiązań wykombinowałem, że zejście do 51 jest możliwe (ale chyba nie jest).
Francuzi dzielili Polskę w ramach swoich eliminacji do 19tych World Puzzle Championship – te mistrzostwa odbywały się właśnie w Polsce.
Ich rozwiązania można znaleźć tutaj:
https://math.berkeley.edu/~auroux/frwpc10/sol3.pdf
Oto zadanie dla wytrwałych z Puzelandu (Wiedza i Życie) 1/2000.
Zadanie polega na podzieleniu prostokąta z „otworami” (czarne pola) wzdłuż oznaczonych linii na jak najmniejszą liczbę kwadratów. Czarne pola nie mogą wchodzić w skład kwadratów; ponadto kwadraty nie powinny, oczywiście, zachodzić na siebie.
Rozwiązanie umieszczone w Puzelandzie 6/2000 zawiera podział na 39 kwadratów.
Znalazłem podział na 38 kwadratów.
http://pokazywarka.pl/i8lfwd/
Podział jest niemal identyczny z tym sprzed 19 lat (drobna różnica przy lewym dolnym rogu). Kwadratów jest jednak 39.
mp