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.

Difference between revisions of "Fractal Jigsaw Puzzle"

From

Jump to: navigation, search
(Filter solutions)
m (Select on used pieces)
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
{{Project
 +
|ImageInclude=
 +
|ProjectName=Fractal Jigsaw Puzzle
 +
|Owner=[[User:FFAA5E|#FFAA5E]]
 +
|Skillz=C++, SVG, Inkscape, Laser-Cutter
 +
|Status=100% finished
 +
|Summary=Create program to generate SVG file with design for puzzle
 +
}}
 +
 
The Fractal Jigsaw Puzzle can be made with a [[Laser Cutter]] and is based on an idea by  
 
The Fractal Jigsaw Puzzle can be made with a [[Laser Cutter]] and is based on an idea by  
 
[https://en.wikipedia.org/wiki/Oskar_van_Deventer Oscar van Deventer], which he shows
 
[https://en.wikipedia.org/wiki/Oskar_van_Deventer Oscar van Deventer], which he shows
Line 20: Line 29:
  
 
[https://github.com/FransFaase/FractalJigsawPuzzle The program] (written in C++) combines
 
[https://github.com/FransFaase/FractalJigsawPuzzle The program] (written in C++) combines
seven different functions that can be used to generate designs, to filter interesting
+
seven different commands that can be used to generate designs, to filter interesting
 
designs, to visualize the designs, and to produce
 
designs, to visualize the designs, and to produce
 
[https://nl.wikipedia.org/wiki/Scalable_Vector_Graphics Scalable Vector Graphics] (SVG)
 
[https://nl.wikipedia.org/wiki/Scalable_Vector_Graphics Scalable Vector Graphics] (SVG)
Line 26: Line 35:
  
 
To find designs the program makes use of an [https://en.wikipedia.org/wiki/Exact_cover Exact Cover]
 
To find designs the program makes use of an [https://en.wikipedia.org/wiki/Exact_cover Exact Cover]
solver. The first two functions of the program can be used to generate
+
solver. The first two commands of the program can be used to generate
 
an input file for the solver. The output from the Exact Cover solver can be
 
an input file for the solver. The output from the Exact Cover solver can be
processed with the third function.
+
processed with the third command.
  
 
=== Generating input for Exact Cover solver ===
 
=== Generating input for Exact Cover solver ===
  
The two first functions of the pianofrac program can be
+
The two first commands of the pianofrac program can be
 
used to generate input for the Exact Cover solver.
 
used to generate input for the Exact Cover solver.
  
Line 38: Line 47:
 
   pianofrac gen_ec [-con] [-range=''n'',''n''-''n'',''n''-] [-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
+
The first command (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
 
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
 
actually consists of an unique number for each piece. The names are
needed for the select function (explained below).
+
needed for the select command (explained below).
With the second function (gen_ec), one can specify a range of sizes for the
+
With the second command (gen_ec), one can specify a range of sizes for the
 
pieces. The -con option can be used to also little connection dots that
 
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"
+
are needed for some solutions. The command gen_ec with the arguments "-con -range=2-3"
is equal to function gen_ec_hc. If high numbers are used in the -range
+
is equal to command gen_ec_hc. If high numbers are used in the -range
option, the function can produce a very large output file. The use of
+
option, the command can produce a very large output file. The use of
 
the -with_name option could cause the program to slowdown and use large
 
the -with_name option could cause the program to slowdown and use large
 
amounts of memory.
 
amounts of memory.
Line 63: Line 72:
 
Because of the triangle nature of the puzzle, there are always six solutions
 
Because of the triangle nature of the puzzle, there are always six solutions
 
that are equivalent with respect to rotations and mirroring.
 
that are equivalent with respect to rotations and mirroring.
The function normalize with the option -minimal can be used to remove all
+
The command normalize with the option -minimal can be used to remove all
 
'double' solutions and thus reduce the file of solutions with a factor six.
 
'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,
 
If the -minimal options is not used, the solutions will all be normalized,
Line 72: Line 81:
  
 
The Exact Cover solver that accepts the input and produces output fit for
 
The Exact Cover solver that accepts the input and produces output fit for
this function can be found [http://www.iwriteiam.nl/ExactCover_20161209_cpp.txt here]
+
this command can be found [http://www.iwriteiam.nl/ExactCover_20161209_cpp.txt here]
 
in the form of a C++ program. Because this program reads the input from the
 
in the form of a C++ program. Because this program reads the input from the
 
standard input and produces output to the standard output, for example,
 
standard input and produces output to the standard output, for example,
 
the following pipe command can be used:
 
the following pipe command can be used:
  
   pianofrac gen_hc -con -range=2-5 | ExactCover | pianofrac normalize -minimal
+
   pianofrac gen_ec -con -range=2-5 | ExactCover | pianofrac normalize -minimal
  
 
=== Select on used pieces ===
 
=== Select on used pieces ===
 
One could take a random line from the output produced from the Exact Cover solver
 
One could take a random line from the output produced from the Exact Cover solver
and feed this as input to the function to produce an SVG file, but this might
+
and feed this as input to the command to produce an SVG file, but this might
 
result in a design that does not have nice properties. For example, because it
 
result in a design that does not have nice properties. For example, because it
 
has a lot of small pieces or some large pieces. Or because it has many pieces
 
has a lot of small pieces or some large pieces. Or because it has many pieces
of the same shape. The following function can be used to remove such designs.
+
of the same shape. The following command can be used to remove such designs.
The function requires that the pieces have a name, which is used to identify
+
The command requires that the pieces have a name, which is used to identify
 
pieces with the same shape. (A future version of the program may drop this
 
pieces with the same shape. (A future version of the program may drop this
restriction.) The function is called in the following manner:
+
restriction.) The command is called in the following manner:
  
 
   pianofrac used_pieces [-max_occ=''n''] [-sup_occ=''n''] [-max=''n''] [-min=''n'']
 
   pianofrac used_pieces [-max_occ=''n''] [-sup_occ=''n''] [-max=''n''] [-min=''n'']
Line 100: Line 109:
 
pieces in the design.) With the option -sup_occ=2 there could be at most
 
pieces in the design.) With the option -sup_occ=2 there could be at most
 
two pieces with the same shape. It makes sense to use both options, as long
 
two pieces with the same shape. It makes sense to use both options, as long
as the value for -sup_occ is larger than -max_occ.
+
as the value for -sup_occ is larger than -max_occ. If the conditions are too
 +
restrictive, and no solution is found, the program will print an error message
 +
and display the minimal and maximal values for the options.
  
This function will output the names (numbers) of the pieces that are used
+
This command will output the names (numbers) of the pieces that are used
 
in the design. The names are sorted from low to high. This allows for the
 
in the design. The names are sorted from low to high. This allows for the
 
output to be piped into the following command:
 
output to be piped into the following command:
Line 116: Line 127:
  
 
=== Filter solutions ===
 
=== Filter solutions ===
Once one has made a choice from the output of the previous function, this
+
Once one has made a choice from the output of the previous command, this
function can be used to select designs based on the pieces that it contains.
+
command can be used to select designs based on the pieces that it contains.
Again, this function requires that the piece placements have a name. (This
+
Again, this command requires that the piece placements have a name. (This
 
requirement may be dropped in the future.)
 
requirement may be dropped in the future.)
  
Line 126: Line 137:
  
 
=== Print solution ===
 
=== Print solution ===
''Coming soon''
+
The print command can be used to print a textual representation using
 +
slash, backslash and underline characters. For each line on the input,
 +
it produces a 'print'.
  
 
   pianofrac print
 
   pianofrac print
 +
 +
An example output from a file with a single line is:
 +
 +
          _
 +
        _/ \_
 +
      _/ \ / \_
 +
      /  _/ \_  \
 +
      \ /  _  \ /
 +
    _/ \_/ \_/ \_
 +
    / \_  _/  _  \
 +
    \_/ \ / \ / \ /
 +
  _/ \ / \ / \ / \_
 +
  /  _/ \_/ \_/ \_  \
 +
  \ /  _  \ /  _  \ /
 +
  / \ / \_/ \_/ \ / \
 +
  \_/ \_  \_/  _/ \_/
 +
  /  _  \_  _/  _  \
 +
  \_/ \_/ \_/ \_/ \_/
 +
    \_  _  _  _/
 +
      \_/ \_/ \_/
 +
  
 
=== Generate SVG ===
 
=== Generate SVG ===
''Coming soon''
+
The command svg can be used to generate an SVG file for a design. It
 +
only produces output for the first line from the input. The command
 +
with its options is:
 +
 
 +
  pianofrac svg [-border_rad=''r''] [-border_d=''r''] [-depth=''n'']
 +
                [-colour=''c''] [-stroke_width=''r''] [-side_length=''r'']
 +
                [-bottom] [-width=''r''] [-height=''r''] [-margin=''r''],
  
  pianofrac svg [-border_rad=''n''] [-border_d=''n''] [-depth=''n'']
+
The options can be used to modify the appearance. The option -depth=''n'',
                [-colour=''n''] [-stroke_width=''n''] [-side_length=''n'']
+
with values 1 to and including 4, specifies the recursion depth of the fractal.
 +
The default value is 2. The options -border_rad=''r'' and -border_d=''r'' can be
 +
used to change the border around the puzzle. The first option specifies the
 +
relative radius of the circle parts of the border. The default value is 1.5.
 +
The second option specifies the size of the triangle from which the radius is
 +
offset. The default value is 1.7. Note that the sum of the values determines
 +
the distance of the border to the center of the puzzle. The option
 +
-colour=''c'' can be used to specify a colour (should be valid SVG stroke colour).
 +
The default value is red. The option -stroke_width=''r'' can be used to specify
 +
the stroke width. The default value is 2. The option -side_length=''r'' can be used to
 +
specify the length of the triangles of the pieces. The default value is 100.
 +
The option -bottom adds an upside-down copy of the border to be added that
 +
can be used for the bottom of the puzzle. When both the option -width and -height
 +
are used (in combination with the -bottom option) the given dimensions will be
 +
used to calculate the optimal value for -side_length such that both the puzzle
 +
and the bottom fit inside the given rectangle. The algorith assumes that the width
 +
is larger than the height. If not it will still work, but not produce an optimal
 +
use of the area. The option -margin can be used to specify the margin that should
 +
be left free. The default value is 10. This option also works when the width and
 +
height are not specified.
  
 
=Result=
 
=Result=
  
For those people who are too lazy to download the program,
+
For those people who are too lazy to download the program, compile it, and experiment
compile it, and experiment with it (with lots of trial and error)
+
with it (probaly requiring lot of trial and error) we give
we give [http://www.iwriteiam.nl/D161211.svg a ready design]
+
[http://www.iwriteiam.nl/D161211.svg a ready design] consisting of nine pieces.
consisting of nine pieces pieces.
+
  
 
=External Links=
 
=External Links=
[https://github.com/FransFaase/FractalJigsawPuzzle FractalJigsawPuzzle on GitHub]
+
* [https://github.com/FransFaase/FractalJigsawPuzzle FractalJigsawPuzzle on GitHub]
 +
* [https://www.thingiverse.com/thing:3061121 On Thingiverse]
  
 
The original blog entries on which this page is based:
 
The original blog entries on which this page is based:
Line 150: Line 209:
 
* [http://www.iwriteiam.nl/D1611.html#1b SVG experiment]
 
* [http://www.iwriteiam.nl/D1611.html#1b SVG experiment]
 
* [http://www.iwriteiam.nl/D1612.html#11 Combined program]
 
* [http://www.iwriteiam.nl/D1612.html#11 Combined program]
 +
* [http://www.iwriteiam.nl/D1808.html#26 Fixed bug and small improvement]

Latest revision as of 08:28, 29 August 2018

Project: Fractal Jigsaw Puzzle
Fractal Jigsaw Puzzle Picture.jpg
Name Fractal Jigsaw Puzzle
Initiator [[Project Owner::#FFAA5E]]
Status 100% finished
Skills C++, SVG, Inkscape, Laser-Cutter
Summary Create program to generate SVG file with design for puzzle


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 commands 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 commands 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 command.

Generating input for Exact Cover solver

The two first commands 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 command (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 command (explained below). With the second command (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 command gen_ec with the arguments "-con -range=2-3" is equal to command gen_ec_hc. If high numbers are used in the -range option, the command 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 command 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]

The Exact Cover solver that accepts the input and produces output fit for this command can be found here in the form of a C++ program. Because this program reads the input from the standard input and produces output to the standard output, for example, the following pipe command can be used:

 pianofrac gen_ec -con -range=2-5 | ExactCover | pianofrac normalize -minimal

Select on used pieces

One could take a random line from the output produced from the Exact Cover solver and feed this as input to the command to produce an SVG file, but this might result in a design that does not have nice properties. For example, because it has a lot of small pieces or some large pieces. Or because it has many pieces of the same shape. The following command can be used to remove such designs. The command requires that the pieces have a name, which is used to identify pieces with the same shape. (A future version of the program may drop this restriction.) The command is called in the following manner:

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

The -min and -max options specify the minimum and maximum number of pieces (value included) that a design should have. The option -max_occ restricts the maximum number of times that a piece of the same shape may occur. And the option -sup_occ restricts the total number of pieces that have the same shape. If for example -max_occ=2 is used, it could still be the case that for each piece there is another piece with the same shape. (This is only possible if there is an even number of pieces and that for each shape there are two pieces in the design.) With the option -sup_occ=2 there could be at most two pieces with the same shape. It makes sense to use both options, as long as the value for -sup_occ is larger than -max_occ. If the conditions are too restrictive, and no solution is found, the program will print an error message and display the minimal and maximal values for the options.

This command will output the names (numbers) of the pieces that are used in the design. The names are sorted from low to high. This allows for the output to be piped into the following command:

 sort | uniq -c | sort

Which will result in a list of designs with a low number of solutions to a high number of solutions. If one want to make an easy puzzle, one should select for a design that has many solutions. Not all designs with a low number of solutions are hard, because it could be the case that they contain a number of large pieces that could only be placed at a few locations, thus quickly reducing the number of possible places for the remaining pieces.

Filter solutions

Once one has made a choice from the output of the previous command, this command can be used to select designs based on the pieces that it contains. Again, this command requires that the piece placements have a name. (This requirement may be dropped in the future.)

 pianofrac filter <pieces>

The output will contain all designs with the pieces listed at pieces.

Print solution

The print command can be used to print a textual representation using slash, backslash and underline characters. For each line on the input, it produces a 'print'.

 pianofrac print

An example output from a file with a single line is:

          _
        _/ \_
      _/ \ / \_
     /  _/ \_  \
     \ /  _  \ /
    _/ \_/ \_/ \_
   / \_   _/  _  \
   \_/ \ / \ / \ /
  _/ \ / \ / \ / \_
 /  _/ \_/ \_/ \_  \
 \ /  _  \ /  _  \ /
 / \ / \_/ \_/ \ / \
 \_/ \_  \_/  _/ \_/
 /  _  \_   _/  _  \
 \_/ \_/ \_/ \_/ \_/
   \_   _   _   _/
     \_/ \_/ \_/


Generate SVG

The command svg can be used to generate an SVG file for a design. It only produces output for the first line from the input. The command with its options is:

 pianofrac svg [-border_rad=r] [-border_d=r] [-depth=n] 
               [-colour=c] [-stroke_width=r] [-side_length=r]
               [-bottom] [-width=r] [-height=r] [-margin=r],

The options can be used to modify the appearance. The option -depth=n, with values 1 to and including 4, specifies the recursion depth of the fractal. The default value is 2. The options -border_rad=r and -border_d=r can be used to change the border around the puzzle. The first option specifies the relative radius of the circle parts of the border. The default value is 1.5. The second option specifies the size of the triangle from which the radius is offset. The default value is 1.7. Note that the sum of the values determines the distance of the border to the center of the puzzle. The option -colour=c can be used to specify a colour (should be valid SVG stroke colour). The default value is red. The option -stroke_width=r can be used to specify the stroke width. The default value is 2. The option -side_length=r can be used to specify the length of the triangles of the pieces. The default value is 100. The option -bottom adds an upside-down copy of the border to be added that can be used for the bottom of the puzzle. When both the option -width and -height are used (in combination with the -bottom option) the given dimensions will be used to calculate the optimal value for -side_length such that both the puzzle and the bottom fit inside the given rectangle. The algorith assumes that the width is larger than the height. If not it will still work, but not produce an optimal use of the area. The option -margin can be used to specify the margin that should be left free. The default value is 10. This option also works when the width and height are not specified.

Result

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

External Links

The original blog entries on which this page is based: