{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T04:24:29Z","timestamp":1765254269240,"version":"build-2065373602"},"reference-count":72,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2022,5,12]],"date-time":"2022-05-12T00:00:00Z","timestamp":1652313600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSERC Discovery","award":["# 400159"],"award-info":[{"award-number":["# 400159"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The general problem of tiling finite regions of the plane with polyominoes is NP-complete, and so the associated computational geometry problem rapidly becomes intractable for large instances. Thus, the need to reduce algorithm complexity for tiling is important and continues as a fruitful area of research. Traditional approaches to tiling with polyominoes use backtracking, which is a refinement of the \u2018brute-force\u2019 solution procedure for exhaustively finding all solutions to a combinatorial search problem. In this work, we combine checkerboard colouring techniques with a recently introduced integer linear programming (ILP) technique for tiling with polyominoes. The colouring arguments often split large tiling problems into smaller subproblems, each represented as a separate ILP problem. Problems that are amenable to this approach are embarrassingly parallel, and our work provides proof of concept of a parallelizable algorithm. The main goal is to analyze when this approach yields a potential parallel speedup. The novel colouring technique shows excellent promise in yielding a parallel speedup for finding large tiling solutions with ILP, particularly when we seek a single (optimal) solution. We also classify the tiling problems that result from applying our colouring technique according to different criteria and compute representative examples using a combination of MATLAB and CPLEX, a commercial optimization package that can solve ILP problems. The collections of MATLAB programs PARIOMINOES (v3.0.0) and POLYOMINOES (v2.1.4) used to construct the ILP problems are freely available for download.<\/jats:p>","DOI":"10.3390\/a15050164","type":"journal-article","created":{"date-parts":[[2022,5,12]],"date-time":"2022-05-12T21:46:53Z","timestamp":1652392013000},"page":"164","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A Parallelizable Integer Linear Programming Approach for Tiling Finite Regions of the Plane with Polyominoes"],"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,5,12]]},"reference":[{"key":"ref_1","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_2","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_3","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_4","first-page":"57","article-title":"A perimeter enumeration of column-convex polyominoes","volume":"9","year":"2007","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"ref_5","unstructured":"Goodman, J., and O\u2019Rourke, J. (2004). Polyominoes. Handbook of Discrete and Computational Geometry, Chapman & Hall\/CRC. [2nd ed.]."},{"key":"ref_6","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":"Discrete Appl. Math."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Guttman, A. (2009). History and introduction to polygon models and polyominoes. Polygons, Polyominoes and Polycubes, Springer. Lecture Notes in Physics.","DOI":"10.1007\/978-1-4020-9927-4"},{"key":"ref_8","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_9","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_10","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_11","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\u2018\u00e9num\u00e9ration suivant l\u2018aire","volume":"48","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"ref_12","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":"Discrete Math."},{"key":"ref_13","unstructured":"Golomb, S. (1965). Polyominoes, Scribner."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Golomb, S. (1994). Polyominoes, Princeton University Press. [2nd ed.].","DOI":"10.1515\/9780691215051"},{"key":"ref_15","unstructured":"Gr\u00fcnbaum, B., and Shephard, G. (1987). Tilings and Patterns, W.H. Freeman and Company. Chapter 9."},{"key":"ref_16","unstructured":"Gr\u00fcnbaum, B., and Shephard, G. (2016). Tilings and Patterns, Dover Publications. [2nd ed.]."},{"key":"ref_17","first-page":"1","article-title":"The undecidability of the domino problem","volume":"66","author":"Berger","year":"1966","journal-title":"Mem. Am. Math. Soc."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1080\/0025570X.1984.11977126","article-title":"Polymorphic Polyominoes","volume":"57","author":"Fontaine","year":"1984","journal-title":"Math. Mag."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/S0021-9800(70)80055-2","article-title":"Tiling with Sets of Polyominoes","volume":"9","author":"Golomb","year":"1970","journal-title":"J. Comb. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1112\/plms\/pdw017","article-title":"Tiling with arbitrary tiles","volume":"3","author":"Gruslys","year":"2016","journal-title":"Proc. Lond. Math. Soc."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/j.cam.2004.05.002","article-title":"Planar tilings by polyominoes, polyhexes, and polyiamonds","volume":"174","author":"Rhoads","year":"2005","journal-title":"J. Comput. Appl. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1080\/0025570X.1980.11976859","article-title":"Will It Tile? Try the Conway Criterion!","volume":"53","author":"Schattschneider","year":"1980","journal-title":"Math. Mag."},{"key":"ref_23","unstructured":"Winslow, A. (2015, January 9\u201311). An optimal algorithm for tiling the plane with a translated polyomino. Proceedings of the 26th International Symposium, ISAAC 2015, Nagoya, Japan."},{"key":"ref_24","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_25","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1080\/0025570X.2004.11953226","article-title":"Tiling Deficient Rectangles with Trominoes","volume":"77","author":"Ash","year":"2004","journal-title":"Math. Mag."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Ashlock, D., and Taylor, L. (2016, January 24\u201329). Evolving Polyomino Puzzles. Proceedings of the 2016 IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada.","DOI":"10.1109\/CEC.2016.7743812"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Bodini, O. (2003, January 16\u201319). Tiling a Rectangle with Polyominoes. Proceedings of the Conference of Discrete Models for Complex Systems, DMCS\u201903, Lyon, France.","DOI":"10.46298\/dmtcs.2313"},{"key":"ref_28","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":"Am. Math. Mon."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/S0021-9800(66)80033-9","article-title":"Tiling with Polyominoes","volume":"1","author":"Golomb","year":"1966","journal-title":"J. Comb. Theory"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0097-3165(89)90082-4","article-title":"Polyominoes Which Tile Rectangles","volume":"51","author":"Golomb","year":"1989","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/BF03027292","article-title":"Tiling rectangles with polyominoes","volume":"18","author":"Golomb","year":"1996","journal-title":"Math. Intell."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0021-9800(69)80044-X","article-title":"Packing a rectangle with congruent n-ominoes","volume":"7","author":"Klarner","year":"1969","journal-title":"J. Comb. Theory"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1006\/jcta.1997.2730","article-title":"Packing Rectangles with Congruent Polyominoes","volume":"77","author":"Marshall","year":"1997","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1007\/s00454-001-0047-6","article-title":"Hard Tiling Problems with Simple Tiles","volume":"26","author":"Moore","year":"2001","journal-title":"Discrete Comput. Geom."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0012-365X(88)90081-7","article-title":"Tiling complexity of small n-ominoes (n<10)","volume":"70","author":"Rawsthorne","year":"1988","journal-title":"Discrete Math."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1006\/jcta.1997.2788","article-title":"Tiling Rectangles and Half Strips with Congruent Polyominoes","volume":"80","author":"Reid","year":"1997","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.jcta.2004.10.010","article-title":"Klarner systems and tiling boxes with polyominoes","volume":"111","author":"Reid","year":"2005","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/802","article-title":"Asymptotically Optimal Box Packing Theorems","volume":"15","author":"Reid","year":"2008","journal-title":"Electron. J. Combin."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/s00026-014-0226-9","article-title":"Many L-Shaped Polyominoes Have Odd Rectangular Packings","volume":"18","author":"Reid","year":"2014","journal-title":"Ann. Comb."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1080\/00029890.1987.12000693","article-title":"Fourteen Proofs of a Result About Tiling a Rectangle","volume":"94","author":"Wagon","year":"1987","journal-title":"Am. Math. Mon."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Korte, B., and Vygen, J. (2018). Combinatorial Optimization: Theory and Algorithms, Springer. [6th ed.]. Algorithms and Combinatorics.","DOI":"10.1007\/978-3-662-56039-6"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Takabatake, K., Yanagisawa, K., and Akiyama, Y. (2022). Solving Generalized Polyomino Puzzles Using the Ising Model. Entropy, 24.","DOI":"10.3390\/e24030354"},{"key":"ref_43","unstructured":"Greenwood, G. (2001, January 27\u201330). Finding solutions to NP problems: Philosophical differences between quantum and evolutionary search algorithms. Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No. 01TH8546), Seoul, Korea."},{"key":"ref_44","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_45","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s00373-007-0713-4","article-title":"Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity","volume":"23","author":"Demaine","year":"2007","journal-title":"Graphs Comb."},{"key":"ref_46","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_47","doi-asserted-by":"crossref","unstructured":"Garvie, M.R., and Burkardt, J. (2022). A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems. Algorithms, 15.","DOI":"10.3390\/a15020065"},{"key":"ref_48","unstructured":"Busche, M. (2022, March 20). Solving Polyomino and Polycube Puzzles. Algorithms, Software, and Solutions. Available online: http:\/\/www.mattbusche.org\/blog\/article\/polycube\/."},{"key":"ref_49","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_50","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, Oxford University, Oxford, UK, September 1999, Red Globe Press. Cornerstones of Computing."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1145\/321296.321300","article-title":"Backtrack Programming","volume":"12","author":"Golomb","year":"1965","journal-title":"J. ACM"},{"key":"ref_52","unstructured":"Knuth, D. (2020). The Art of Computer Programming, Fascicle 5: Mathematical Preliminaries Redux, Addison-Wesley. Introduction to Backtracking; Dancing Links."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF00247795","article-title":"Polyominoes tiling by a genetic algorithm","volume":"6","author":"Gwee","year":"1996","journal-title":"Comput. Optim. Appl."},{"key":"ref_54","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_55","first-page":"123","article-title":"Tile homotopy groups","volume":"49","author":"Reid","year":"2003","journal-title":"L\u2019Enseign. Math."},{"key":"ref_56","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":"Am. Math. Mon."},{"key":"ref_57","unstructured":"Aho, A., Hopcroft, J., and Ullman, J. (1974). The Design and Analysis of Computer Algorithms, Addison-Wesley. [1st ed.]."},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Marek, V. (2009). Introduction to Mathematics of Satisfiability, CRC Press. [1st ed.].","DOI":"10.1201\/9781439801741"},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Biere, A., Heule, M., Maaren, H.V., and Walsh, T. (2021). Handbook of Satisfiability, IOS Press. [2nd ed.]. Frontiers in Artificial Intelligence and Applications.","DOI":"10.3233\/FAIA336"},{"key":"ref_60","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_61","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_62","unstructured":"Mordell, L. (1969). Diophantine Equations, Academic Press. [1st ed.]. Pure and Applied Mathematics."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0097-3165(93)90086-N","article-title":"Geometry, complexity, and combinatorics of permutation polytopes","volume":"64","author":"Onn","year":"1993","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_64","doi-asserted-by":"crossref","unstructured":"Ziegler, G. (1995). Lectures on Polytopes, Springer. [7th ed.]. Graduate Texts in Mathematics.","DOI":"10.1007\/978-1-4613-8431-1"},{"key":"ref_65","unstructured":"Quinn, M. (2003). Parallel Programming in C with MPI and OpenMP, McGraw-Hill. [1st ed.]."},{"key":"ref_66","unstructured":"Alsop, T. (2022, March 20). \u201cNumber of Computer Cores in the 10 Fastest Supercomputers in the World in 2020\u201d From Statista\u2014A Web Resource for Market and Consumer Data. Available online: https:\/\/www.statista.com\/statistics\/268280\/number-of-computer-cores-in-selected-supercomputers-worldwide."},{"key":"ref_67","unstructured":"Czech, Z.J. (2017). Introduction to Parallel Computing, Cambridge University Press. [1st ed.]."},{"key":"ref_68","unstructured":"Weisstein, E. (2022, March 20). \u201cEternity\u201d. From MathWorld\u2014A Wolfram Web Resource. Available online: https:\/\/mathworld.wolfram.com\/Eternity.html."},{"key":"ref_69","unstructured":"Knuth, D. (2022, March 20). Dancing Links. Available online: https:\/\/arxiv.org\/abs\/cs\/0011047."},{"key":"ref_70","unstructured":"Rosenhouse, J., and Taalman, L. (2011). Taking Sudoku Seriously. The Math behind the World\u2019s Most Popular Pencil Puzzle, Oxford University Press."},{"key":"ref_71","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.disc.2007.12.043","article-title":"A survey of known results and research areas for n-queens","volume":"309","author":"Bell","year":"2009","journal-title":"Discret. Math."},{"key":"ref_72","doi-asserted-by":"crossref","first-page":"916","DOI":"10.1137\/140987869","article-title":"A Global Approach for Solving Edge-Matching Puzzles","volume":"8","author":"Kovalsky","year":"2015","journal-title":"SIAM J. Imaging Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/5\/164\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:09:47Z","timestamp":1760137787000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/5\/164"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,12]]},"references-count":72,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,5]]}},"alternative-id":["a15050164"],"URL":"https:\/\/doi.org\/10.3390\/a15050164","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,5,12]]}}}