This wiki has been archived and made read-only.
For up-to-date information about TkkrLab and it's projects please visit our main website at tkkrlab.nl.

Fractal Jigsaw Puzzle

From

Revision as of 13:39, 11 January 2017 by FFAA5E (Talk | contribs) (Program)

Jump to: navigation, search

The Fractal Jigsaw Puzzle can be made with a Laser Cutter and is based on an idea by Oscar van Deventer, which he shows in this video. The puzzle can be ordered from Laser Exact.

This page describes software to produce your own Fractal Jigsaw puzzles, possibly resulting in a better design than the one used by Van Deventer.

Original design

It seems that the design by Van Deventer is taken from Bridged Polyamonds. On this mathpuzzle page there is a link to the design of the puzzle with a matching colouring of the pieces. One could try to import this image in Inkscape and try to vectorize the image, but it is doubtfull whether this will lead to a good result.

Program

The program (written in C++) combines seven different functions that can be used to generate designs, to filter interesting designs, to visualize the designs, and to produce Scalable Vector Graphics (SVG) files that be imported into Inkscape.

To find designs the program makes use of an Exact Cover solver. The first two functions of the program can be used to generate an input file for the solver. The output from the Exact Cover solver can be processed with the third function.

Generating input for Exact Cover solver

The two first functions of the pianofrac program can be used to generate input for the Exact Cover solver.

 pianofrac gen_ec_hc [-with_name]
 pianofrac gen_ec [-con] [-range=n,n-n,n-] [-with_name]

The first function (gen_ec_hc) generates input based on a hard coded set of pieces. The -with_name option will add names to the lines. The names actually consists of an unique number for each piece. The names are needed for the select function (explained below). With the second function (gen_ec), one can specify a range of sizes for the pieces. The -con option can be used to also little connection dots that are needed for some solutions. The function gen_ec with the arguments "-con -range=2-3" is equal to function gen_ec_hc. If high numbers are used in the -range option, the function can produce a very large output file. The use of the -with_name option could cause the program to slowdown and use large amounts of memory.

Each line of the generated output represent one possible placement of a piece, represented by a binary vector using 0 and 1 followed by a space and a description of the placement. Each possible design of a puzzle can be represented by a (small) selection of the lines such that in each column there is exactly one 1 and only 0's in all other lines. If this is the case, it means that the piece placements do not overlap and cover all locations.

Normalizing results from Exact Cover solver

The Exact Cover solver will produce a file with one solution per line, where each solution is represented by the names of the the selected piece placement. Because of the triangle nature of the puzzle, there are always six solutions that are equivalent with respect to rotations and mirroring. The function normalize with the option -minimal can be used to remove all 'double' solutions and thus reduce the file of solutions with a factor six. If the -minimal options is not used, the solutions will all be normalized, causing each solution to appear six times in the solution. (One could use "sort -u" to achieve the same effect as using the -minimal option.)

 pianofrac normalize [-minimal]

Select on used pieces

Coming soon

 pianofrac used_pieces [-max_occ=n] [-sup_occ=n] [-max=n] [-min=n]

Filter solutions

Coming soon

 pianofrac filter <pieces>

Print solution

Coming soon

 pianofrac print

Generate SVG

Coming soon

 pianofrac svg [-border_rad=n] [-border_d=n] [-depth=n]
               [-colour=n] [-stroke_width=n] [-side_length=n]

Result

For those people who are too lazy to download the program, compile it, and experiment with it (with lots of trial and error) we give a ready design consisting of nine pieces pieces.

External Links

The original blog entries on which this page is based