{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T21:40:52Z","timestamp":1765143652952,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,2,17]],"date-time":"2022-02-17T00:00:00Z","timestamp":1645056000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council","doi-asserted-by":"publisher","award":["400159"],"award-info":[{"award-number":["400159"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Checkerboard colouring arguments for proving that a given collection of polyominoes cannot tile a finite target region of the plane are well-known and typically applied on a case-by-case basis. In this article, we give a systematic mathematical treatment of such colouring arguments, based on the concept of a parity violation, which arises from the mismatch between the colouring of the tiles and the colouring of the target region. Identifying parity violations is a combinatorial problem related to the subset sum problem. We convert the combinatorial problem into linear Diophantine equations and give necessary and sufficient conditions for a parity violation. The linear Diophantine equation approach leads to an algorithm implemented in MATLAB for finding all possible parity violations of large tiling problems, and is the main contribution of this article. Numerical examples illustrate the effectiveness of our algorithm. The collection of MATLAB programs, POLYOMINO_PARITY (v2.0.0) is freely available for download.<\/jats:p>","DOI":"10.3390\/a15020065","type":"journal-article","created":{"date-parts":[[2022,2,17]],"date-time":"2022-02-17T20:24:26Z","timestamp":1645129466000},"page":"65","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4980-0514","authenticated-orcid":false,"given":"Marcus R.","family":"Garvie","sequence":"first","affiliation":[{"name":"Department of Mathematics & Statistics, University of Guelph, Guelph, ON N1G 2W1, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0273-2769","authenticated-orcid":false,"given":"John","family":"Burkardt","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Pittsburgh, Pittsburgh, PA 15260, USA"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,17]]},"reference":[{"key":"ref_1","unstructured":"Golomb, S. (1965). Polyominoes, Scribner."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Golomb, S. (1994). Polyominoes, Princeton University Press. [2nd ed.].","DOI":"10.1515\/9780691215051"},{"key":"ref_3","unstructured":"Gr\u00fcnbaum, B., and Shephard, G. (1987). Tilings and Patterns, W.H. Freeman and Company. Chapter 9."},{"key":"ref_4","unstructured":"Gr\u00fcnbaum, B., and Shephard, G. (2016). Tilings and Patterns, Dover Publications. [2nd ed.]."},{"key":"ref_5","unstructured":"Gardner, M. (1988). Time Travel and Other Mathematical Bewilderments, W. H. Freeman and Company."},{"key":"ref_6","unstructured":"Gardner, M. (2009). Hexaflexagons, Probability Paradoxes, and the Tower of Hanoi. Martin Gardner\u2019s First Book of Mathematical Puzzles and Games. New Martin Gardner Mathematical Library, Cambridge University Press."},{"key":"ref_7","unstructured":"Gardner, M. (2009). Sphere packing, Lewis Carroll, and Reversi. Martin Gardner\u2019s new mathematical diversions. New Martin Gardner Mathematical Library, Cambridge University Press."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1080\/00029890.1954.11988548","article-title":"Checker boards and polyominoes","volume":"61","author":"Golomb","year":"1954","journal-title":"Amer. Math. Mon."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/s00283-010-9160-9","article-title":"Tilings","volume":"32","author":"Ardila","year":"2010","journal-title":"Math. Intell."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0097-3165(90)90057-4","article-title":"Tiling with polyominoes and combinatorial group theory","volume":"53","author":"Conway","year":"1990","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_11","first-page":"123","article-title":"Tile homotopy groups","volume":"49","author":"Reid","year":"2003","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"key":"ref_12","unstructured":"Lilly, D. (1978, January 16\u201318). Complexity of solvable cases of the decision problem for predicate calculus. Proceedings of the 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, MI, USA."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"5525","DOI":"10.1090\/S0002-9947-00-02666-0","article-title":"Ribbon tile invariants","volume":"352","author":"Pak","year":"2000","journal-title":"Trans. Amer. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0304-3975(02)00495-4","article-title":"Tile invariants: New horizons","volume":"303","author":"Pak","year":"2003","journal-title":"Theoret. Comput. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1080\/00029890.1990.11995660","article-title":"Conway\u2019s Tiling Groups","volume":"97","author":"Thurston","year":"1990","journal-title":"Amer. Math. Mon."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","article-title":"On representatives of subsets","volume":"s1-10","author":"Hall","year":"1935","journal-title":"J. Lond. Math. Soc."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.tcs.2008.02.033","article-title":"Polyomino coloring and complex numbers","volume":"400","author":"Kirillovs","year":"2008","journal-title":"Theoret. Comput. Sci."},{"key":"ref_18","unstructured":"Tulleken, H. (2022, January 13). Polyominoes: Shapes and Tilings. Self-Published Book (Version 3.3). Available online: https:\/\/www.researchgate.net\/publication\/333296614_Polyominoes."},{"key":"ref_19","unstructured":"Garey, M., and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company."},{"key":"ref_20","unstructured":"Feller, W. (1957). An Introduction to Probability Theory and Its Applications, John Wiley & Sons Inc.. [2nd ed.]."},{"key":"ref_21","unstructured":"Mordell, L. (1969). Diophantine Equations. Pure and Applied Mathematics, Academic Press. [1st ed.]."},{"key":"ref_22","unstructured":"Burkardt, J. (2022, January 13). jvburkardt\/polyomino_parity: Initial Release. Available online: https:\/\/zenodo.org\/record\/5851095#.Yg2y1JYRWUk."},{"key":"ref_23","unstructured":"Burkardt, J. (2022, January 13). jvburkardt\/polyominoes: Initial Release. Available online: https:\/\/zenodo.org\/record\/5851118#.Yg21vJYRWUk."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"95","DOI":"10.55016\/ojs\/cdm.v15i2.62866","article-title":"A new mathematical model for tiling finite regions of the plane with polyominoes","volume":"15","author":"Garvie","year":"2020","journal-title":"Contrib. Discret. Math."},{"key":"ref_25","unstructured":"Busche, M. (2022, January 13). Solving Polyomino and Polycube Puzzles. Algorithms, Software, and Solutions. Available online: http:\/\/www.mattbusche.org\/blog\/article\/polycube\/."},{"key":"ref_26","first-page":"90","article-title":"Programmeren van de pentomino puzzle","volume":"47","year":"1971","journal-title":"Euclides"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1145\/365628.365654","article-title":"A program to solve the Pentomino problem by the recursive use of macros","volume":"8","author":"Fletcher","year":"1965","journal-title":"Commun. ACM"},{"key":"ref_28","unstructured":"Davies, J., Roscoe, B., and Woodcock, J. (2000). Dancing Links. Millennial Perspectives in Computer Science, Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Professor Sir Antony Hoare, Burlington, VT, USA, 13\u201318 June 1999, Cornerstones of Computing, Palgrave Macmillan."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1016\/j.tcs.2005.06.031","article-title":"Enumeration of L-convex polyominoes by rows and columns","volume":"347","author":"Castiglione","year":"2005","journal-title":"Theoret. Comput. Sci."},{"key":"ref_30","first-page":"1","article-title":"On the generation and enumeration of some classes of convex polyominoes","volume":"11","author":"Duchi","year":"2004","journal-title":"Electron. J. Combin."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(84)90116-6","article-title":"Algebraic languages and polyominoes enumeration","volume":"34","author":"Delest","year":"1984","journal-title":"Theoret. Comput. Sci."},{"key":"ref_32","first-page":"57","article-title":"A perimeter enumeration of column-convex polyominoes","volume":"9","year":"2007","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"ref_33","unstructured":"Goodman, J., and O\u2019Rourke, J. (2004). Polyominoes. Handbook of Discrete and Computational Geometry, Chapman & Hall\/CRC. [2nd ed.]."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"2014","DOI":"10.1016\/j.dam.2010.08.011","article-title":"Enumeration of polyominoes inscribed in a rectangle","volume":"158","author":"Goupil","year":"2010","journal-title":"Discret. Appl. Math."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Guttman, A. (2009). History and introduction to polygon models and polyominoes. Polygons, Polyominoes and Polycubes, Springer. Lecture Notes in Physic.","DOI":"10.1007\/978-1-4020-9927-4"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"585","DOI":"10.4153\/CJM-1973-060-4","article-title":"A procedure for improving the upper bound for the number of n-ominoes","volume":"25","author":"Klarner","year":"1973","journal-title":"Can. J. Math."},{"key":"ref_37","first-page":"31","article-title":"Asymptotic bounds for the number of convex n-ominoes","volume":"8","author":"Klarner","year":"1974","journal-title":"Can. J. Math."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1006\/aama.1998.0601","article-title":"Enumeration of symmetry classes of convex polyominoes in the square lattice","volume":"21","author":"Leroux","year":"1998","journal-title":"Adv. Appl. Math."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0166-218X(92)00103-S","article-title":"Codage des polyominos convexes et \u00e9quations pour l'\u00e9num\u00e9ration suivant l'aire","volume":"48","year":"1994","journal-title":"Discret. Appl. Math."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0012-365X(81)90237-5","article-title":"Counting polyominoes: Yet another attack","volume":"36","author":"Redelmeier","year":"1981","journal-title":"Discret. Math."},{"key":"ref_41","first-page":"534","article-title":"Algorithm AS 299: Generation of Simplex Lattice Points","volume":"44","author":"Chasalow","year":"1995","journal-title":"J. R. Stat. Soc. Ser. C"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/65\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:21:52Z","timestamp":1760134912000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,17]]},"references-count":41,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020065"],"URL":"https:\/\/doi.org\/10.3390\/a15020065","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,2,17]]}}}