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