61
$\begingroup$

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

Improve this question
$\endgroup$
11
  • $\begingroup$ 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? $\endgroup$ Commented Jun 12, 2012 at 7:29
  • $\begingroup$ @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. $\endgroup$ Commented Jun 12, 2012 at 7:43
  • $\begingroup$ 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. $\endgroup$ Commented Jun 12, 2012 at 7:52
  • $\begingroup$ @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. $\endgroup$ Commented Jun 12, 2012 at 7:55
  • 1
    $\begingroup$ There is a guy, Sam Savage, that produces puzzles based on Escher patterns: shmuzzles.com/shmuzzle_resources.htm $\endgroup$ Commented Jul 2, 2012 at 18:17

2 Answers 2

Reset to default
47
$\begingroup$

======= 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

Improve this answer
$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$ Commented Jun 12, 2012 at 7:46
  • $\begingroup$ @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. $\endgroup$ Commented Jun 12, 2012 at 7:53
  • $\begingroup$ f is not defined in the first manipulate and there are some problems on the edges, but otherwise a great big +1! $\endgroup$ Commented Jun 12, 2012 at 10:55
  • 5
    $\begingroup$ Vitaliy, you get much sleep last night? (Apparently not, given when the response was posted.) $\endgroup$ Commented Jun 12, 2012 at 15:50
  • 1
    $\begingroup$ @DanielLichtblau Sleepcoding ;-) $\endgroup$ Commented Jun 12, 2012 at 16:37
23
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Commented Jan 25, 2014 at 18:38
  • $\begingroup$ Your code needs to be updated to accommodate the new version (such as 12.0). $\endgroup$ Commented Jan 31, 2020 at 2:07

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.