Tricks im c't-Puzzle

Erst mal möchte ich allen Teilnehmern im Forum ganz herzlich danken. Die Beiträge dort haben mir immer wieder Anregungen und Ansporn gegeben.

In Anlehnung an den vielzitierten X-Trick habe ich meine Tricks mit weiteren Buchstaben belegt. Die meisten sind unter den Puzzlern wahrscheinlich schon allgemein bekannt, aber vielleicht ist doch noch die eine oder andere unbekannte Perle dabei.

Übersicht

Hotspot-Implementation

Ich suche den Hotspot nur innerhalb einer 3*4-Ebene und nehme da die Stelle, die die wenigsten freien Nachbarn hat. Welche das ist, kann ich für jede der 4096 möglichen Belegungen einer Ebene vorab ausrechnen und als Array speichern.

Wichtig in Verbindung mit der Plus-Indizierung ist die Erkenntnis, dass der Hotspot niemals mehr als 2 freie Nachbarn hat. Hätte er mehr, würde eine andere Stelle als Hotspot gewählt: es gibt immer eine Stelle (etwa am Rand) mit 2 freien Nachbarn oder weniger.

Vereinfacht gibt jetzt es ein Array int hotspot[4096], das in der Suche genutzt werden kann, um den Hotspot zu finden:
int nextPos = hotspot[belegung & 0xfff]
In dieser Form gilt das natürlich nur auf Ebene 0, für die höheren Ebenen müssen noch Shifts und Additionen dazu.

Plus-Index

Das Problem, immer viele Teile untersuchen zu müssen, obwohl nur wenige wirklich passen, haben sicher alle Teilnehmer entdeckt.

Wenn ich mich für einen Hotspot entschieden habe, könnte ich jetzt alle Teile-Varianten durchprobieren, die diese Stelle belegen. Das sind aber ziemlich viele, und der Vergleich, ob ein Teil passt oder nicht, wird damit ganz klar zum dominierenden Zeitfaktor.

Im anderen Extrem könnte ich theoretisch für jede mögliche Befüllung des Quaders eine Liste ablegen, welche Teile hinenpassen. Dann hätte ich die perfekte Vorselektion und wäre ich sicher, kein überflüssiges Teil zu probieren. Leider bräuchte ich da 2⁶⁰ verschiedene Listen, und so viel Speicher bekäme man wahrscheinlich auch dann nicht zusammen, wenn man sämtliche jemals produzierten RAMs der Welt kombinieren könnte. Gesucht ist also ein gesunder Kompromiss zwischen Selektionsschärfe und Speicherbedarf.

Mein Kompromiss sieht so aus, Kollisionen mit den 4 Nachbarn rechts, links, vorne und hinten durch eine entsprechende Indizierung der Varianten zu vermeiden. Ich brauche also je Position bis zu 16 verschiedene Listen (benannt A bis P) von Teile-Varianten gemäß Bild und Tabelle:

Statt wirklich 11 Listen zu führen, die wieder und wieder zum großen Teil dieselben Varianten enthalten und somit nur kostbaren Platz im Prozessor-Cache verschwenden, habe ich mir einen Trick überlegt. Ich schreibe alle für die 11 Listen relevanten Varianten in geeigneter Reihenfolge in eine Gesamtliste hintereinander, und zwar so, dass jede der benötigten Listen A bis M irgendwo als Ausschnitt auftritt. Nachdem ich etliche Blätter Papier mit Tabellen und Skizzen vollgekritzelt hatte, stand die Lösung.

Basis ist, die Teile-Varianten, die eine betrachtete Stelle belegen, auch nach den Nachbarpositionen in Teile-Gruppen a bis m zu sortieren, ganz analog zur obigen Tabelle. Diese Gruppen bilden die wiederverwendbaren Teilstücke der oben geforderten Listen A bis M.

Die Frage lautet, wie ich die Gruppen a bis m so hintereinander schreiben kann, das die geforderten Listen A bis M immer einen zusammenhängenden Abschnitt ergeben. Eine Lösung hierzu ist:

Ich schreibe bei jedem Teil die Liste der Varianten in der obigen Reihenfolge "dbacgeafbjiackaeim" einfach hintereinander und merke mir in einer zweiten Liste die 19 Start- und Endpunkte der Abschnitte als "Schlüsselpositionen". 

Im Betrieb liefern mir nun 2 Arrays im 4096er-Format die (abhängig von der Ebenen-Belegung und abgestimmt mit dem Hotspot-Array) passenden Start- und End-Schlüsselnummern, über die ich dann auf die Schlüsselpositionen und damit auf den richtigen Listenausschnitt zugreife.

Ergebnis

Interessant ist, was hinten rauskommt: 1364 Mio. platzierte Teile, 5999 Versuche, ein Teil zu platzieren, und 222 Mio. Zugriffe auf die Endspiel-Tabelle. Das Ganze braucht auf meinem Athlon XP2000+ etwa 182 Sekunden.

Da war doch noch was

Was ich sonst noch probiert habe, was aber überflüssig, schlecht oder katastrophal war.

Ich hoffe, meine Erläuterung haben zur Erhellung, Erbauung oder auch Erheiterung beigetragen und bin gespannt auf die Ideen der anderen.

Ralf Kleberhoff ( ralf03@kleberhoff.de )