The above puzzle is designed by Oskar van Deventer. He has a YouTube video showing it. This video was the inspiration for my research into this type of fractal puzzles. The puzzle can be bought from him from Etsy.

The first image visualises the pieces that make up the puzzle. (There is a link to this image on the page Material added 25 Dec 05 under the heading 'Bridged DiTans and Triamonds' on the mathpuzzle website.) The second image explains how each piece consist of a number of connected triangles. (The image is taken from the section 'Bridged Polyamonds' from the Logelium website.) In most of the pieces the triangles are connected on the corners, but there are also some where some triangles are touching on the sides. The red brown piece in the right bottom corner consists of three triangles that all are connected on sides. When I saw this, I wondered whether it would be possible to create a puzzle with pieces where the triangles are only connected on the corners. So, that made me think about developing a program for generating this kind of fractal puzzles.

The first step was figuring out how the fractal shapes were generated. I started make some drawings and figured out that it is based on an L-system or Lindenmayer system and its production rules. In the above animation it shows the various generations of the fractal where three copies (in the colours red, green, and blue) are used to create a triangle shape with three grey connecting bends. Each bend is a third of a whole circle, an arc of 120°. There are two types of arc, that we call l and r, refering to whether the arc makes a left or right turn. (Due to my dislexy, I often swap left and right.) The simplest fractal pattern can be described with 'lr'. For the next it is 'lr l lr r lr'. The general rule is to take three copies of the previous generation and separate them by an extra l and an extra r.

The curve is also a space filling curve. Because Giuseppe Peano was the first to discover one, space-filling curves in the 2-dimensional plane are sometimes called Peano curves, but that phrase also refers to the Peano curve, the specific example of a space-filling curve found by Peano.

Above the abstract representation of the puzzle to be solved. For a correct solution, pieces cannot overlap. This means that every triangle and connection point cannot be covered by more than one piece. Furthermore, each triangle needs to be covered. A piece consist of a number of triangles and connection points where the triangles are connected. In general it will not have more connection points than triangles. This problem looks very similar to exact cover. Donald A. Knuth used the Dancing links technique in his Algorithm X to solve exact cover problems.

When designing a puzzle, there are a number of properties to be considered. The first is the shape of the perimeter within in which the piece need to be placed. The second is the size of the pieces, the number of triangles that are used. The third is the variation of pieces in the solution: many small or also some large pieces. The fourth is the number of copies of the same type of piece. Often, solutions will contain multiple copies of the smaller pieces. The fifth is the number of solutions. It might be the case that for a certain set of pieces there can be more than one solution. Do we want a puzzle with exact one solution or do we allow multiple solutions. The last, is the difficulty of the puzzle. It is not necessary that a puzzle with one solution is harder than a puzzle with multiple solutions.

The pianofrac program (to be found at my FractalJigsawPuzzle repository at GitHub) can generate and Exact Cover problem with the command gen_ec_hc for the hard-code set of pieces or the gen_ec command with pieces of a certain size, specified with the -range option. (The options -con and -with_name are required for the following steps.)

In the above command the ExactCover program is used to solve the Exact Cover problem to generate all possible solutions. Due to the rotation symmetry of the puzzle, there could be three duplicates of a solution. To filter out these duplicates the normalize command of the pianofrac program.

The used_pieces command of the pianofrac program, sums the names (numbers) of the pieces that are used in each solution listed in the input file on a separate line in the output. With the help of the Unix programs sort and uniq a list of puzzles, sorted by the number of solutions, can be created. This still results in a large file of puzzles, which could make selecting a puzzle hard.

The used_pieces has some options to filter out puzzles on a number of conditions. With the options -min and -max one can restrict the number of pieces to be used in a puzzle (the specified values are included). With the option -max_occ it is possible to restrict the number of duplicates per type of piece and with -sup_occ it is possible to restrict to total number of duplicates for all types of pieces. In case no puzzles are returned the program prints out the 'minimal' limits.

With the filter command of the program, the solutions with a puzzle can be selected from the sols.txt. The 'name' of the puzzle is sequence of the numbers found in the puzzles.txt file (without the number specifying the number of solutions for the puzzle).

The the svg command an SVG file can be generated. The -space option can be used to specify the space between the pieces. If the option is not used, there will be just a single line between the pieces. For more options see the FractalJigsawPuzzle repository on GitHub.

The first puzzle was made with a single line and with G₅ puzzle. It was quite difficult to get the pieces out of the puzzle. And because the aspect ratio was not exactly 1, putting a symmetric piece in the wrong way, will make it very hard to get it out again. Not really playable. We drilled a hole into the side such that it can be hung on the wall. Some of the mentioned puzzles can be bought from the website annabelester.

For more about this, see blog posts:

• Monday, June 24, 2019
• Tuesday, June 25, 2019
• Wednesday, July 3, 2019