A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles

We consider a problem introduced by Mossel and Ross (‘Shotgun assembly of labeled graphs’, arXiv:1504.07682). Suppose a random n × n jigsaw puzzle is constructed by independently and uniformly choosing the shape of each ‘jig’ from q possibilities. We are given the shuffled pieces. Then, depending on q, what is the probability that we can reassemble the puzzle uniquely? We say that two solutions of a puzzle are similar if they only differ by a global rotation of the puzzle, permutation of duplicate pieces, and rotation of rotationally symmetric pieces. In this paper, we show that, with high probability, such a puzzle has at least two non-similar solutions when 2 ⩽ q ⩽ 2e−1/2n, all solutions are similar when q ⩾ (2+ϵ)n, and the solution is unique when q = ω(n).

• Publication year

  2017

• Venue

  Combinatorics, probability & computing

• Publication date

  2017-01-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1017/S0963548318000391arXiv 1701.04813
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Reconstructing Random Jigsaws

  2017cited by this paper
• Even 1×n Edge-Matching and Jigsaw Puzzles are Really Hard

  2016cited by this paper
• Shotgun assembly of random jigsaw puzzles

  2016cited by this paper
• Shotgun edge assembly of random jigsaw puzzles

  2016cited by this paper
• Unique reconstruction threshold for random jigsaw puzzles

  2016cited by this paper
• Shotgun Assembly of Labeled Graphs

  2015influential reference
• Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity

  2007cited by this paper

• Shotgun assembly of unlabeled Erdős–Rényi graphs

  2025cites this paper
• An Algorithm to Recover Shredded Random Matrices

  2023cites this paper
• Shotgun Threshold for Sparse Erdős–Rényi Graphs

  2022cites this paper
• Shotgun assembly threshold for lattice labeling model

  2022cites this paper
• Reconstructing Random Pictures

  2022influential citation
• Shotgun assembly of random graphs

  2022cites this paper
• Shotgun assembly of unlabeled Erdos-Renyi graphs

  2021cites this paper
• Shotgun assembly of Erdős-Rényi random graphs

  2020cites this paper
• Shotgun reconstruction in the hypercube

  2019cites this paper
• Topics in extremal graph theory and probabilistic combinatorics

  2018cites this paper
• Reconstructing Random Jigsaws

  2017cites this paper
• Shotgun assembly of random jigsaw puzzles

  2016cites this paper
• Shotgun Assembly of Labeled Graphs

  2015cites this paper
• MIT Open Access Articles Shotgun assembly of Erdős-Rényi random graphs

  year unknowncites this paper