3x3 Jigsaw Puzzles
After solving the beautiful Nosey Puzzle by Alexander E Holroyd, and the very difficult Puzzle 29 by Yuu Asaka, I asked myself a simple and stupid question:What is the most difficult 3x3 jigsaw puzzle?
I want to find the set of 9 pieces (each of which has 4 edges which can be either flat, female or male) which gives the minimum number of solutions. If possible, I would like the solution to be unique even though one flips the pieces.
Fortunately, the solution can be easily found with a computer: we can brutforce the solution. The trick is that there are only 12 inner edges, and each one of them is either flat, inward or outward. This means that there are in total 3^12 = 531.441 puzzles to compute (some of them being equivalent up to rotations or flips).
For each one of these 3^12 puzzles, one can record its set of 9 pieces (up to rotations and flips). One then look for a set of 9 pieces which appeared only one time.
On my laptop, the computation takes around 1min, and I have found the 18 following puzzles.
Interestingly, all of them have a square piece located at an edge!
Among these solutions, I looked for the ones having a maximal of chiral pieces: pieces which are different when flipped. There are 6 puzzles with 2 chiral pieces (namely Puzzles 2, 5, 8, 10, 15 and 17). I claim that these are the most difficult 3x3 puzzles.
My favourite one is the following, which you can easily cut with a laser cut machine (pdf file here).
3x4 and 4x4 Jigsaw Puzzles
Of course, one can try to find the most difficult 3x4 puzzle similarly, or even a 4x4 puzzle.
However, there are now 17 inner edges, and 3^17 = 129.140.163 is now too large to be brutforced (it is even worse for the 4x4 puzzle). So one needs a different algorithm...
I could do the computation with an algorithm which roughly works as follows: one can see a 3x4 puzzle has a concatenation of two 3x2 puzzles. One performs a brutforce for the 3x2 sub-puzzles, clean the result (that is remove all non-interesting sub-puzzles), and then look the for interesting recombinations of two sub-puzzles (note that the sub-puzzles can be computed recursively with the same algorithm!).
If my computations are correct, there are 42 different puzzles of size 3x4 with a unique solution (up to symmetries), among which 10 have 3 chiral pieces. These are the most difficult 3x4 jigsaw puzzles.
The one I have laser cut is the following (pdf file).
4x4 puzzle
Finally, I could not find a 4x4 puzzle with a unique solution. This one has few solutions, and it seems difficult enough (pdf file)
However, one can easily guess that two pieces must be in the center, so it is not as difficult as planned.
This concludes my search for the "most difficult jigsaw puzzle". For the next step, I would like to look for difficult "(tray-) packing puzzle": see the beautiful collection by Stewart Coffin (redesigned on thingiverse by asiegel here).