Na Math Stack Exchange zadałem pytanie o najmniejszy region, który może zawierać wszystkie bezpłatne n-ominos .
Chciałbym dodać tę sekwencję do On-Line Encyclopedia of Integer Sequences, gdy będę mieć więcej terminów.
Przykład
Region dziewięciu komórek jest najmniejszym podzbiorem płaszczyzny, który może zawierać wszystkie dwanaście wolnych 5-omino , jak pokazano poniżej. (Wolny poliomino to taki, który można obracać i przerzucać.)
(Region dwunastokomórkowy to najmniejszy podzbiór płaszczyzny, który może zawierać wszystkie 35 wolnych 6-omino .)
Wyzwanie
Oblicz górne granice na najmniejszych obszarach płaszczyzny, które mogą zawierać wszystkie n-omino w funkcji n.
Taki stół zaczyna się:
n | size
--+-------
1 | 1*
2 | 2*
3 | 4*
4 | 6*
5 | 9*
6 | 12*
7 | 37
8 | 50
9 | 65
*These values are the smallest possible.
Przykład przesłania
1-omino: 1
#
2-omino: 2
##
3-omino: 4
###
#
4-omino: 6
####
##
5-omino: 9
#
#####
###
6-omino: 12
####
######
##
7-omino: <= 37
#######
######
######
######
######
######
Punktacja
Uruchom program tak długo, jak chcesz, i opublikuj listę górnych granic wraz z kształtami, które je osiągają.
Zwycięzcą zostanie uczestnik, którego tabela jest leksykograficzna najwcześniej (z „nieskończonością” dołączoną do krótszych zgłoszeń). Jeśli dwóch uczestników przedstawi te same wyniki, wygrywa wcześniejsze zgłoszenie.
Na przykład jeśli zgłoszenia są
Aliyah: [1,2,4,6,12,30,50]
Brian: [1,2,4,6,12,37,49,65]
Clare: [1,2,4,6,12,30]
wtedy Aliyah wygrywa. Bije Briana, ponieważ 30 <37, i bije Clare, ponieważ 50 <nieskończoności.
źródło
Odpowiedzi:
C # i SAT: 1, 2, 4, 6, 9, 12, 17, 20, 26, 31, 37, 43
Jeśli ograniczymy ramkę ograniczającą, istnieje dość oczywiste wyrażenie problemu w kategoriach SAT : każde tłumaczenie każdej orientacji każdego wolnego poliomino jest dużą koniunkcją; dla każdego poliomina tworzymy rozłączenie nad jego koniunkcjami; a następnie wymagamy, aby każde rozłączenie było prawdziwe, a całkowita liczba komórek była ograniczona.
Aby ograniczyć liczbę komórek, moja początkowa wersja zbudowała pełny sumator; potem użyłem sortowania bitonicznego do zliczania jednoargumentowego (podobnie do tej wcześniejszej odpowiedzi, ale uogólniony); w końcu zdecydowałem się na podejście opisane przez Bailleux i Boufkhada w efektywnym kodowaniu CNF ograniczeń logicznej liczby logicznej .
Chciałem, aby post był samodzielny, więc wykopałem implementację C # rozwiązania SAT z licencją BSD, która była najnowocześniejsza około 15 lat temu, zastąpiłem implementację listy NIH
System.Collections.Generic.List<T>
(zyskując współczynnik 2 w prędkości), grał w golfa od 50 kB do 31 kB, aby zmieścić się w limicie postu 64 kB, a następnie wykonał agresywną pracę nad zmniejszeniem zużycia pamięci. Ten kod można oczywiście dostosować do wyjścia pliku DIMACS, który można następnie przekazać do nowocześniejszych solverów.Znalezione rozwiązania
Znalezienie 43 dla n = 12 zajęło nieco ponad 7,5 godziny.
Kod Polyomino
Kod solvera SAT
Optymalność
Różne rozwiązania
Liczenie rozwiązań problemu SAT jest proste, choć czasem powolne: znajdujesz rozwiązanie, dodajesz nową klauzulę, która bezpośrednio je wyklucza, i uruchamiasz ponownie. Tutaj łatwo jest wygenerować klasę równoważności rozwiązań pod symetriami prostokąta, więc poniższy kod wystarcza do wygenerowania wszystkich różnych rozwiązań.
źródło
Aby rozpocząć proces, oto szybka (ale niezbyt optymalna) odpowiedź.
Wzór:
Weź trójkąt o długości n - 1, przyklej dodatkowy kwadrat do rogu i odetnij dolny kwadrat.
Dowód, że wszystkie n-ominos pasują:
Zauważ, że każde n-omino może zmieścić się w prostokącie o długości + szerokości co najwyżej n + 1.
Jeśli n-omino mieści się w prostokącie o długości + szerokości co najwyżej n, to ładnie pasuje do trójkąta (który jest połączeniem wszystkich takich prostokątów). Jeśli zdarzy się użyć kwadratu odcięcia, transpozycja będzie pasować do trójkąta.
W przeciwnym razie mamy łańcuch z co najwyżej jedną gałęzią. Zawsze możemy dopasować jeden koniec łańcucha do dodatkowego kwadratu (udowodnij to za pomocą obudowy), a resztę zmieści się w prostokącie o długości + szerokości co najwyżej n, zmniejszając się do powyższego przypadku.
Jedyny przypadek, w którym powyższe nie działa, to przypadek, w którym używamy zarówno dodatkowego kwadratu, jak i kwadratu odcięcia. Jest tylko jedno takie n-omino (długie L), i to pasuje do transponowanego trójkąta.
Kod (Python 2):
Stół:
źródło
C #, wynik: 1, 2, 4, 6, 9, 12, 17, 20, 26, 31, 38, 44
Format wyjściowy programu jest nieco bardziej kompaktowy.
Wykorzystuje to rozstawione losowe podejście i zoptymalizowałem nasiona. Egzekwuję ograniczenie ramki granicznej, które jest prawdopodobne i zgodne ze znanymi danymi dla małych wartości n. Jeśli to ograniczenie jest rzeczywiście ważne, to wtedy
1, 1, 2, 2, 2, 6, 63, 6
.Demo online
źródło
Chciwe umieszczanie w losowej kolejności
Znalezione regiony podano poniżej, a także program rdzy , który je wygenerował. Wywołaj go z parametrem wiersza poleceń równym n, którego chcesz wyszukać. Do tej pory podniosłem go do n = 10. Pamiętaj, że nie jest jeszcze zoptymalizowany pod kątem prędkości, zrobię to później i prawdopodobnie znacznie przyspieszy.
Algorytm jest prosty, tasuję poliomino w (rozstawionej) losowej kolejności, a następnie umieszczam je pojedynczo w pozycji z maksymalnym możliwym zachodzeniem na region do tej pory. Robię to 100 razy i generuję najlepszy wynikowy region.
Regiony
Program
Uwaga: wymaga co noc, ale po prostu zmień wysiew, aby się go pozbyć, jeśli ci zależy.
źródło