9 ms·

I was given an edge-matching puzzle as a kid, similar to this one: https://i.etsystatic.com/17381496/r/il/440b0d/3124003935/il_fullxfull.3124003935_edw8.jpg ht

I was given an edge-matching puzzle as a kid, similar to this one: https://i.etsystatic.com/17381496/r/il/440b0d/3124003935/il_fullxfull.3124003935_edw8.jpg https://i.etsystatic.com/17381496/r/il/440b0d/3124003935/il_... 3x3 tiles, after spending probably days on I gave up a few years later I wrote some code to brute-force the solution, there were a total of two solutions out of ~20 billion possibilities (not including rotations) and the box said "for kids ages 8+"... I suspect the designers just drew it out and cut it up without realising quite how hard it was (NP complete)

teruakohatu 5y ago
I remember those puzzles. Are you sure there was no way for a child to prune the search space?
- gnarbarian 5y ago
  turns out it was a puzzle and OP is blind.
- blibble 5y ago
  I found the pictures I took after beating my childhood nemesis https://imgur.com/a/ICIBZCw https://imgur.com/a/ICIBZCw and https://imgur.com/a/JOWkTsp https://imgur.com/a/JOWkTsp have a go, though I think that was the strategy I was using as a child (and the box actually says 6+... mean)
  - marcosdumay 5y ago
    Yes, you can prune that thing severely. I imagine nearly all branches can be discarded after 5 tiles are positioned and the initial set is invariant to rotations, what leads to "only" many tens of thousands of possibilities. I hated with a passion those puzzles when I was a child, and the people that claimed that they measured intelligence. I had better things to do than mindlessly rearranging pieces in a board until they fit! Strangely, I have much more patience for that now.
maxov 5y ago
~20bn sounds about right. 9! * 4^9 / 4 ~ 23.8bn. Divide by 4 due to rotational symmetry. Absolutely mind-boggling to me that such a small, simple puzzle has such an extreme search space! Great example of P vs NP, time to build a Where’s Waldo matching game cryptosystem.
- cousin_it 5y ago
  I think a naive tree search (start from one tile and try adding others with matching edges) might find a solution pretty fast, because most of the search space gets discarded early.
  - maxov 5y ago
    Good point! I think this heuristic works well if the edges between tiles in completed picture are uniquely identifiable or close to that. However from the images there seem to be only 4 "colors" of edges in the puzzle (8 if you count two orientations for each character), so I think this will prune the search space to "only" perhaps around 100k-500k. Still really good, this makes the search space 50k-250k times smaller.
dunco 5y ago
The puzzle performed exactly as desired by giving your parents a few days off! They were the customer, not you haha!
saagarjha 5y ago
There are 43 quintillion Rubik's cube arrangements, and only one of them is the right one. Of course, this hasn't stopped children from solving the cube and even developing their own algorithms ;)
- SomeHacker44 5y ago
  IMO the cube has partial solutions that simplify the problem as you go. This "game" seems more like a penrose tiling. Any mistake may not be apparent until you cannot put a piece, thus there is relatively little simplification and it may not be apparent how far you must undo the puzzle to make additional progress. Just my gut feeling on the comparison of the two games.

teruakohatu 5y ago

I remember those puzzles. Are you sure there was no way for a child to prune the search space?

gnarbarian 5y ago
turns out it was a puzzle and OP is blind.
blibble 5y ago
I found the pictures I took after beating my childhood nemesis https://imgur.com/a/ICIBZCw https://imgur.com/a/ICIBZCw and https://imgur.com/a/JOWkTsp https://imgur.com/a/JOWkTsp have a go, though I think that was the strategy I was using as a child (and the box actually says 6+... mean)
- marcosdumay 5y ago
  Yes, you can prune that thing severely. I imagine nearly all branches can be discarded after 5 tiles are positioned and the initial set is invariant to rotations, what leads to "only" many tens of thousands of possibilities. I hated with a passion those puzzles when I was a child, and the people that claimed that they measured intelligence. I had better things to do than mindlessly rearranging pieces in a board until they fit! Strangely, I have much more patience for that now.

maxov 5y ago

~20bn sounds about right. 9! * 4^9 / 4 ~ 23.8bn. Divide by 4 due to rotational symmetry. Absolutely mind-boggling to me that such a small, simple puzzle has such an extreme search space! Great example of P vs NP, time to build a Where’s Waldo matching game cryptosystem.

cousin_it 5y ago
I think a naive tree search (start from one tile and try adding others with matching edges) might find a solution pretty fast, because most of the search space gets discarded early.
- maxov 5y ago
  Good point! I think this heuristic works well if the edges between tiles in completed picture are uniquely identifiable or close to that. However from the images there seem to be only 4 "colors" of edges in the puzzle (8 if you count two orientations for each character), so I think this will prune the search space to "only" perhaps around 100k-500k. Still really good, this makes the search space 50k-250k times smaller.

dunco 5y ago

The puzzle performed exactly as desired by giving your parents a few days off! They were the customer, not you haha!

saagarjha 5y ago

There are 43 quintillion Rubik's cube arrangements, and only one of them is the right one. Of course, this hasn't stopped children from solving the cube and even developing their own algorithms ;)

SomeHacker44 5y ago
IMO the cube has partial solutions that simplify the problem as you go. This "game" seems more like a penrose tiling. Any mistake may not be apparent until you cannot put a piece, thus there is relatively little simplification and it may not be apparent how far you must undo the puzzle to make additional progress. Just my gut feeling on the comparison of the two games.