No Easy Puzzles: A Hardness Result for Jigsaw Puzzles

1. Norgate, M.: Cutting borders: Dissected maps and the origins of the jigsaw puzzle. Cartogr. J. 44(4), 342–350 (2007)

   Article  Google Scholar 

2. Yao, F.H., Shao, G.F.: A shape and image merging technique to solve jigsaw puzzles. Pattern Recogn. Lett. 24, 1819–1835 (2003)

   Article  Google Scholar 

3. Freeman, H., Garder, L.: Apictorial jigsaw puzzles: The computer solution of a problem in pattern recognition. IEEE Trans. Electron. Comput. EC-13, 118–127 (1964)

   Google Scholar 

4. Kleber, F., Sablatnig, R.: Scientific puzzle solving: current techniques and applications. In: Computer Applications to Archaeology (CAA 2009), Williamsburg, Virginia (March 2009)

   Google Scholar 

5. Kong, W., Kimia, B.B.: On solving 2D and 3D puzzles using curve matching. In: Proc. IEEE Conf. Computer Vision and Pattern Recognition, Hawaii (December 2001)

   Google Scholar 

6. Radack, G.M., Badler, N.I.: Jigsaw puzzle matching using a boundary-centered polar encoding. Comput. Vision Graph. 19, 1–17 (1982)

   Google Scholar 

7. Webster, R.W., Ross, P.W., Lafollette, P.S., Stafford, R.L.: A computer vision system that assembles canonical jigsaw puzzles using the euclidean skeleton and Isthmus critical points. In: IAPR Workshop on Machine Vision Applications (MVA 1990), Tokyo, IAPR, pp. 118–127 (November 1990)

   Google Scholar 

8. Gallagher, A.C.: Jigsaw puzzles with pieces of unknown orientation. In: 25th Conf. Computer Vision and Pattern Recognition (CVPR 2012), Providence, Rhode Island (June 2012)

   Google Scholar 

9. Sağıroğlu, M.Ş., Erçil, A.: Optimization for automated assembly of puzzles. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research 18(2), 321–338 (2010)

   Article  MATH  Google Scholar 

10. Wolfson, H., Schonberg, E., Kalvin, A., Lamdan, Y.: Solving jigsaw puzzles by computer. Ann. Oper. Res. 12(1-4), 51–64 (1988)

    Article  MathSciNet  Google Scholar 

11. Arvind, V., Köbler, J.: Graph isomorphism is low for ZPP(NP) and other lowness results. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 431–442. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

12. Arvind, V., Kukur, P.P.: Graph isomorphism is in SPP. Inform. Comput. 204(5), 835–852 (2006)

    Article  MATH  Google Scholar 

13. Köbler, J., Schoöning, U., Torán, J.: Graph isomorphism is low for PP. Comput. Complex. 2(4), 301–330 (1992)

    Article  MATH  Google Scholar 

14. McKay, B.D.: Practical graph isomorphism. In: 10th Manitoba Conf. Numerical Mathematics and Computing (Winnipeg, 1980). Congressus Numerantium, vol. 30, pp. 45–86 (1981)

    Google Scholar 

15. Cook, S.A.: The complexity of theorem-proving procedures. In: Proc. 3rd ACM Symp. Theory of Computing (STOC), pp. 151–158 (1971)

    Google Scholar 

16. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman & Co (1979)

    Google Scholar 

17. Gröger, H.D.: On the randomized complexity of monotone graph properties. Acta Cybernet. 10(3), 119–127 (1992)

    MATH  MathSciNet  Google Scholar 

18. Ullman, J.R.: An algorithm for subgraph isomorphism. J. ACM 23(1), 31–42 (1976)

    Article  MATH  Google Scholar 

19. Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997)

    MATH  Google Scholar 

20. Gindre, F., Trejo Pizzo, D.A., Barrera, G.: Daniela Lopez De Luise, M.: A criterion-based genetic algorithm solution to the jigsaw puzzle NP-complete problem. In: Proc. World Congress on Engineering and Computer Science (WCECS 2010), San Francisco (October 2010)

    Google Scholar 

21. Goldberg, D., Malon, C., Bern, M.: A global approach to automatic solution of jigsaw puzzles. Comput. Geom. 28(2-3), 165–174 (2004)

    Article  MathSciNet  Google Scholar 

22. Gwee, B.H., Lim, M.H.: Polyominoes tiling by a genetic algorithm. Comput. Optim. Appl. 6(3), 273–291 (1996)

    Article  MATH  MathSciNet  Google Scholar 

23. Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25, 42–65 (1982)

    Article  MATH  MathSciNet  Google Scholar 

24. Demaine, E.D., Demaine, M.L.: Jigsaw puzzles, edge matching, and polyomino packing: connections and complexity. Graphs Combin. 23(suppl. 1), 195–208 (2007)

    Google Scholar 

25. Hall, P.: On representatives of subsets. J. London Math. Soc. 10(1), 26–30 (1935)

    Google Scholar 

26. Halmos, P.R., Vaughan, H.E.: The marriage problem. Am. J. Math. 72, 214–215 (1950)

    Article  MATH  MathSciNet  Google Scholar 

Download references