Office for Technology Commercialization
http://www.research.umn.edu/techcomm
612-624-0550

Jigsaw Puzzle Solver

Technology #20120158

Questions about this technology? Ask a Technology Manager

Download Printable PDF

Image Gallery
Jigsaw Puzzle SolverShredded Document ReconstructionJigsaw Puzzle Solver
Categories
Researchers
Peter Olver, PhD
Mathmatics, College of Science and Engineering
External Link (www2.math.umn.edu)
Managed By
Andrew Morrow
Technology Licensing Officer

Shredded Document Reconstruction

The automatic jigsaw puzzle solving algorithm has potential uses in the reconstruction of shredded documents, assembly of broken artifacts in archeology and other assembly applications. The algorithm uses only the shapes of the pieces (not the picture itself formed by the puzzle) to solve the puzzle. No assumptions are made regarding the shapes or the overall layout and shape of the puzzle itself.

Curve Recognition Algorithm is More Robust

The solving of jigsaw puzzles belongs to a class of problems for which humans have a natural aptitude but remains more challenging for automated algorithms. Previous puzzle solving algorithms have relied strongly on assumptions that the puzzle pieces have a standard shape and fit into a rectangular array. The described algorithm uses curve recognition to parameterize the Euclidean signature curve. As such, the method does not require such assumptions regarding the shape of the puzzle, shapes of the individual pieces or their intrinsic arrangement and thus a much more robust algorithm.

Benefits of Robust Automatic Jigsaw Puzzle Solver

  • Does not rely on assumptions regarding the shape of the puzzle, shapes of the individual pieces or their intrinsic arrangement.
  • The puzzle solving algorithm has been used to solve two commercially available puzzles.
  • The algorithm has potential uses in the reconstruction of shredded documents and in the assembly of broken artifacts in archeology.

Phase of Development A finished preprint presenting the mathematical algorithms, along with working Matlab code has been successfully run on two challenging commercially available puzzles.