Auf dieser Seite will ich alle Programme zusammenstellen, die mir Leute zur Lösung des c't-Puzzles aus dem Artikel "Zusammengewürfelt, Puzzles mit dem Computer lösen" von Harald Bögeholz, c't 7/2003, Seite 230 (hier ist der Artikel, siehe auch www.ctpuzzle.de) zugeschickt haben. Wenn auch Dein Beitrag hier erscheinen soll, schick ihn mir bitte an epsilon0@ixcase.com und schreibe dazu, dass Du mit der Veröffentlichung des Quelltextes auf dieser Seite einverstanden bist. Ausserdem wäre es nett, eine ungefähre Angabe der Laufzeit (mit Beschreibung des entsprechenden Systems und Compiler, evtl. die Switches?) anzufügen, und einen Namen/Pseudonym, den ich für diese Seite verwenden kann, und evtl. noch die Angabe einer eMail-Adresse, die ich einigermassen Spamroboter-sicher auf die Seite eintragen werde. Ein kurzer Text mit einigen Erläuterungen werde ich auch gerne hier veröffentlichen. Für Diskussionen einzelner Programme empfehle ich weiterhin das Heise-Forum
Programm von Epsilon0 / Uli Schuhmacher
Mein eigener Versuch, nicht sehr schnell, aber mit 560 Zeilen auch nicht sehr kompliziert, X-Trick, 1,3 Mrd. Aufrufe.
Programm von elmy / Oliver Ehli
Ein Generator, der ein 19 Tausend Zeilenmonster erzeugt, dass dann recht schnell ist. Interessante Idee und bis jetzt einmalig.
Programm von OFH / Oliver Faulhaber
3D-Oberfläche in Java3D
recht schnelle Version, mit einer kleinen Statistik
Programm von Tobias Glasmachers
ziemlich schnelle Variante, mit ausführlichen Erläuterungen
Programm von Horst Raap
einer der wie ich finde sehr interessanten Versuche, die Anzahl der benötigten Tests möglichst weit zu reduzieren, hier bis 350 Mio. Hat eine Abbruchbedingung per Paritätscheck.
Programm von Ralf Kleberhoff
mit ausführlichem Begleittext
Programm von Jochen Hoenicke
ein weiterer sehr schneller Kandidat...
2. Programm von Jochen Hoenicke
und als Bonus noch eine Version mit nur 225 Mio gelegten Steinen!
Programm von Jens Kunerle / Snej
Gemischtes Programm aus C++ und Assembler
Programm von Arnold Wendl
Puzzlelöser und graphische Oberfläche zur Auswahl bestimmter Lösungen, findet auch die einzige "echte" c't-Puzzle Lösung.
Programm von Ulrich Krämer
Flexibles Programm, löst das Puzzle auch für andere Geometrien (2x5x6, C-förmig, T-förmig, etc.)
Programm von Thomas Althaus
schnelles Programm mit Multithreading
Programm von Leopold Toetsch
mit einigen interessanten Tricks im Detail
Programm von Heinz Repp
noch ein gemischtes C / Assembler Programm
Programm von Omoikane / Peter Schaeffer
mit einigen Bedingungen um die Rekursion vorzeitig abbrechen zu können
Programm von Dominik Raddatz
eine Version mit Multithreading und eine ohne, auch einige ungewöhnliche Tricks sind dabei
6:20 Minuten auf meinem Duron 850 MHz
Mail: epsilon0 at ixcase dot com
Hier ist erstmal mein Programm, das ich für den Wettbewerb eingereicht habe. Ich habe in letzer Sekunde noch den "X-Trick" reingehackt und bin so auf einem Duron 850 MHz bei 1.365.232.379 Legeoperationen auf etwa 380 Sekunden gekommen; für viele Verbesserungen hat die Zeit nicht mehr gereicht, meine Freunde wollten wirklich langsam zu dieser Party und haben nicht eingesehen, dass hier unbedingt noch was verbessert werden muss... es sind etwas weniger als die normalen 1,5 Mrd Legeoperationen geworden, da ich eine Bitreihenfolge verwendet habe, die sich spiralförmig von aussen nach innen in den 3x4 Schichten durcharbeitet, ausserdem habe ich die Positionen des X/+ - Teils ausgewählt, die möglichst weit vorne in der Bitreihenfolge liegen. Compiler Intel-C++ 7.1, gnu Makefile ist im Archiv dabei. Ausserdem habe ich noch zwei Programmversionen, die jeweils das halbe Problem lösen und sich parallel starten lassen, man muss dann nur noch die Lösungszahlen addieren; für mehr Hyperthreading hat die Zeit nicht gereicht.
3:08 Minuten auf P3 1 GHz
Mail: elmy at acm dot org
das binary fastSolver benoetigt auf meinem p3-1000 exakt 188s im single user mode unter linux, mit gcc. (icc binary ist langsamer und ausserdem braucht icc ewig zum optimieren...) fastSolver ist ein generiertes programm, bei dem fuer semtliche koordinaten saemtliche loops ueber teilchen positionen ausgeschrieben werden. das sind 19600 zeilen code ;-} dabei ist kein wissen ueber suchbaeume oder loesungen involviert. es verwendet aber, was wohl jetzt x-trick heisst und braucht daher 1.46 mrd. rekursionen. ps. ich kann dein programm nicht uebersetzen, weil du msasm-syntax verwendet hast. sobald ich das in at&t format gebracht hab, sage ich bescheid wie schnell es hier gelaufen ist..
Tut mir Leid wegen der inkompatiblen asm - Sache, aber gegen Ende hat echt die Zeit gedrängt...
3D-Oberfläche
Mail: ofh3 at hotmail dot com
Webseite: http://www.anifun3.de/gallery/
Hallo Uli, anbei mein Beitrag zum Wettbewerb. Das Programm ist in Java implementiert und hat eine 3D-Oberfläche, die auf Java3D basiert. Minimiert man das Fenster, dann pausiert die 3D-Renderengine und der Lösungsalgorithmus schafft dann etwa 116 Lösungen/sec auf einem P3/800 (Mit aktiver Renderengine entsprechend weniger). Das Programm ist für die Wettbewerbsverhältnisse lediglich rough optimiert und benötigt ca. 4 Mrd. Legeoperationen (Combos). Aber wenn man mal bedenkt, dass ich mit 40 sec/Lösung begonnen habe... ;) Damit gehört das Programm natürlich nicht in die Top-Liga, aber eigentlich habe ich ja mitgemacht, weil mich die Visualisierung des Lösungsalgorithmus und auch die Darstellung von ein paar hunderttausend Lösungen reizte: Die Aufgabe ist nämlich wie geschaffen für eine Demonstration von Java3D bzw. von AniFun3: d.h. die Vorgehensweise des Algorithmus kann in "Echtzeit" mitverfolgt werden. Der mitgelieferte Backtracing-Algorithmus beginnt mit Puzzleteil 1 links vorne. Von dort aus wird das Puzzle nach oben, hinten und rechts aufgefüllt. Zur Oberfläche: Die 3D-Szene wurde in einem grafischen 3D-Editor (AniFun3) erstellt und der Lösungsalgorithmus über die Programmierschnittstelle eingeklinkt. Bei der angehängten Datei handelt es sich um ein selbstextrahierendes RAR-Archiv. Das Archiv enthält alle notwendigen Komponenten incl. Java 3D für Windows und DirectX(6+). Eine Installation ist nicht notwendig. Das Programm kann auch auf Linux ausgeführt werden, wenn die Java-Installation vorher mit Java3D erweitert wurde (www.j3d.org). Java3D für Linux benötigt eine OpenGL-fähige Grafikkarte.
3:02 Minuten auf P4 1.7 GHz
Mail: dgutekunst at gmx dot de
hier mein c't Programm. Ausführungszeit auf meinem P4 1.7 GHz, 256 MB DDR-SDRAM: 182s Executable ist dabei (Linux!!!). // icc -O3 -tpp7 -march=pentium4 -ip -ipo -Ob2 -o ct ct.cpp cbitpart.cpp // su (login as root) // time nice -n -15 ./ct (das sagt eigentlich alles) In ct_invoc_dump ist der Output einer ausführlicheren Version meines Programmes (falls sie die genaue Anzahl der Rekursionsaufrufe interessiert).
??:?? Minuten auf ??
Mail: Tobias.Glasmachers at gmx dot de
Hier ist mein Programm (Source) sowie eine HTML-Beschreibung des Algorithmus, die Du gerne in Deine Web-Seite einbauen kannst! Bitte verlinke auch meine Sourcecode. Hast Du ein Programm, das die Version mit Syntax-Highlighting erzeugt? Ich denke es sind einige Ansätze dabei, die meine Lösung von andern unterscheiden, das macht das Ganze vielleicht interessant. Tobi
Das Syntax-Highlighting mache ich von Hand, ganz schöne Arbeit... nein, im Ernst, es ist gnu source-highlight
ca. 17 Minuten auf Athlon 1 GHz
Mail: raap at epost dot de
Anbei meine Version zur Lösung des Puzzles. Ist nicht sehr schnell (ca. 17 min auf Athlon 1000), probiert aber nur 356 Mio. Stellungen durch. Folgende "Tricks" sind drin: - Hash-Tabelle merkt sich Wiederholungen von Stellungen (10% Gewinn) - Es wird auf den unteren Rekursionsebenen entweder das Loch mit den wenigsten Möglichkeiten aufgefüllt oder aber das Teil an alle möglichen Positionen gesetzt, welches die wenigsten Möglichkeiten hat. - Es wird ein "Paritätscheck" gemacht. Wenn man sich die Teilwürfel abwechselnd als schwarz und weiß gefärbt vorstellt, belegt jedes Teil immer eine bestimmte Anzahl davon, z.B. ist die Differenz beim X-Teil zwischen belegten weißen und schwarzen immer 3. Die Gesamtdifferenz am Ende muss aber 0 ergeben. Damit lassen sich etliche unslösbare Stellungen ohne durchprobieren erkennen.
3:02 Minuten auf Athlon XP 2000+
Mail: ralf03 at kleberhoff dot de
Anbei der Quelltext meines Wettbewerbsbeitrags und ein heute erstellter Text mit den darin eingebauten Tricks. Nachdem die Cracks heute den X-Trick erklärt haben, habe ich gemerkt, dass ich ihn doch nicht richtig verstanden/geraten hatte, dass da also noch einiges Potenzial gewesen waere. Aber zu spaet. Zeit auf Athlon XP2000+ (Intel-Compiler): 182 sec (Mal sehen, was rauskommt, wenn ich den X-Trick richtig einbaue) Gruss, Ralf
2:09 Minuten auf Athlon 1700+
Mail: hoenicke at informatik dot uni-oldenburg dot de
Eine Beschreibung des Algorithmus steht im am Anfang von ctpuz.c im Kommentar. Der Text sollte vielleicht direkt auf der Webseite stehen. Laufzeit: Athlon 1700+: 129 sec. P4 1800 : 146 sec. P-III 450 : ca. 8 min. PS: ich werde gleich auch noch meine 225-Mio Stellungen Variante verpacken und in einer zweiten Mail schicken. Sie ist zwar mit 5 min Laufzeit auf P4-1800 relativ langsam, aber dennoch interessant, weil sie komplett andere Datenstrukturen benutzt.
4:58 Minuten auf P4 1.8 GHz
Mail: hoenicke at informatik dot uni-oldenburg dot de
PS: ich werde gleich auch noch meine 225-Mio Stellungen Variante verpacken und in einer zweiten Mail schicken. Sie ist zwar mit 5 min Laufzeit auf P4-1800 relativ langsam, aber dennoch interessant, weil sie komplett andere Datenstrukturen benutzt. hier das versprochene zweite Programm. Wieder ist die Beschreibung am Anfang der C-Datei. Das interessante an dieser Version ist, dass der Algorithmus nicht die Teile sucht, die noch in den Würfel passen, sondern in jedem Schritt die Teile entfernt, die mit dem gerade gelegtem Teil in Konflikt stehen. Laufzeit: Athlon 1700+: 378 sec. P4 1800 : 298 sec. Es fällt auf, dass hier der P4 seine MHz voll ausspielen kann.
<999 Sekunden auf P3 450 MHz
1.Das Programm besteht aus einem Mix von c++ (Initialisierung) und asm
(Rekursion) und braucht auf einem PIII-450: <999 Sekunden
Compiler von Borland C++5, tasmx-Compiler , tlink32-Linker
c-Compiler Optionen: ???
tasmx Optionen: -ml -m3
tlink32 Optionen: tlink32 /v /c /S:7800000 /Lc:\bc5\lib;c:\bc5\include
\bc5\lib\c0x32 p2 puzz,puzz,puzz,cw32 import32
(die Groesse des Stacks ist wichtig)
2.Brute-Force Bitfuellmethode:
Das Programm verwendet den X-Trick nicht und ist dementsprechend langsam
Das Symmetrieteil ist das aus 5 Bit bestehende raeumliche Teil.
Die Permutation ist so gewaehlt das zuerst 2 Schichten des 3x4x5 Quaders
gefuellt werden, dann eine Schicht des 3x3x4 Quaders und zum Schluss der
3x3x3 Wuerfel immer von der schmalsten Seite her.
Bei Bit 33 muessen die langen Teile alle eingefuegt sein [solve32b]
Ein Test auf Rekursionsabbruch (abbruch64 bzw. abbruch32) macht alles nur
langsamer :(
Der Test untersucht ob evtl. ein Bit zugebaut wird. (Ich dachte das waere der
X-Trick und wollte ihn mit aller Macht einbauen).
3.Das erste freie Bit (nb) wird gesucht
Je nachdem welche der drei Richtungen ab nb noch frei sind werden die zu
testenden Teile ausgesucht und getestet (groesster Geschwindigkeitszuwachs -
doppelt so schnell)
Dazu folgende Datenstruktur zu jedem freien Bit und jedem verwendbaren Teilset
(~110MB)
Teile die genau in xyz x xy y yz z zx x Richtung fortgesetzt werden
zugehoerige Pointer:
Dann wenn - verbaut: ------------------
Dann wenn x verbaut: ------
Dann wenn y verbaut: ------
Dann wenn z verbaut: ------
Dann wenn xy verbaut: -
Dann wenn xz verbaut: -
Dann wenn yz verbaut: -
Dann wenn xyz verbaut:
4.Der zusaetzliche Symmetriehack - das Erzeugen von gespiegelten Loesungen
(xyz==345)
Es geht um Teil Nr5 und Nr9 auf dem ct Puzzle-Bild (Numerierung ab 1)
Symmetrieteil ist 5, d.h. 144 Ansichten ganz weit hinten
man kann Paare erzeugen wie folgt: fuer eine Ansicht t1 von Teil5
spiegele t1 an der yz-Ebene -> t2
drehe t2 um z-Achse (180 Grad) -> t3
drehe t1 um z-Achse (180 Grad) -> t4
Entweder ist (t1,t2) oder (t1,t3) vorhanden
Man entscheidet sich nun bewusst fuer diejenige der beiden
Paarkombinationen (t1,t2) bzw. (t3,T4) welche weiter hinten liegt
Jetzt kann man fuer jede Ansicht von Teil9 waehlen ob man diese oder die
an der yz-Ebene gespiegelte Version nimmt: -> die hintere
(Teil5 und die anderen Teile gehen dann in ihre gespiegelte Lagen ueber
und die Anzahl der Loesungen aendert sich nicht.)
Werden die Teile mitprotokolliert muss man bei einer Loesung sehen ob
Teil9 gespiegelt wurde. Wenn ja mus die gesamte Loesung nochmal
gespiegelt werden um eine richtige Loesung zu erhalten.(Kein Problem bei
nur 410.000 Loesungen im Gegensatz zu 1.000.000.000 Legeoperationen)
Leider bringt er nur 3% Geschwindigkeitszuwachs :((
5.Der asmTeil ist eine fast 1:1 Umsetzung der entsprechenden C-Funktion, da mein
Compiler nur langsamen Schrott erzeugt
Mischung aus Löser und graphischer Oberfläche zur Anzeige bestimmter Lösungen
Mein Schwerpunkt war die Frage, wie finde ich denn nun in all den berechneten Lösungen diejenige heraus, welche die Beschriftung richtig anzeigt. "gefundene_loesung.bmp" zeigt die erfolgreiche Suche. 3D-Betrachtung (mit rotieren, ausblenden einzelner Bausteine, die übrigens an einem CAD-system modelliert wurden) wird letztendlich mit einem sehr einfachen OpenGL-Standardviewer (der auch fleißig UNICODE benutzt, und deshalb nicht unter WINDOWS-98 laufen soll) dargestellt, gestartet mit dem Startknopf ganz rechts unten. Ein paar Informationen stehen in der Datei info.txt, das Fragezeichen in der Menüleiste von ct_puzzle_select.exe ist auch zu empfehlen. Ach ja, eigentlich suche ich noch jemanden, der aus diesem C-Programm rtd.c (sicherlich sehr, sehr eigenwillig, z. Bsp. ohne Resource-Datei , minimalst dukumentiert) ein AcitveX-MFC-Programm macht, welches im Intranet als 'eingebundener Viewer' in Webseiten genutzt werden kann, und das natürlich ohne den Quellcode wesentlich zu ändern oder zu erweitern.
90:00 Minuten auf P4 mit ?? MHz
Mail: ulrich dot kraemer at gmx dot de
Das Programm ist zwar nicht das schnellste, 1.5 Std auf einem P4 mit WinXP, dafür aber sehr flexible. Die Hauptinformationen werden aus der "MainConfig.ini" gelesen Die mitgelieferte "MainConfig.ini" verweist standardmässig auf die "Puz_CT_345.ini". Diese enthält die Konfiguration für den 3*4*5 Block. Konfigurationen für die folgende Lösungen sind enthalten. Auf der Heise Seite vorgestellte Lösungen Puz_CT_345.ini -> Quader bestehend aus 3*4*5 Puz_CT_256.ini -> Quader bestehend aus 2*5*6 Puz_CT_C.ini -> Die Lösung, die ein C darstellt Puz_CT_T.ini -> Die Lösung, die ein T darstellt Puz_CT_Pyramide.ini -> Die Pyramide mit 5*5 auf den untersten beiden Ebenen Ein anderes Puzzle Puz_TCube.ini -> 54 Steine, die aus je 4 Würfeln, die als T angeordnet sind, bestehen, müssen in einen 6*6*6 Würfel Die alternativen Konfiguration können zur Laufzeit geladen oder beim Start als Parameter übertgeben werden (Konfigurationsdatei auf das Programmicon ziehen). Der "Start"-Button Startet den Ablauf. Weitere Informationen (bei eventuellem Interesse) stehen in der Readme.txt P.S. Der komplette Sourcecode inklusive Komentare, wenn vorhande, ist in Englisch gehalten.
4:30 Minuten auf Dual Celeron 2*504 MHz
Mail: Dr dot Thomas dot Althaus at gmx dot de
anbei mein Beitrag zum Wettbewerb. Das Binary wurde für Windows XP / 2000 mit Visual C++ 6.0 und Microsoft Assembler 6.15 übersetzt. Interessante Features: - Laufzeit auf (Dual) Celeron mit 504 MHz: 4:30 min - Multithreaded : Mutterthread + 2 Worker Threads (ideal für 2 Prozessor-Maschinen) - Rekursive Anlegefunktion ist in 80x86 Assembler handcodiert (kein MMX, kein SSE2) - Sehr einfach gehaltener Algorithmus: + -Teil vorlegen und bei symmetrischer Entartung ein weiteres Teil hinzufügen und Symmetrien beseitigen, der Rest ist "Brute Force" - Sollte auf P4 linear mit dem Takt skalieren (keine Hashtables), Hyperthreading geeignet - Erwartete Zielzeit (auf P4@3066MHz) 117.8 Sekunden - x, x für den Hyperthreadingboost ;-)
ca. 5 Minuten auf Athlon 800 MHz
Mail: lt at toetsch dot at
- Das Programm ist die Wettberwerbsversion *erweitert* um den X-Trick und den Loch-Check (O-Trick). Die Wettbewerbsversion brauchte ~16 Minuten, diese rennt jetzt mit ~5 Minuten jeweils auf Athlon 800, i386/linux, gcc 2.95.2. - Ein Lochcheck testet vorab auf 2-Bit Löcher - Interessant sind wahrscheinlich die and-Checks, die ich so noch nicht gesehen habe. An bestimmten Positionen (z.B. oben/hinten kann nur in eine Richtung gesetzt werde, diese Bits müssen frei sein. Diese Checks gibt es global und per Teil. - Weiters bringt die used_list (eine and-Liste per Position/used-Kombination) einiges. - Teile und Löcher werden klassifiziert (TYPS), 3 Bits - 8-fache Teileliste scheint am Besten zu funktionieren - Lösungsvektor (und Teile) sind 0-verschoben, das erste (implizite) Bit ist auch nach rechts verschoben. - Schliesslich ist für die 60-Bitvariante noch der o-Trick (Lochcheck) eingebaut, bringt auch noch ~9%. ohne X-Trick 2.22 Gtrys 400/s, 16m (aber mit allen and-Checks) mit X: 1.465 Gtrys, 857/s, 7m56 (alles andere aus) loch_check: 1.162 Gtrys, 980/s, 6m56 P1, typs=3: 995/s, 6m50 and/Teil: 1105/s, 6m09 and/Global: 1.114 Gtrys 1087/s, 6m14 [1] any, used_list: 821 Mtrys 1184/s, 5m43 (164 64-bit, 657 32bit) next[i] ~same loch_maske_64 724 Mtrys 1277/s 5m18 no and_list_l 735 Mtrys 1289/s 5m16 [1] Eventuell schlecht alignte Jumps. Hat eigentlich schon wer hingewiesen, daß unalignte Jump-Targets in engen Schleifen bis zu 50% Performance kosten können? (Vielleicht ist hier ein neuerer Compiler schon besser). PS: Durch die vielen Versuche ist der Sourcecode absolut hässlich, ich bitte um Vergebung ;-)
17:00 Minuten auf PII 233 MHz
Mail: Heinz dot Repp at online dot de
ich schicke hier NICHT die offiziell eingereichte Programmversion - die war noch ziemlich kryptisch und unflexibel, aber zum 30.4. immer noch die schnellste, die ich hatte, brauchte 36% länger und hatte ziemlich genau 1.7 Mrd Plazierungen - sondern eine, in die ich schon Anregungen aus Forumsbeiträgen vom Mai eingearbeitet habe: die Symmetrien werden soweit möglich beim 'x' weggenommen - ich hatte vorher das von mir 'Q' genannte Teil mit 576 Möglichkeiten genommen -, und vor jeder mit einer 'x'-Lage gestarteten Suche werden alle mit dieser kollidierenden Lage schon vorher entfernt; in den Assemblerteil habe ich deine <32-Bit-Optimierung eingebaut - ich hatte zwar vorher schon eine <32-Bit-Routine, aber aus anderen Gründen, und die Integer-Beschränkung wieder herausgenommen, weil ich die Routine dann auch für >32 Bit genommen aund außerdem angenommen habe, daß die Optimierung nicht viel bringen würde, weil die Zahl der <32-Bit-Aufrufe deutlich in der Minderzahl ist, jetzt habe ich aber gefunden, daß das völlig verlustfrei einzubauen ist, weil eine <32-Abfrage ohnehin für den Bitscan-Befehl nötig ist und dann doch ganze 11% Zeitersparnis bringt! ich verwende unter anderem noch: - statt Teile als belegt zu kennzeichnen und dann jedesmal zu überprüfen verwende ich ein Array, in dem die Teile permutiert werden; dadurch stehen immer nur Teile zur Auswahl, die noch nicht verwendet wurden. Die Abfrage entfällt, dafür muß die Permutation gewartet werden. Trotzdem bringt das 23% weniger Laufzeit - ich erstelle für jedes Bit und Teil eine Liste der Lagen, für die das das höchstwertige ist. Dadurch muß ich in jeder Rekursionsstufe nur Lagen aus dieser Liste überprüfen, das sind im Schnitt vielleicht 5 bis 6 statt mehrere hundert. Also bei dieser Nicht-Contest-Version wurde der Assemblerteil mit MASM 6.13 ohne spezielle Optionen (nur der .686p im Quelltext), das C-Programm mit dem Borland C++ Compiler bcc32 aus den Commandline Tools 5.5 mit allem, was die Optimierungen so hergeben (-6 -O -O2 -Oc -OS -Ov -DHIGHSPEED: bringt aber alles nix, weil nur die Rekursion zeitkritisch ist ;-), kompiliert und beides mit dem Borland-Linker gelinkt. Es kommt auf 1380724348 Plazierungen und auf meinem P II 233 auf 17'00" (meine offizielle Version hatte 1700174647 Plazierungen und brauchte 23'02"). Dein Programm braucht auf meinem System übrigens 17'30". Veröffentlichen kannst du gerne alles, ich habe nichts dagegen. Mal sehen, ob wir gemeinsam noch weiter kommen ...
4:56 Minuten auf P4 2.2 GHz
Mail: ps1 at informatik dot uni-ulm dot de
Hier meine (leider nicht konkurrenzfaehige) Loesung zum CT-Puzzle (zum
Veroeffentlichen auf Deiner Webseite).
Laufzeit (gcc-2.95 -O2) bei 563M Stellungen:
Tuleron 1400 5:47
P4 2200 4:56
ct295 Binary
ctw.cc Sourcecode fuer die endgueltige Version
fct.cc Sourcecode zum Testen von Parametern (per #define am Anfang setzen)
Verwendete Optimierungen:
- Angepasste Datenstrukturen, werden z.T. zur Laufzeit angepasst. Z.B. werden
Teile, die auf dem aktuellen X-Teil liegen, aus den Listen herausgenommen.
- Memorieren der bereits erechneten Stellungen bis Rekursionstive 5, um
beim erneuten Auftreten diese nicht mehr berechnen zu muessen. Dazu wurde die
STL (map) verwendet.
- Fruehzeitiger Abbruch der Rekursion, wenn Felder existieren, die nicht
mehr belegt werden koennen. Dazu wird fuer die naechsten 24 Positionen getestet,
ob noch ein Teil existiert, welches kollisionsfrei dort abgelegt werden kann.
- Leicht abgewandelter X-Trick. Das X-Teil wird zuerst gelegt und dann mit den
restlichen 11 Teilen wie in dem CT-Artikel verfahren. Da das X-Teil !NICHT! das
Symetrieteil ist, muss alles 40-mal durchgerechnet werden (Ich bin leider nicht
auf den Trick mit der Paralellisierung der Felder gekommen).
Da durch diesen Trick bei den letzten Vorbelegungen des X-Teils die
anderen Optimierungen nicht mehr greifen, wird das Feld beim 28. Teil
umgedreht. Dabei muessen leider die gespeicherten Positionen verworfen werden.
- Ab dem 28. Teil wird in jedem Schritt zusaetzlich getestet, ob das Symetrieteil
(der 4-er) noch gelegt werden kann, ansonsten wird die Rekursion abgebrochen.
In fct.cc hab ich noch verschiedene andere Sachen getestet, die aber nichts
gebracht haben:
- Abbruch der Rekursion, wenn ein noch nicht verwendetes Teil nicht mehr
gelegt werden kann.
- Andere Reihenfolgen bei der Nummerierung der Felder.
- Verschiedene Teile als Symetrieteil und verschiedene Auswahlmoehlichkeiten.
- Auswahl der naechsten zu legenden Position anhand der minimalen Zugmoeglichkeiten.
ca. 5 Minuten auf P4 3 GHz
Mail: dom at wtal dot de
Schicke Dir auch mal die Email, die ich an Harald Bögeholz geschickt habe; die hat Geschwindigkeitstechnisch zwar keine Chance gegen die Spezialisten (habe ja sogar nicht mal _meine_ schnellste Version hingeschickt), finde sie persönlich aber trotzdem interessant. In dem Archiv sind zwei Versionen, eine mit 2 Threads, eine mit nur einem. Der Algorithmus ist derselbe, also ist die 2 Thread-Variante die interessantere, auf einem "normalen" System aber auch die langsmere. Nun zu meiner Lösung: Sie sollte unter Linux (Debian Testing bei mir) so im Bereich von 5 Minuten laufen (P4,3,05GHz), und geht prinzipiell genauso vor wie die Puzzlelösung in dem Artikel, jedoch mit folgenden Unterschieden: 1. Die Symmetrie wird durch zwei Teile zusammen rausgerechnet (Teil 5 nach hinten, Teil 7 nach oben), dadurch wird die Gesamtanzahl aller zu speichernden Positionen minimal (2592), und die Anzahl der gesetzten Teile beträgt "nur" noch 3Mrd. 2. Die Rekursion ist aufgelöst und ersetzt durch 12 verschachtelte Funktionen, die sich dadurch inlinen lassen, und die Schleifen sind einfacher zu entrollen (die Anzahl verbleibender Teile ist ja bekannt). 3. Die 60 Würfel werden, bevor sie in die Datenstruktur eingetragen werden, umsortiert: Näherungsweise so, daß die nächste zu wählende Position möglichst wenige neue Teile setzen muß. Hatte dazu ein Programm geschrieben, das mir die Auswahl erleichtert. Das senkt die Anzahl der gesetzten Teile auf 2,9Mrd, auch die vergeblichen Versuche werden weniger. 4. Die Puzzleteile werden nach ihrem ersten gesetzten Bit sortiert; dadurch brauche ich nur Teile testen, die tatsächlich an die gesuchte Position passen. 5. Die "Liste der bereits benutzten Teile" ist keine: Sie ist ein Array, deren erste Elemente immer die Indizes der noch verbleibenden Elemente enthält. Die verschachtelten Funktionen wissen immer selbst, wieviele dieser Elemente zu benutzen sind. Immer, wenn ein Teil gesetzt wird, wird das letzte Element der aktuellen Liste an die Stelle kopiert, und anschließend wieder zurück. Das kostet sicherlich etwas zusätzliche Speicherzugriffe, braucht aber keinerlei Vergleiche, was insbesondere bei der Bearbeitung von 5 und weniger Teilen, die 90% der Zeit benötigen, eine Rolle spielen dürfte. Dadurch kann man natürlich nicht nachvollziehen, in welchen Positionen die Teile gesetzt wurden. 6. Multithreading: Zwei Threads starten mit denselben Daten, die Synchronisation ist immer bei der Auswahl des ersten zu setzenden Teils; wenn der andere Thread es bereits bearbeitet hat, wird das nächste genommen. 7. Es werden auf den "Rekursionsebenen" mit bereits 2 bzw. höchstens 7 gesetzen Steinen ein Check auf isolierte Leerstellen gemacht und dementsprechend die "Rekursion" an dieser Stelle abgebrochen. Die Punkte 1, 2, 5 und 6 stellen wohl mal eine etwas andere Vorgehensweise dar, um das ganze interessant zu machen. Da ich ohnehin keine Siegchance habe (nur gcc3.2, kein inline-assembler, kein SSE2/MMX), habe ich auch gar nicht mehr versucht, den "X-Trick" zu verwenden. Der beschleunigt mein Programm zwar, ich müßte aber einige der anderen Vorkehrungen wegwerfen, und das wäre IMHO zu schade.
Ich, Uli Schuhmacher, bin per eMail unter epsilon0@ixcase.com erreichbar. Ansonsten verweise ich hier noch auf das c't-Forum zum oben erwähnten Artikel: Forum