{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T17:10:03Z","timestamp":1741281003564,"version":"3.38.0"},"reference-count":16,"publisher":"Walter de Gruyter GmbH","issue":"4-5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,8,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>This paper deals with the very hard problem of grid coloring that has been specified more than 10 years ago in S. Fenner et al., <jats:italic>Rectangle Free Coloring of Grids<\/jats:italic>, 2009. Available at: <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/www.cs.umd.edu\/%7Egasarch\/papers\/grid.pdf\">http:\/\/www.cs.umd.edu\/\u223cgasarch\/papers\/grid<\/jats:ext-link>.<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/www.cs.umd.edu\/%7Egasarch\/papers\/grid.pdf\">pdf<\/jats:ext-link>. It was unknown whether rectangle-free completely four-colored square grids of sizes 17\u00a0\u00d7\u00a017 and 18\u00a0\u00d7\u00a018 exist. As result of an extensive research I computed commonly with Christian Posthoff a rectangle-free pattern that can be reused cyclic-rotated by 90\u00b0 for the four colors of the grid of size 18\u00a0\u00d7\u00a018 (B. Steinbach and C. Posthoff, \u201cExtremely complex 4-colored rectangle-free grids: solution of open multiple-valued problems,\u201d in <jats:italic>Proceedings of the IEEE 42nd International Symposium on Multiple-Valued Logic<\/jats:italic>, Victoria, BC, Canada, ISMVL, 2012, pp. 37\u201344, B. Steinbach and C. Posthoff, \u201cRectangle-free colorings of extremely complex grids using 4 colors,\u201d <jats:italic>J. Mult.-Valued Log. Soft Comput.<\/jats:italic>, vol. 21, nos. 5\u20136, pp. 609\u2013625, 2013). A similar solution for the grid of size 17\u00a0\u00d7\u00a017 has not been found so far. We explore in this paper for which sizes of square grids rectangle-free four-colored patterns exist, at which the pattern of one color can be reused for another color after a rotation by 90\u00b0.<\/jats:p>","DOI":"10.1515\/itit-2024-0069","type":"journal-article","created":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T03:50:42Z","timestamp":1738986642000},"page":"159-173","source":"Crossref","is-referenced-by-count":0,"title":["Rectangle-free four-colored square grids realized by cyclic-rotated reusable patterns"],"prefix":"10.1515","volume":"66","author":[{"given":"Bernd","family":"Steinbach","sequence":"first","affiliation":[{"name":"Institute of Computer Science , Freiberg University of Mining and Technology , Freiberg , Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2025,2,10]]},"reference":[{"unstructured":"S. Fenner, et al.., Rectangle Free Coloring of Grids, 2009. Available at: http:\/\/www.cs.umd.edu\/~gasarch\/papers\/grid.pdf.","key":"2025030616183072293_j_itit-2024-0069_ref_001"},{"doi-asserted-by":"crossref","unstructured":"B. Steinbach and C. Posthoff, \u201cExtremely complex 4-colored rectangle-free grids: solution of open multiple-valued problems,\u201d in Proceedings of the IEEE 42nd International Symposium on Multiple-Valued Logic, Victoria, BC, Canada, ISMVL, 2012, pp.\u00a037\u201344.","key":"2025030616183072293_j_itit-2024-0069_ref_002","DOI":"10.1109\/ISMVL.2012.12"},{"unstructured":"B. Steinbach and C. Posthoff, \u201cRectangle-free colorings of extremely complex grids using 4 colors,\u201d J. Mult.-Valued Log. Soft Comput., vol.\u00a021, nos. 5\u20136, pp.\u00a0609\u2013625, 2013.","key":"2025030616183072293_j_itit-2024-0069_ref_003"},{"unstructured":"B. Steinbach and C. Posthoff, \u201cHighly complex 4-colored rectangle-free grids \u2013 solution unsolved multiple-valued problems,\u201d J. Mult.-Valued Log. Soft Comput., vol.\u00a024, nos. 1\u20134, pp.\u00a0369\u2013404, 2014.","key":"2025030616183072293_j_itit-2024-0069_ref_004"},{"doi-asserted-by":"crossref","unstructured":"B. Steinbach and C. Posthoff, \u201cSolution of the last open four-colored rectangle-free grid \u2013 an extremely complex multiple-valued problem,\u201d in Proceedings of the IEEE 43nd International Symposium on Multiple-Valued Logic, Toyama, Japan, ISMVL, 2013, pp.\u00a0302\u2013309.","key":"2025030616183072293_j_itit-2024-0069_ref_005","DOI":"10.1109\/ISMVL.2013.51"},{"unstructured":"A. D. Keedwell and J. D\u00e9nes, Latin Squares and their Applications, 2nd ed. Amsterdam, Elsevier, 2015.","key":"2025030616183072293_j_itit-2024-0069_ref_006"},{"doi-asserted-by":"crossref","unstructured":"B. Steinbach and C. Posthoff, Logic Functions and Equations \u2013 Fundamentals and Applications Using the XBOOLE-Monitor, 3rd ed. Nature Switzerland AG, Springer, 2022.","key":"2025030616183072293_j_itit-2024-0069_ref_007","DOI":"10.1007\/978-3-030-88945-6"},{"unstructured":"B. Steinbach and C. Posthoff, \u201cFour-colored rectangle-free grids of the size 12\u00d721,\u201d in Recent Progress in the Boolean Domain, B. Steinbach, Ed., Newcastle upon Tyne, UK, Cambridge Scholars Publishing, 2014, pp.\u00a0121\u2013144.","key":"2025030616183072293_j_itit-2024-0069_ref_008"},{"unstructured":"B. Steinbach and C. Posthoff, \u201cBoolean rectangle problem,\u201d in Recent Progress in the Boolean Domain, B. Steinbach, Ed., Newcastle upon Tyne, UK, Cambridge Scholars Publishing, 2014, pp.\u00a03\u201385.","key":"2025030616183072293_j_itit-2024-0069_ref_009"},{"unstructured":"B. Steinbach and C. Posthoff, \u201cFour-colored rectangle-free grids,\u201d in Recent Progress in the Boolean Domain, B. Steinbach, Ed., Newcastle upon Tyne, UK, Cambridge Scholars Publishing, 2014, pp.\u00a087\u2013144.","key":"2025030616183072293_j_itit-2024-0069_ref_010"},{"unstructured":"B. Steinbach and C. Posthoff, \u201cPermutation classes,\u201d in Recent Progress in the Boolean Domain, B. Steinbach, Ed., Newcastle upon Tyne, UK, Cambridge Scholars Publishing, 2014, pp.\u00a063\u201385.","key":"2025030616183072293_j_itit-2024-0069_ref_011"},{"doi-asserted-by":"crossref","unstructured":"F. A. Aloul, et al.., \u201cSolving difficult SAT instances in the presence of symmetry,\u201d in DAC \u201802: Proceedings of the 39th Annual Design Automation Conference, New York, NY, United States, Association for Computing Machinery, 2002, pp.\u00a0731\u2013736.","key":"2025030616183072293_j_itit-2024-0069_ref_012","DOI":"10.1145\/513918.514102"},{"doi-asserted-by":"crossref","unstructured":"J. Devriendt, et al.., \u201cImproved static symmetry breaking for SAT,\u201d in Theory and Applications of Satisfiability Testing \u2013 SAT 2016, N. Creignou and D. Le Berre, Eds., Cham, Springer International Publishing, 2016, pp.\u00a0104\u2013122.","key":"2025030616183072293_j_itit-2024-0069_ref_013","DOI":"10.1007\/978-3-319-40970-2_8"},{"doi-asserted-by":"crossref","unstructured":"M. J. H. Heule, \u201cOptimal symmetry breaking for graph problems,\u201d Math. Comput. Sci., vol.\u00a013, no. 4, pp.\u00a0533\u2013548, 2019, https:\/\/doi.org\/10.1007\/s11786-019-00397-5.","key":"2025030616183072293_j_itit-2024-0069_ref_014","DOI":"10.1007\/s11786-019-00397-5"},{"doi-asserted-by":"crossref","unstructured":"A. Biere, et al.., Handbook of Satisfiability, Amsterdam, IOS Press, 2021.","key":"2025030616183072293_j_itit-2024-0069_ref_015","DOI":"10.3233\/FAIA336"},{"doi-asserted-by":"crossref","unstructured":"B. Steinbach and C. Posthoff, \u201cArtificial intelligence and creativity. Two requirements to solve an extremely Complex coloring problem,\u201d in Proceedings of the 5th International Conference on Agents and Artificial Intelligence, J. Filipe and A. Fred, Eds., Barcelona, Spain, 2013, pp.\u00a0411\u2013418.","key":"2025030616183072293_j_itit-2024-0069_ref_016","DOI":"10.5220\/0004183004110418"}],"container-title":["it - Information Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2024-0069\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2024-0069\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T16:19:28Z","timestamp":1741277968000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2024-0069\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,1]]},"references-count":16,"journal-issue":{"issue":"4-5","published-online":{"date-parts":[[2025,3,3]]},"published-print":{"date-parts":[[2024,8,26]]}},"alternative-id":["10.1515\/itit-2024-0069"],"URL":"https:\/\/doi.org\/10.1515\/itit-2024-0069","relation":{},"ISSN":["1611-2776","2196-7032"],"issn-type":[{"type":"print","value":"1611-2776"},{"type":"electronic","value":"2196-7032"}],"subject":[],"published":{"date-parts":[[2024,8,1]]}}}