Octogram Puzzle Solver

Posted on by
1

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.

CroppedImage536536-18.-Octogram

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

O’Reilly eBooks fast geschenkt

Posted on by
Reply

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!

Posted on by
2

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

UpdateCheck

Posted on by
6

Mac OS X Software Update Notifications for Non-Admin-Users

As you might heard before, you should not do your normal work with an account that has administrative rights, no matter under which operating system. Although the vendors don’t make it very easy sometimes. Compared to MS Windows you are quite well off with Mac OS X, but also here you will find some caveats. For example, the automatic notification about available software updates only works, if you are logged in as an administrator. (In a multi-user environment this makes sense, since you don’t want to confuse ordinary users with such notifications. However, you cannot switch it on for a non-admin account that is used by the owner/admin of the machine, even if you want it.)

screenshot

Since I could not find any tool or script that fills in that gap, I wrote my own. It’s an applescript embedded into a plist-file for the launchd. It will check for available software updates once per day, and if there are any, it will display them in a Growl notification or – if Growl is not installed – in an ordinary dialog window. But using Growl is highly recommended!

Download: UpdateCheck

To install it, just move the file to Library/LaunchAgents in your Home folder. If the LaunchAgents folder does not exist, create it. Then re-login or enter the following command in the Terminal:
launchctl load ~/Library/LaunchAgents/de.anderson.sven.updateCheck.plist

PS.: As a Mac OS X user you might also be interested in another tool by me: Hibernate (Hibernation Tool for Mac OS)

Ensetzenwichteln…

Posted on by
1

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

Palringo has severe security issues

Posted on by
9

Many iPhone users are happy that there is finally an instant messaging client that claims to support all the important services like ICQ, MSN, Gtalk, Yahoo-Chat and so on. So was I, and happily installed Palringo today. But after a short while the happiness was gone. It was already suspicious from the beginning that you have to register an account with Palringo before being able to use it. After a short investigation I knew why.

In fact the Palringo client on the iPhone does not support any of the aforementioned services. All the client is doing is setting up a connection to a server (echo.palringo.com:38535), which then connects to the different services you want to use. This implies several security issues.

First, this means that Palringo is storing all your passwords of the different IM services you are using, and this is dangerous. For many services, like Google or MSN, these passwords are not only used for the chat system, but might also be used for your personal email account or even credit card payments! Are you sure you wanna share that with some random company? Beside that they can read all of your communication. (At least if you don’t use end-to-end encryption.)

But this is not the whole story. What really bothers me is that this connection from the iPhone to the Palringo server is completely unencrypted and plain text! Since the iPhone exclusively uses wireless technologies this is particularly severe. It means that everybody in your vicinity can very very easily intercept all of your communication and all your passwords as well. Remember, the same passwords might be used for your personal email or credit card payments. You don’t want that. 

So please do yourself a favor and don’t use Palringo! (At least not the current version.)