Cited By
View all- Pich AFalomir Z(2018)Logical composition of qualitative shapes applied to solve spatial reasoning testsCognitive Systems Research10.1016/j.cogsys.2018.06.00252:C(82-102)Online publication date: 1-Dec-2018
No easy puzzles
Pages 2 - 11
Abstract
We model jigsaw puzzle solving and study the number of edge matchings required.Realistic jigsaw puzzles require ( n 2 ) comparisons in the worst case.Realistic jigsaw puzzles require ( n 2 ) comparisons on average.Generalised puzzles require (tightly) O ( n 2 ) and ( n log n ) comparisons. We show that solving (bounded-degree) jigsaw puzzles requires ( n 2 ) edge matching comparisons both in the worst case and in expectation, making all jigsaw puzzles as hard to solve as the trivial upper bound. This result applies to bounded-degree puzzles of all shapes, whether pictorial or apictorial. For non-bounded degree puzzles, we show that ( n log n ) is a tight bound.
References
[1]
Vikraman Arvind, Johannes Köbler, Graph isomorphism is low for ZPP(NP) and other lowness results, in: Lect. Notes Comput. Sc., vol. 1770, Springer Verlag, 2000, pp. 431-442.
[2]
Vikraman Arvind, Piyush P. Kukur, Graph isomorphism is in SPP, Inform. and Comput., 204 (2006) 835-852.
[3]
Hans L. Bodlaender, Dynamic programming on graphs with bounded treewidth, in: Lecture Notes in Comput. Sci., vol. 317, Springer, Berlin, 1988, pp. 105-118.
[4]
S.A. Cook, The complexity of theorem-proving procedures, in: Proc. 3rd ACM Symp. Theory of Computing, 1971, pp. 151-158.
[5]
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Section 8.1: lower bounds for sorting, in: Introduction to Algorithms, MIT Press and McGrow-Hill, 2001, pp. 165-168.
[6]
Erik D. Demaine, Martin L. Demaine, Jigsaw puzzles, edge matching, and polyomino packing: connections and complexity, Graphs Combin., 23 (2007) 195-208.
[7]
E. Allen Emerson, Joseph Y. Halpern, Decision procedures and expressiveness in the temporal logic of branching time, J. Comput. System Sci., 30 (1985) 1-24.
[8]
H. Freeman, L. Garder, Apictorial jigsaw puzzles: the computer solution of a problem in pattern recognition, IEEE Trans. Electron. Comput., C-13 (1964) 118-127.
[9]
Andrew C. Gallagher, Jigsaw puzzles with pieces of unknown orientation, in: 25th Conf. Computer Vision and Pattern Recognition, CVPR '12, Providence, Rhode Island, June 2012, pp. 382-389.
[10]
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., 1979.
[11]
Francisco Gindre, David A. Trejo Pizzo, Gabriel Barrera, M. Daniela Lopez De Luise, 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, Oct. 2010, pp. 367-372.
[12]
David Goldberg, Christopher Malon, Marshall Bern, A global approach to automatic solution of jigsaw puzzles, Comput. Geom., 28 (2004) 165-174.
[13]
Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Publishing Company, Reading, MA, 1989.
[14]
Hans D. Gröger, On the randomized complexity of monotone graph properties, Acta Cybernet., 10 (1992) 119-127.
[15]
B.H. Gwee, M.H. Lim, Polyominoes tiling by a genetic algorithm, Comput. Optim. Appl., 6 (1996) 273-291.
[16]
Philip Hall, On representatives of subsets, J. Lond. Math. Soc., 10 (1935) 26-30.
[17]
Paul R. Halmos, Herbert E. Vaughan, The marriage problem, Amer. J. Math., 72 (1950) 214-215.
[18]
Florian Kleber, Robert Sablatnig, Scientific puzzle solving: current techniques and applications, in: Computer Applications to Archaeology, CAA 2009, Williamsburg, Virginia, March 2009.
[19]
D.E. Knuth, Section 5.3.1: minimum-comparison sorting, in: The Art of Computer Programming: Sorting and Searching, vol. 3, Addison-Wesley, 1997, pp. 180-197.
[20]
Johannes Köbler, Uwe Schoöning, Jacobo Torán, Graph isomorphism is low for PP, Comput. Complexity, 2 (1992) 301-330.
[21]
Weixin Kong, Benjamin B. Kimia, On solving 2D and 3D puzzles using curve matching, in: Proc. IEEE Conf. Computer Vision and Pattern Recognition, Hawaii, Dec. 2001, pp. 583-590.
[22]
Eyal Kushilevitz, Noam Nisan, Communication Complexity, Cambridge University Press, New York, NY, USA, 1997.
[23]
Eugene M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. System Sci., 25 (1982) 42-65.
[24]
Brendan D. McKay, Practical graph isomorphism, Congr. Num., 30 (1981) 45-86.
[25]
Martin Norgate, Cutting borders: dissected maps and the origins of the jigsaw puzzle, Cartogr. J., 44 (December 2007) 342-350.
[26]
G.M. Radack, N.I. Badler, Jigsaw puzzle matching using a boundary-centered polar encoding, Comput. Vis. Graph., 19 (1982) 1-17.
[27]
Mahmut Şamil Sağıroğlu, Aytül Erçil, Optimization for automated assembly of puzzles, TOP, 18 (2010) 321-338.
[28]
Alan M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. Lond. Math. Soc., 42 (1936) 230-265.
[29]
Julian R. Ullman, An algorithm for subgraph isomorphism, J. ACM, 23 (1976) 31-42.
[30]
Heribert Vollmer, Introduction to Circuit Complexity: A Uniform Approach, Springer-Verlag, Berlin, 1999.
[31]
Roger W. Webster, Paul W. Ross, Paul S. Lafollette, Robert L. Stafford, 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'90, Tokyo, IAPR, Nov. 1990, pp. 118-127.
[32]
Haim Wolfson, Edith Schonberg, Alan Kalvin, Yehezkel Lamdan, Solving jigsaw puzzles by computer, Ann. Oper. Res., 12 (1988) 51-64.
[33]
Feng-Hui Yao, Gui-Feng Shao, A shape and image merging technique to solve jigsaw puzzles, Pattern Recogn. Lett., 24 (2003) 1819-1835.
Recommendations
Automatic Solution of Jigsaw Puzzles
We present a method for automatically solving apictorial jigsaw puzzles that is based on an extension of the method of differential invariant signatures. Our algorithms are designed to solve challenging puzzles, without having to impose any restrictive ...
A new technique for solving puzzles
Special issue on game theoryThis paper proposes a new technique for solving jigsaw puzzles. The novelty of the proposed technique is that it provides an automatic jigsaw puzzle solution without any initial restriction about the shape of pieces, the number of neighbor pieces, etc. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V.
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 27 June 2015
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 01 Jan 2025
Other Metrics
Citations
Cited By
View all- Pich AFalomir Z(2018)Logical composition of qualitative shapes applied to solve spatial reasoning testsCognitive Systems Research10.1016/j.cogsys.2018.06.00252:C(82-102)Online publication date: 1-Dec-2018