Jigsaw generator

This is a small experiment where jigsaw puzzles are randomly generated.

We focus on regular grids, where all pieces are squares of the same size. A piece has 4 edges, selected from a small set of shapes, namely edge types. By design, adjacent pieces must have complementary edge types. Having only a few edge types increases the combinations, as more pieces can connect together.

Moreover, the goal is to make apictoral jigsaw puzzles out of transparent acrylic. This means that front and back faces cannot be distinguished by looking at the piece. In practice, this not only increases the number of combinations, it also requires a different intuition from usual puzzles.

The main design constraint is to have exactly one solution, if we ignore the rotation and flip of the whole board. This property opens various strategies, as well as making the problem well defined (i.e. you search THE solution). However, proving that there is a single solution is likely to be NP-hard. Hence, the approach here is to brute force all combinations, effectively counting them.

Getting started

First of all, this project is meant as an experiment, and is therefore not expected to be flexible, nor robust. Still, feel free to play with the provided helpers!

In this project, jigsaw puzzles are 2D grids of square pieces, where edges belong to a finite (and typically small) set. While the helpers are typically agnostic about the actual shape of the edge types, this discussion will assume that the definitions from jigsaw.default are used. This provides a definition for opposite and flip, the two operations required to infer how edges can connect.

Currently, low-level functions are provided, in order to manipulate 2D grids. There are two main representations, depending on the context:

• Edge-wise, referred as grid, which is a pair of 2D arrays, representing horizontal and vertical edges, of shape H x (W + 1) and (H + 1) x W, respectively.
• Piece-wise, referred as pieces, which is a single 3D array, representing a 2D array of pieces, of shape H x W x 4.

While the former has the advantage of not duplicating any information (and therefore should be usually preferred), the latter is used during the search, as pieces are manipulated explicitly. A basic usage is showcased in getting_started.ipynb.

A more scalable approach is provided in attempt_01.ipynb; as the name implies, this is not well-tested, but it has proved sufficient until now. The overall flow is as follow:

1. Define a sampler, which is a parameter-less functor that will return a new random grid.
2. Optionally define custom validators; usually if this is easier to implement a rule as a test instead of a sampling strategy.
3. Search for a sample that is successfully validated. The uniqueness of the solution is usually the last validator to be applied.

The number of solution roughly depends on the ratio of the number of edge types and the number of pieces. On the one hand, if there are too many edge types, then there is almost surely a single (and often easy) solution. On the other hand, if there are too few edge types, then there are almost surely many solutions; if uniqueness is requested, this will not converge.

I believe there is no bulletproof strategy here, finding the right balance is trial-and-error. The key challenge is to make a puzzle that is enjoyable, and not just pure brute-force. Remembering which combinations of pieces have been tested may very well be a nightmare, so be sure to add a "strategy" in your design.

Attempts

Overall, the lessons learnt are as following:

• 3x3 are too easy; at most they can act as a tutorial, but should be avoided.
• 4x4 are the most successful, a reasonable trade-off that does not scare away most players.
• 5x5 should be well-designed, as combinatorics will hit your players hard. They need several clear steps, or they will end up brute-forcing it, and despair. For your veteran players, who seek challenge!
• 6x6 and above are both too difficult and tedious to design. I did not even attempt to make some, these sound too scary...
• Internal flat edges is the best way to guide the player; having only pins is overwhelming.
• Play with the various edge types, as they do not behave the same when flipped or rotated.
• Always include a so-called strategy, both on the layout (e.g. only one logical location for an additional corner) and the pins (e.g. a subset of pins only appear on the outer pieces). Please refer to the notebooks for concrete examples.
• In particular, players need a way to validate sub-parts of their solution; being able to confirm that some pieces must be together is reassuring and avoid naive brute-forcing.

Here are the provided design attempts, the most successful designs are marked with a ⭐:

01.01 — 3x3 basic

01.02 — 3x3

01.03 — 3x3 skewed

01.04 — 3x3 skewed

01.05 — 4x4

01.06 — 4x4 twisted

01.07 — 4x4 with 8 corners

01.08 — 4x4 with 5th corner ⭐

01.09 — 4x4 split ⭐

01.10 — 4x4 snake ⭐

01.11 — 5x5 with square center

01.12 — 5x5 with 5th corner

02.01 — 4x4 with 8 corners

02.02 — 5x5 with nested corners ⭐

02.03 — 4x4 with pure square ⭐

02.04 — 4x4 with more edges ⭐

02.05 — 4x4 with 6 corners ⭐

02.06 — 4x4 corners-only

02.07 — 4x4 cycle ⭐

About laser cutters

This whole project came to be since I got the opportunity to use some laser cutter, a Trotec Speedy 300. I am by no mean an expert, but cutting acrylic is somewhat straightforward; you just need to find a balance between speed and power, and vendors usually provide hints about typical values.

However, it seems that there are two main categories of acrylic: extruded (XT) and cast (GS). While the former is cheaper, the latter yields better-looking results.

A few references:

• Trotec: Speedy 300 Operating Manual
• Trotec: Comparison of cast and extruded acrylic
• 3mm cast acrylic glass used

References

Even though these were not used in the final code, this may be of interest:

• Unique reconstruction threshold for random jigsaw puzzles, Nenadov et al., 2016 (link)
• Even 1 × n Edge-Matching and Jigsaw Puzzles are Really Hard, Bosboom et al., 2016 (link)
• No easy puzzles: Hardness results for jigsaw puzzles, Brand, 2015 (link)
• Solving Small-piece Jigsaw Puzzles by Growing Consensus, Son et al., 2016 (pdf)
• Shotgun Assembly of Labeled Graphs, Mossel and Ross, 2017 (link)
• Solving jigsaw puzzles by computer, Wolfson et al., 1988 (link)
• Automatic Reassembly of Three-Dimensional Jigsaw Puzzles, Grim et al., 2016 (link)
• Automatic Solution of Jigsaw Puzzles, Hoff and Olver, 2014 (link)