A computational solution to a tedious puzzle.
If you stumbled upon this page, there’s a good chance you are in possession of one of these:
I don’t know much about the origin of this game. The box points to www.derekcorp.co.nz, a custom souvenir manufacturer in New Zealand. I received this copy from a friend, who got it from another friend. The only information provided was that no one was able to solve it so far.
The puzzle is made of 16 square pieces depicting pukekos (a species of bird found in New Zealand).
There is a half pukeko printed on each of the four edges of a piece, showing either its head or legs. A total of five different (although frustratingly similar) "models" are present across all the pieces. Joining the right pieces will complete a full bird.
The goal is to arrange the pieces in a 4 × 4 square so that all illustrations across pieces line up.
Additionally:
-
Two of the pieces are identical.
-
There is only one appearance of the "Z" pukeko, which makes you think it’s a good starting point for solving the puzzle.
Your first instinct when you approach this puzzle is to pick random pieces one by one and place them matching the already placed pieces. After a lot of messing around, you may reach a partial solution where only one or two pieces of the square are missing, but the pieces left won’t fit.
Most people quickly reach the conclusion that there are too many possible arrangements and the game is too tedious to even bother trying to solve it.
Indeed, the number of possible piece combinations is astronomic:
16! 416 / 2 / 4 = 1.1232837 × 1022
(we divide by 2 because there are two identical pieces, and by 4 to exclude rotations)
Furthermore, there doesn’t seem to be any great heuristics much better than brute force. I decided that I would better program the solution; at least I could have some fun this way.
The puzzle has 41 unique solutions, once you exclude duplicates (i.e. solutions where identical pieces are switched) and rotations (i.e. solutions that are constructed by rotating other solutions).
If you just want to see one solution, look here.
If you want to examine all solutions, you can find the output of the program in plain text here.
I coded the solution in Scala. The algorithm does a depth-first search (backtracking) through a recursive function.
The API is generic enough to model most puzzles of this class. It receives an arbitrary list of pieces and a sequence of positions (as integer coordinates) that make the "board". The sequence doesn’t have to form a square, so other arrangements are possible. The backtracking function tries to fit the pieces in order following the provided sequence of positions.
I found that the best strategies are sequences that maximize early adjacency, i.e. where each piece is placed adjacent to the most other pieces already placed. This can be achieved by spiraling out from the center of the square.
Doing this, the constraints are accumulated early in the backtracking and the search tree gets greatly reduced. In effect, my tests have shown that the placement scheme is crucial in keeping the algorithm under acceptable times.
Requires SBT
Clone this repo (or download it):
$ git clone https://github.com/gsoto/pukeko.git
Run:
$ sbt run
If you are getting strange output characters on Windows, try:
$ chcp 65001