A related question I once thought of: What’s the minimum number of pieces you need to assemble to form a “skeleton” of a puzzle - such that every other piece fits directly to one of the skeleton pieces?
For an 9x4 puzzle I came up with the following pattern - a skeleton that uses 15 of 36 pieces:
-X—-X—-X-
-X—-X—-X-
XXXXXXXXX
—————————
It would be interesting to see if that’s optimal, and if the optimal solution is different for different puzzle sizes.
For an 9x4 puzzle I came up with the following pattern - a skeleton that uses 15 of 36 pieces:
It would be interesting to see if that’s optimal, and if the optimal solution is different for different puzzle sizes.