4 ms·
~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 su
by 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 agoI 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 agoGood 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.