Unique reconstruction threshold for random jigsaw puzzles

Rajko Nenadov, Pascal Pfister, Angelika Steger

A random jigsaw puzzle is constructed by arranging $n^2$ square pieces into an $n\times n$ grid and assigning to each edge of a piece one of $q$ available colours uniformly at ran…