[maxov]

~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]

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]

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.