Bei Math Stack Exchange stellte ich eine Frage zu der kleinsten Region, die alle freien n-Ominos enthalten kann .
Ich möchte diese Sequenz zur Online-Enzyklopädie ganzzahliger Sequenzen hinzufügen sobald ich weitere Begriffe habe.
Beispiel
Eine Region mit neun Zellen ist die kleinste Teilmenge der Ebene, die alle zwölf freien 5-Ominos enthalten kann , wie unten dargestellt. (Ein freies Polyomino kann gedreht und gedreht werden.)
(Eine zwölfzellige Region ist die kleinste Teilmenge der Ebene, die alle 35 freien 6-Ominos enthalten kann .)
Die Herausforderung
Berechnen Sie die Obergrenzen für die kleinsten Bereiche der Ebene, die alle n-Ominos als Funktion von n enthalten können.
Ein solcher Tisch beginnt:
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.
Beispiel Einreichung
1-omino: 1
#
2-omino: 2
##
3-omino: 4
###
#
4-omino: 6
####
##
5-omino: 9
#
#####
###
6-omino: 12
####
######
##
7-omino: <= 37
#######
######
######
######
######
######
Wertung
Führen Sie Ihr Programm so lange aus, wie Sie möchten, und veröffentlichen Sie die Liste der oberen Schranken zusammen mit den Formen, mit denen die einzelnen Schranken erreicht werden.
Der Gewinner ist der Teilnehmer, dessen Tabelle lexikographisch am frühesten ist (wobei "unendlich" an die kürzeren Einreichungen angehängt ist.). Reichen zwei Teilnehmer die gleichen Ergebnisse ein, gewinnt die frühere Einreichung.
Zum Beispiel, wenn die Einreichungen sind
Aliyah: [1,2,4,6,12,30,50]
Brian: [1,2,4,6,12,37,49,65]
Clare: [1,2,4,6,12,30]
dann gewinnt Aliyah. Sie schlägt Brian, weil 30 <37, und sie schlägt Clare, weil 50 <unendlich.
quelle
Antworten:
C # und SAT: 1, 2, 4, 6, 9, 12, 17, 20, 26, 31, 37, 43
Wenn wir den Begrenzungsrahmen einschränken, gibt es einen ziemlich offensichtlichen Ausdruck des Problems in Bezug auf SAT : Jede Übersetzung jeder Orientierung jedes freien Polyominos ist eine große Konjunktion; für jedes Polyomino bilden wir eine Disjunktion über seine Konjunktionen; und dann muss jede Disjunktion wahr sein und die Gesamtzahl der verwendeten Zellen war begrenzt.
Um die Anzahl der Zellen zu begrenzen, hat meine ursprüngliche Version einen Volladdierer erstellt. dann habe ich die bitonische Sortierung für das unäre Zählen verwendet (ähnlich zu dieser früheren Antwort, aber verallgemeinert); Schließlich entschied ich mich für den von Bailleux und Boufkhad beschriebenen Ansatz der effizienten CNF-Codierung von booleschen Kardinalitätsbeschränkungen .
Ich wollte den Post in sich geschlossen machen, also habe ich eine C # -Implementierung eines SAT-Lösers mit einer BSD-Lizenz ausgegraben, die vor etwa 15 Jahren auf dem neuesten Stand war, und die NIH-Listenimplementierung durch
System.Collections.Generic.List<T>
(mit einem Faktor von +) ersetzt 2 in der Geschwindigkeit), spielte es von 50kB auf 31kB herunter, um in das 64kB-Post-Limit zu passen, und arbeitete dann aggressiv an der Reduzierung des Speicherverbrauchs. Dieser Code kann natürlich angepasst werden, um eine DIMACS-Datei auszugeben, die dann an modernere Löser übergeben werden kann.Lösungen gefunden
43 für n = 12 zu finden, dauerte etwas mehr als 7,5 Stunden.
Polyomino-Code
SAT-Solvercode
Optimalität
Eindeutige Lösungen
Das Zählen von Lösungen für ein SAT-Problem ist einfach, wenn auch manchmal langsam: Sie finden eine Lösung, fügen eine neue Klausel hinzu, die dies direkt ausschließt, und führen sie erneut aus. Hier ist es einfach, die Äquivalenzklasse von Lösungen unter den Symmetrien des Rechtecks zu generieren, sodass der folgende Code ausreicht, um alle unterschiedlichen Lösungen zu generieren.
quelle
Um den Prozess in Gang zu bringen, finden Sie hier eine schnelle (aber nicht sehr optimale) Antwort.
Muster:
Nehmen Sie ein Dreieck mit der Länge n - 1, kleben Sie ein zusätzliches Quadrat auf die Ecke und schneiden Sie das untere Quadrat ab.
Beweis, dass alle n-Ominos passen:
Beachten Sie, dass jedes n-Omino in ein Rechteck mit einer Länge + Breite von höchstens n + 1 passen kann.
Wenn ein n-Omino in ein Rechteck mit einer Länge + einer Breite von höchstens n passt, passt es gut in das Dreieck (das ist die Vereinigung aller dieser Rechtecke). Wenn das abgeschnittene Quadrat verwendet wird, passt es beim Transponieren in das Dreieck.
Ansonsten haben wir eine Kette mit höchstens einer Filiale. Wir können immer ein Ende der Kette in das zusätzliche Quadrat einpassen (beweisen Sie dies mit der Fallarbeit), und der Rest passt in ein Rechteck mit einer Länge + Breite von höchstens n, reduziert auf den obigen Fall.
Der einzige Fall, in dem das Obige nicht funktioniert, ist der Fall, in dem wir sowohl das zusätzliche Quadrat als auch das abgeschnittene Quadrat verwenden. Es gibt nur einen solchen N-Omino (das lange L), und dieser passt in das transponierte Dreieck.
Code (Python 2):
Tabelle:
quelle
C #, Score: 1, 2, 4, 6, 9, 12, 17, 20, 26, 31, 38, 44
Das Ausgabeformat des Programms ist etwas kompakter.
Hierbei wird ein Zufallsansatz mit Startwerten verwendet, und ich habe die Startwerte optimiert. Ich erzwinge eine Begrenzungsrahmenbedingung, die plausibel ist und mit den bekannten Daten für kleine Werte von n übereinstimmt. Wenn diese Einschränkung tatsächlich gültig ist, dann
1, 1, 2, 2, 2, 6, 63, 6
.Online-Demo
quelle
Gierige Platzierung in zufälliger Reihenfolge
Die gefundenen Regionen sowie der Rost sind unten angegeben , aus dem sie entstanden . Rufen Sie es mit einem Befehlszeilenparameter auf, der dem n entspricht, bis zu dem Sie suchen möchten. Ich habe es bis jetzt auf n = 10 gebracht. Beachten Sie, dass es noch nicht für die Geschwindigkeit optimiert ist. Ich werde das später tun und wahrscheinlich die Dinge viel beschleunigen.
Der Algorithmus ist unkompliziert. Ich mische die Polyominos in einer (gesetzten) zufälligen Reihenfolge und platziere sie dann einzeln an der Position mit der größtmöglichen Überlappung mit der Region, die bisher möglich war. Ich mache das 100 Mal und gebe die beste resultierende Region aus.
Regionen
Programm
Hinweis: Erfordert jede Nacht, aber ändern Sie einfach die Aussaat, um das loszuwerden, wenn es Sie interessiert.
quelle