Octogram Puzzle Solver

A friend of mine lent me a puzzle he once bought in New Zealand. Its called Octogram Puzzle, and a very similar puzzle is known as Draught Puzzle. Its goal is to put a number of differently shaped tiles into a square board, while the boards size is 8×8 squares and the tiles are variants of connected squares.

It takes quite some time to find a solution, and I was so annoyed that you just have to try around and almost can’t solve it in a systematic way, that I started to think about how you could efficiently find all possible solutions of the puzzle with a computer algorithm.

The key to a fast algorithm seems to be to detect “dead ends” of the search path tree as early as possible, that is, partly filled boards that don’t lead to any solution, so that you can skip large amounts of search paths. A typical case are small enclosures (for instance a single square), that none of the left tiles fit into.

I ended up with a modified flood fill algorithm, that starts at a corner, fills that corner with each of the tiles, and then recursively fills all the border squares of the tile with other tiles and so on. This is done by keeping a queue of squares that must be filled next. This way, if putting a tile on the board creates an enclosure, in which none of the left tiles fits into, a part of the enclosure will be border squares of the just added tile and will be queued to be filled. So the enclosure is expected to be detected relatively early, depending on the queue size.

Since every solution exists in 8 equivalent orientations (4 rotations x 2 transpositions) I also added conditions for the tiles filling the four corner squares in order to skip all equivalent orientations.

My single-threaded C++ implementation found all possible solutions (16146) in 22 minutes on a 2.6 GHz CPU, compiled with g++ 4.4.3 and -O3.

I am very interested in even faster algorithms or hints how I can further improve my algorithm, so please comment!

All the solutions are available here.

Here is the code:

O’Reilly eBooks fast geschenkt

Wie ich vor zwei Tagen festgestellt habe, gibt es im iPhone App Store viele O’Reilly Bücher als “App”, das heißt man bekommt das eBook und einen brauchbaren eBook-Reader in einem Paket. Und das ganze zu einem wirklich günstigen Preis, z.B. “Erlang Programming” für nur 4 EUR (bzw. 5 USD). Man vergleiche: bei O’Reilly auf den Webseiten kostet das gleiche Buch 40 USD! (Zugegebenermaßen dann in mehreren Formaten.) Ich habe mich natürlich erstmal gefreut, dass wir iPhone Benutzer mal wieder bevorzugt werden und deutlich weniger zahlen müssen als der gemeine Mob die Benutzer anderer Plattformen. (Mehr können wir uns ja auch nicht mehr leisten, haben wir doch unser ganzes Geld schon auf dem Apple-Altar geopfert.)

Das schöne ist aber: das ist nicht nur für iPhone Benutzer interessant! Denn letztendlich ist diese App nichts anderes als eine Zip Datei in der ein eBook-Reader und das eBook selbst im ePub Format enthalten ist. Es gibt ausdrücklich keinerlei DRM Schutz bei den Apps und O’Reilly selbst beschreibt, wie man die ePub Daten aus der App extrahiert. Man sollte also auch ohne ein iPhone zu besitzen die Bücher über iTunes kaufen können, und die extrahierten ePub Daten auf dem eBook-Reader der Wahl lesen können. (Oder muss mit iTunes ein iPhone verknüpft sein, bevor man Apps kaufen kann? Das wäre noch zu prüfen.)

Ich frage mich, ob das schlicht ein Fehler ist (denn selbst wenn man sich den gleichen eBook Reader als stand-alone App runter läd, kostet das Erlang Buch im integrierten “Bookstore” wieder 40 USD) und es nur eine Frage der Zeit ist, bis das behoben wird, oder ob das wieder mal ein Fall von verquerem Marketing ist, bei dem man als Käufer mit dem entsprechenden Quäntchen Information viel Geld sparen kann.

Lern Badisch!

Ensetzenwichteln…

Liebe Frau Chen-Yu,
vielen Dank. für die sehr gute Organisation dieses Jahr-Entsetzens – Wichteln.
Wir genossen es wirklich und uns auf das folgende Jahr-Ereignis freuen.
Es war sehr nett, al jene netten Leute wieder zu entsprechen.
Viele Grüße
Herr Lehmann

RapLeaf leaks?

There is a company named RapLeaf, that collects all information it can find around email addresses in the internet, mostly from social-networks and similar sites. Others have already noticed, that at RapLeaf, your personals are public. Yes, it is quite scary what they do. But on the other hand they are right, when they say: “it’s only aggregating what’s out there”. They are showing us the data, that anybody could collect. In fact we should be thankful, that they prove that it is actually very feasible to do, what privacy advocates always warned about: if you correlate all the small digital traces we produce every day, it can become a very powerful and potentially unpleasant data mine.

As for every huge collection of email addresses, one can assume that spammers are, among others, highly interested in that data, although they don’t want to pay for them. So it is not really surprising, that another statement from RapLeafs privacy policies turns out to be very true:

“Despite Rapleaf’s efforts to protect your personal information, there is always some risk that an unauthorized third party may find a way around our security systems”

By some coincidences I found a link, which seems to give access to RapLeafs (probably huge) list of email addresses: http://thebes.drakkenterprises.com/rapleafsrch/getpage.php?TYPE=RAPLEAF

Congratulations, probably this will eventually reveal your email address as well!

Update: the link doesn’t seem to spit out email addresses anymore. But I can testify, that it did until today in the form “<largenumber>, user%40example.com”. Every time you hit the reload button, you got a new one.

Structured Procrastination

Ich habe schon oft an mir beobachtet, dass ich keineswegs nur faul bin und gar nichts tue, sondern dass ich nie das mache, was gerade am wichtigsten erscheint. Somit ist die wichtigste Aufgabe die ich habe immer eine starke Motivation andere Dinge zu tun, die teilweise durchaus sinnvoll sind, wie z.B. Fenster putzen oder Blogeinträge zu schreiben. In Ansätzen kennt das vermutlich jeder ein bisschen, aber glaubt mir, bei mir ist das extrem. Dadurch kam ich auf die Idee, dass ich mir also, um mich zu etwas zu motivieren, einfach eine noch wichtigere und unangenehmere Aufgabe stellen muss, und schon würde sich die Blockade lösen, die bis dahin verhindert hat das zuvor wichtigste zu tun. Wie so oft war ich mit dieser Idee aber nicht der erste, und es gibt offensichtlich Menschen, deren Verhaltensmuster in erschreckender Weise dem meinigen bis ins Detail entspricht. Netterweise hat das so jemand mal sehr schön aufgeschrieben. Und irgendwie ist es auch beruhigend, dass man nicht alleine ist. Das bin ich:

I’m not wasting time.
I’m a structured procrastinator.

(Ich habe das natürlich entdeckt, als ich mich gerade erfolgreich um das Schreiben einer Veröffentlichung gedrückt habe.)

Wasser

Wie Krischan schon bemerkte, scheinen Flüssigkeiten ja ein beliebtes Objekt für stilvolle Werbespots zu sein.

Quelle: http://www.unsubscribe-me.org/