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: https://pastebin.com/eT5Sf28b

I also wrote a concurrent version in Go, which you can find here: https://github.com/ansiwen/octogram

Dies war der geilste Samba Gig, den ich bisher hatte:

Sapucaiu no Samba – Lagerhaus, Bremen 2011 from Tuttle on Vimeo.

Wer genau hinsieht, kann mich in diesen Videos entdecken.

Hören kann man mich schon eher. Ich spiele eine Repinique. Das ist das Instrument, das auch der Leiter spielt, und einen hohen, metallischen Klang hat.

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.

Get the latest Flash Player to see this player.

[Javascript required to view Flash movie, please turn it on and refresh this page]

Source: The Pirate Bay

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

Hier gibt es einen sehr lesenswerten Bericht wie im Moment mutige junge Menschen in China mit Hilfe des Internet und dem so genannten Web 2.0 Widerstand gegen den Unrechtsstaat leisten:

Co-operation 2.0 on Beijing’s Black Jails

Schönes Interview mit Noam Chomsky, das sich nicht nur auf Amerika beziehen lässt.

Via: Daniel

Tut mir leid, muss schon wieder was youtuben:

Note: ?? means “dining-hall”.

Via: Fool’s Mountain

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.)

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

Get the latest Flash Player to see this player.

[Javascript required to view Flash movie, please turn it on and refresh this page]

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

Ich werde das werte Publikum nicht mit belanglosen Flugtagberichten langweilen, sondern mich gleich auf das konzentrieren, weswegen man dem Modellflug zuschaut anstatt ihn selbst zu betreiben. (Der Ton ist wichtig!)