Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I want to generate a path to cut an arbitrary shape into a set of jigsaw puzzle pieces.

  1. All pieces must be unique to preclude placing a piece in the wrong spot.
  2. Pieces must be interlocking such that each piece is held by adjacent pieces.
  3. It must be possible to generate different paths (sets) for a specific shape that are not merely rotations or reflections of the first.

Since jigsaw puzzles are mass produced there must be a known solution. However, my interest is not in simply implementing this solution, rather I am curious to know how one might approach this task, aided by Mathematica. I am also interested in alternatives to the standard puzzle piece such as these (even if pieces are not 100% interlocking):

jigsaw puzzles

share|improve this question
    
Great question. Jigsaw puzzles can be with or without picture. Did you intend to make pieces unique purely by shape of the boundary or boundaries can by repetitive and uniqueness is also set by the pieces image or color? –  Vitaliy Kaurov Jun 12 '12 at 7:29
    
@Vitaliy my intent is to have unique shapes which may or may not be overlaid with an image; a solid-color puzzle should have a single solution. –  Mr.Wizard Jun 12 '12 at 7:43
    
I'd first partition the puzzle into polygons, then shaping those little "tongues" that interlock them. Are you interested mostly in the partitioning part or making the shapes interlock? Partitioning into rectangles then distorting the rectangles a bit and adding "tongues" to them (I really can't find a good English word for these!) would be the easiest, but also a bit boring. –  Szabolcs Jun 12 '12 at 7:52
    
@Szabolcs both, really; the tongues (sounds reasonable) need to be unique shapes as they are often what determines whether or not a piece fits. That adds to the complexity. Also, there is a question of "how unique" a piece is; if we apply a random distortion I do not think we are guaranteed to have a "highly unique" piece, meaning there is a chance we create pieces which someone could force into place incorrectly. –  Mr.Wizard Jun 12 '12 at 7:55
1  
There is a guy, Sam Savage, that produces puzzles based on Escher patterns: shmuzzles.com/shmuzzle_resources.htm –  berniethejet Jul 2 '12 at 18:17

2 Answers 2

up vote 35 down vote accepted

======= Update =========

Great question! It inspired this Wolfram Blog article and includes most of the code below plus some apps and fractal layouts like this:

enter image description here

I think it make sense to keep the older code blow for archival and historic purposes.

======= Older implementation =========

Excellent motivating creativity question. This is a bit big for a comment, so here are a few thoughts.

==== Voronoi practical implementation ====

Let's start from writing the following function:

bsc[p1_, p2_] := 
 With[{rc = RandomChoice[{-1, 1}], d = EuclideanDistance[p1, p2], 
   pm = (p1 + p2)/2, dp = (p2 - p1)/5},
  If[d < .1,
   Line[{p1, p2}],
   BSplineCurve[{p1, pm, pm - dp + rc {1, -1} Reverse[dp], 
     pm + dp + rc {1, -1} Reverse[dp], pm, p2}, 
    SplineWeights -> {1, 5, 5, 5, 5, 1}/22]
   ]]

which will morph a long enoug line into a line with a "tongue". It will put the tongue in a random direction for more random generation of puzzle pieces. And some comparison function that will show what points we are adding to wrap BSplineCurve around.

f[p1_, p2_] := 
 With[{d = EuclideanDistance[p1, p2], pm = (p1 + p2)/2, 
   dp = (p2 - p1)/5},
  If[d < .1,
   Line[{p1, p2}],
   Line[{p1, pm, pm - dp + {1, -1} Reverse[dp], 
     pm + dp + {1, -1} Reverse[dp], pm, p2}]
   ]]

Here is a Manipulate to test it out:

Manipulate[
 Graphics[{f @@ pt, {Red, Thick, bsc @@ pt}}, ImageSize -> {300, 300},
   Axes -> True, Frame -> True, AspectRatio -> 1, 
  PlotRange -> {{0, 1}, {0, 1}}], {{pt, {{0, 0}, {1, 1}}}, Locator}, 
 FrameMargins -> 0]

enter image description here

Now this will create a simple Voronoi diagram:

gr = ListDensityPlot[RandomReal[{}, {35, 3}], InterpolationOrder -> 0,
   Mesh -> All, Frame -> False]

enter image description here

And this will extract lines out of it and replace long enoug lines with our tongues function:

Graphics[bsc @@@ 
  Union[Sort /@ 
    Flatten[Partition[#, 2, 1] & /@ 
      Map[gr[[1, 1, #]] &, 
       Flatten[Cases[gr, Polygon[_], Infinity][[All, 1]], 1]], 1]]]

enter image description here

This can be superimposed on an image or simply colorized (with added outer frame):

MorphologicalComponents[
  Binarize@Graphics[{Thick, 
     bsc @@@ Union[
       Sort /@ Flatten[
         Partition[#, 2, 1] & /@ 
          Map[gr[[1, 1, #]] &, 
           Flatten[Cases[gr, Polygon[_], Infinity][[All, 1]], 1]], 
         1]]}, Frame -> True, FrameTicks -> False, 
    PlotRangePadding -> 0, FrameStyle -> Thick]] // Colorize

enter image description here

You have to execute code a few times to find best random colorization - it is based on random tongue orientation.

=== Yet another way - Hilbert & Moore curves====

I slightly modified this Demonstration and cut resulting curves with grid lines:

LSystem[axiom_, rules_List, n_Integer?NonNegative, False] := 
  LSystem[axiom, rules, n, False] = 
   Nest[StringReplace[#, rules] &, axiom, n];
LSystem[axiom_, rules_List, n_Integer?NonNegative, True] := 
  LSystem[axiom, rules, n, True] = 
   NestList[StringReplace[#, rules] &, axiom, n];
LSeed["Hilbert curve"] = "+RF-LFL-FR+"; 
LSeed["Moore curve"] = "+LFL+F+LFL-";
LRules["Hilbert curve"] = {"L" -> "+RF-LFL-FR+", 
  "R" -> "-LF+RFR+FL-"}; 
LRules["Moore curve"] = {"L" -> "-RF+LFL+FR-", "R" -> "+LF-RFR-FL+"};
LPoints[lstring_String] := 
  LPoints[lstring] = Map[First, Split[Chop[Map[First,
       FoldList[Function[{pta, c},
         Switch[c,
          "+", {pta[[1]], pta[[2]] + 90 Degree},
          "-", {pta[[1]], pta[[2]] - 90 Degree},

          "F", {{pta[[1]][[1]] + Cos[pta[[2]]], 
            pta[[1]][[2]] + Sin[pta[[2]]]}, pta[[2]]},
          _, pta]],
        {{0, 0}, 0.},
        Characters[lstring]]]]]];
LPoints[lstring_String, level_Integer?NonNegative] := 
  Map[(2^(5 - level)*# + ((2^(5 - level) - 1)/2)) &, LPoints[lstring]];
LLine[lstring_String, 
   level_Integer?NonNegative] := {AbsoluteThickness[2*(5 - level)], 
   BSplineCurve[LPoints[lstring, level]]};
Manipulate[
 MorphologicalComponents[
   Binarize@Graphics[If[showPreviousLevels == False,
      LLine[
       LSystem[LSeed[whichcurve], LRules[whichcurve], n - 1, 
        showPreviousLevels], n], 
      MapIndexed[LLine[#1, First[#2]] &, 
       LSystem[LSeed[whichcurve], LRules[whichcurve], n - 1, True]]], 
     GridLinesStyle -> Directive[Thick, Black], FrameStyle -> Thick, 
     GridLines -> {None, Table[x, {x, 4, 30, 4}]}, Frame -> True, 
     FrameTicks -> False, PlotRangePadding -> 0]] // Colorize
 , {{n, 4}, 
  ControlType -> None}, {{whichcurve, "Hilbert curve", 
   ""}, {"Hilbert curve", "Moore curve"}, 
  ControlType -> RadioButtonBar}, {{showPreviousLevels, False}, 
  ControlType -> None}, SaveDefinitions -> True]

enter image description here

share|improve this answer
    
Thanks for answering. It did occur to me to create a Voronoi segmentation and then perturb the edge into something interlocking. Most of the tilings are problematic however in that they specifically have repeating shapes which I am expressly trying to avoid. –  Mr.Wizard Jun 12 '12 at 7:46
    
@Mr.Wizard Agreed, Voronoi is a good candidate for morphing. In relation to other tilings - this is why I asked about the cover image. I thought with small set of pieces image/color/pattern will make them unique. But I see you are trying to go in the opposite direction - towards unique boundaries. –  Vitaliy Kaurov Jun 12 '12 at 7:53
    
f is not defined in the first manipulate and there are some problems on the edges, but otherwise a great big +1! –  Ajasja Jun 12 '12 at 10:55
5  
Vitaliy, you get much sleep last night? (Apparently not, given when the response was posted.) –  Daniel Lichtblau Jun 12 '12 at 15:50
1  
@DanielLichtblau Sleepcoding ;-) –  Vitaliy Kaurov Jun 12 '12 at 16:37

The first part of the problem is partitioning a shape into smaller parts of a roughly equal area. Then we can add little "tongues" on the pieces to make them interlock.

One idea for partitioning is using either a Delaunay triangulation of a set of points (for triangular pieces) or a Voronoi tessellation (for many-sided polygons).

Let's take for example this method of generating a set of random points with a minimum distance. I modified the algorithm a little to squeeze as many points into a region as possible:

canvas = Image@ConstantArray[0, {100, 100}];
distance = 15;

{img, {pts}} = Reap[
   NestWhile[
    ImageCompose[#, SetAlphaChannel[#, #] &@Image@DiskMatrix[distance],
      Sow@RandomChoice@Position[
         Transpose@ImageData[#, DataReversed -> True], 0.]] &,
    canvas,
    Count[Flatten@ImageData@Binarize[#], 0] > 0 &]];

Then the Delaunay triangulation looks like this:

<<ComputationalGeometry`
PlanarGraphPlot[pts, LabelPoints -> False]

(For a better result we'd need to add points from the edges.)

The Voronoi tessellation looks like this:

Show[DiagramPlot[pts], PlotRange -> 100 {{0, 1}, {0, 1}}]

It can also be shown with ListDensityPlot:

showTiles[pts_] := 
 ListDensityPlot[ArrayPad[pts, {{0, 0}, {0, 1}}], Mesh -> All, 
  InterpolationOrder -> 0, Frame -> False, ColorFunction -> (White &)]

showTiles[pts]

Mathematica graphics

Another possibility is to start with a regular grid of points (e.g. a hexagonal grid),

hex = Join @@ Table[{x, Sqrt[3] y}, {x, 0, 4}, {y, 0, 2}];
pts = Join[hex, TranslationTransform[{1/2, Sqrt[3]/2}] /@ hex];

showTiles[pts]

and distort it randomly:

pts = RandomReal[0.1 {-1, 1}, Dimensions[pts]] + pts;
showTiles[pts]

Mathematica graphics

Just for some fun, we can actually create the tiles and shuffle them a bit. Who wants to add some code to make them draggable and rotatable?

Graphics[
 {EdgeForm[Black],
  Texture@ExampleData[{"TestImage", "Sailboat"}], 

  GeometricTransformation[#, 
     Composition[
      TranslationTransform@RandomReal[0.1 {-1, 1}, 2], 
      RotationTransform[RandomReal[{-Pi, Pi}], Mean@First[#]]]] & /@ 
   Cases[Normal@showTiles[Rescale[pts]], 
    Polygon[p_, ___] :> Polygon[p, VertexTextureCoordinates -> p], 
    Infinity]}
 ]

Mathematica graphics

share|improve this answer
    
It is already draggable and rotateable I guess. Slightly easier if one adds the option ContentSelectable -> True. It would be nice to prevent stretching though. Nice one +1 –  Rojo Jan 25 at 18:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.