{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T10:40:25Z","timestamp":1778150425628,"version":"3.51.4"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,3,1]],"date-time":"2024-03-01T00:00:00Z","timestamp":1709251200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,10]],"date-time":"2024-03-10T00:00:00Z","timestamp":1710028800000},"content-version":"vor","delay-in-days":9,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Democritus University of Thrace"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The use of Cellular Automata (CA) in combination with Learning Automata (LA) has demonstrated effectiveness in handling hard-to-be-solved problems. Due to their capacity to learn and adapt, as well as their inherent parallelism, they can expedite the problem-solving process for a range of problems, such as challenging logic puzzles. One such puzzle is Sudoku, which poses a combinatorial optimization challenge of great difficulty and complexity. In this study, a Sudoku puzzle was represented as an Irregular Learning Cellular Automaton (ILCA), using a reward and penalty algorithm to resolve it. Simulations for an amount of 400 puzzles were performed, while the results demonstrate that the proposed algorithm operates effectively, highlighting the concurrent and learning capabilities of the ILCA structure. Furthermore, two different performance enhancement methods are investigated, namely learning rates method and selective probability reset rule, which are able to increase the initial performance by <jats:inline-formula><jats:alternatives><jats:tex-math>$$26.8\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>26.8<\/mml:mn>\n                    <mml:mo>%<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and to achieve an overall <jats:inline-formula><jats:alternatives><jats:tex-math>$$99.3\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>99.3<\/mml:mn>\n                    <mml:mo>%<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> resolution rate.\n<\/jats:p>","DOI":"10.1007\/s11047-024-09975-4","type":"journal-article","created":{"date-parts":[[2024,3,10]],"date-time":"2024-03-10T20:01:30Z","timestamp":1710100890000},"page":"41-60","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Handling Sudoku puzzles with irregular learning cellular automata"],"prefix":"10.1007","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2587-1895","authenticated-orcid":false,"given":"Theodoros Panagiotis","family":"Chatzinikolaou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1856-1813","authenticated-orcid":false,"given":"Rafailia-Eleni","family":"Karamani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8032-1725","authenticated-orcid":false,"given":"Iosif-Angelos","family":"Fyrigos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8240-484X","authenticated-orcid":false,"given":"Georgios Ch.","family":"Sirakoulis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,10]]},"reference":[{"key":"9975_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.asoc.2016.12.006","volume":"53","author":"M Ahangaran","year":"2017","unstructured":"Ahangaran M, Taghizadeh N, Beigy H (2017) Associative cellular learning automata and its applications. Appl Soft Comput 53:1\u201318","journal-title":"Appl Soft Comput"},{"issue":"7","key":"9975_CR2","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1002\/gps.5085","volume":"34","author":"H Brooker","year":"2019","unstructured":"Brooker H, Wesnes KA, Ballard C et al (2019) The relationship between the frequency of number-puzzle use and baseline cognitive function in a large online sample of adults aged 50 and over. Int J Geriatr Psychiatry 34(7):932\u2013940","journal-title":"Int J Geriatr Psychiatry"},{"key":"9975_CR3","doi-asserted-by":"crossref","unstructured":"Chatzinikolaou TP, Fyrigos IA, Karamani RE, et\u00a0al (2020) Memristive oscillatory circuits for resolution of np-complete logic puzzles: Sudoku case. In: 2020 ISCAS, pp 1\u20135","DOI":"10.1109\/ISCAS45731.2020.9181110"},{"key":"9975_CR4","doi-asserted-by":"crossref","unstructured":"Chatzinikolaou TP, Karamani RE, Sirakoulis GC (2022) Irregular learning cellular automata for the resolution of complex logic puzzles. In: Chopard B, Bandini S, Dennunzio A, et\u00a0al (eds) Cellular Automata. Springer International Publishing, pp 356\u2013367","DOI":"10.1007\/978-3-031-14926-9_32"},{"key":"9975_CR5","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-642-13122-6_12","volume-title":"Fun with Algorithms","author":"YF Chien","year":"2010","unstructured":"Chien YF, Hon WK (2010) Cryptographic and physical zero-knowledge proof: from sudoku to nonogram. In: Boldi P, Gargano L (eds) Fun with Algorithms. Springer, Berlin Heidelberg, Berlin, Heidelberg, pp 102\u2013112"},{"key":"9975_CR6","unstructured":"Chong\u00a0Leung JY, Lui WS, Lee TM (2014) The application of graph theory to sudoku. Honorable Mention, Hang Lung Mathematics Awards, Vol. 6"},{"key":"9975_CR7","doi-asserted-by":"crossref","unstructured":"Chopard B, Droz M (1998) Cellular automata modeling of physical systems. Collection Alea-Saclay: Monographs and Texts in Statistical Physics. Cambridge University Press","DOI":"10.1017\/CBO9780511549755"},{"key":"9975_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93073-2","volume-title":"An introduction to metaheuristics for optimization","author":"B Chopard","year":"2018","unstructured":"Chopard B, Tomassini M (2018) An introduction to metaheuristics for optimization. Springer, New york"},{"issue":"6","key":"9975_CR9","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1038\/scientificamerican0606-80","volume":"294","author":"JP Delahaye","year":"2006","unstructured":"Delahaye JP (2006) The science behind Sudoku. Sci Am 294(6):80\u201387","journal-title":"Sci Am"},{"key":"9975_CR10","doi-asserted-by":"publisher","first-page":"98,306","DOI":"10.1109\/ACCESS.2019.2927815","volume":"7","author":"NI Dourvas","year":"2019","unstructured":"Dourvas NI, Sirakoulis GC, Adamatzky AI (2019) Parallel accelerated virtual physarum lab based on cellular automata agents. IEEE Access 7:98,306-98,318","journal-title":"IEEE Access"},{"issue":"1","key":"9975_CR11","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1038\/srep00725","volume":"2","author":"M Ercsey-Ravasz","year":"2012","unstructured":"Ercsey-Ravasz M, Toroczkai Z (2012) The chaos within sudoku. Sci Rep 2(1):725","journal-title":"Sci Rep"},{"issue":"1","key":"9975_CR12","first-page":"14","volume":"41","author":"JW Grabbe","year":"2017","unstructured":"Grabbe JW (2017) Sudoku and changes in working memory performance for older adults and younger adults. Activi Adaptat Aging 41(1):14\u201321","journal-title":"Activi Adaptat Aging"},{"key":"9975_CR13","doi-asserted-by":"crossref","unstructured":"Hufkens LV, Browne C (2019) A functional taxonomy of logic puzzles. In: 2019 IEEE Conference on Games (CoG), IEEE, pp 1\u20134","DOI":"10.1109\/CIG.2019.8848107"},{"key":"9975_CR14","doi-asserted-by":"crossref","unstructured":"Ioannidis K, Sirakoulis GC, Andreadis I (2008) A cellular automaton collision-free path planner suitable for cooperative robots. In: 2008 Panhellenic conference on informatics, pp 256\u2013260","DOI":"10.1109\/PCI.2008.43"},{"issue":"3","key":"9975_CR15","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s11334-021-00397-4","volume":"17","author":"S Jana","year":"2021","unstructured":"Jana S, Dey A, Maji AK et al (2021) A novel hybrid genetic algorithm-based firefly mating algorithm for solving sudoku. Innovations Syst Softw Eng 17(3):261\u2013275","journal-title":"Innovations Syst Softw Eng"},{"key":"9975_CR16","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/j.neucom.2015.04.125","volume":"188","author":"W Jiang","year":"2016","unstructured":"Jiang W, Li B, Li S et al (2016) A new prospective for learning automata: a machine learning approach. Neurocomputing 188:319\u2013325","journal-title":"Neurocomputing"},{"issue":"110","key":"9975_CR17","first-page":"700","volume":"145","author":"RE Karamani","year":"2021","unstructured":"Karamani RE, Fyrigos IA, Tsakalos KA et al (2021) Memristive learning cellular automata for edge detection. Chaos Solitons Fractals 145(110):700","journal-title":"Chaos Solitons Fractals"},{"issue":"4","key":"9975_CR18","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10732-007-9012-8","volume":"13","author":"R Lewis","year":"2007","unstructured":"Lewis R (2007) Metaheuristics can solve sudoku puzzles. J Heurist 13(4):387\u2013401","journal-title":"J Heurist"},{"issue":"1","key":"9975_CR19","first-page":"6","volume":"11","author":"I Lynce","year":"2006","unstructured":"Lynce I, Ouaknine J (2006) Sudoku as a sat problem. ISAIM 11(1):6\u201313","journal-title":"ISAIM"},{"issue":"1","key":"9975_CR20","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/1767\/1\/012050","volume":"1767","author":"C Manikandan","year":"2021","unstructured":"Manikandan C, Satwik KSS, Smarani TM et al (2021) A combined sudoku and synthetic colour image techniques for cryptographic key generation. J Phys Conf Ser 1767(1):012,050","journal-title":"J Phys Conf Ser"},{"key":"9975_CR21","doi-asserted-by":"crossref","unstructured":"Mantere T, Koljonen J (2007) Solving, rating and generating sudoku puzzles with GA. In: 2007 IEEE congress on evolutionary computation, pp 1382\u20131389","DOI":"10.1109\/CEC.2007.4424632"},{"key":"9975_CR22","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.jocs.2018.09.003","volume":"32","author":"M Mitsopoulou","year":"2019","unstructured":"Mitsopoulou M, Dourvas NI, Sirakoulis GC et al (2019) Spatial games and memory effects on crowd evacuation behavior with cellular automata. J. Comput. Sci. 32:87\u201398","journal-title":"J. Comput. Sci."},{"key":"9975_CR23","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/j.jocs.2015.08.002","volume":"11","author":"M Mozafari","year":"2015","unstructured":"Mozafari M, Shiri ME, Beigy H (2015) A cooperative learning method based on cellular learning automata and its application in optimization problems. J. Comput. Sci. 11:279\u2013288","journal-title":"J. Comput. Sci."},{"issue":"4","key":"9975_CR24","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1109\/TSMC.1974.5408453","volume":"4","author":"KS Narendra","year":"1974","unstructured":"Narendra KS, Thathachar MAL (1974) Learning automata\u2014a survey. IEEE Trans Syst Man Cybern SMC 4(4):323\u2013334","journal-title":"IEEE Trans Syst Man Cybern SMC"},{"key":"9975_CR25","volume-title":"Theory of Self-Reproducing Automata","author":"JV Neumann","year":"1966","unstructured":"Neumann JV (1966) Theory of Self-Reproducing Automata. University of Illinois Press, illinois"},{"key":"9975_CR26","doi-asserted-by":"crossref","unstructured":"Pacurib JA, Seno GMM, Yusiong JPT (2009) Solving sudoku puzzles using improved artificial bee colony algorithm. In: ICICIC 2009, IEEE, pp 885\u2013888","DOI":"10.1109\/ICICIC.2009.334"},{"issue":"2","key":"9975_CR27","first-page":"54","volume":"39","author":"E Russell","year":"2006","unstructured":"Russell E, Jarvis F (2006) Mathematics of Sudoku II. Math Spectr 39(2):54\u201358","journal-title":"Math Spectr"},{"key":"9975_CR28","unstructured":"Simonis H (2005) Sudoku as a constraint problem. In: CP Workshop on modeling and reformulating constraint satisfaction problems, Citeseer, pp 13\u201327"},{"key":"9975_CR29","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1007\/978-3-319-21380-4_102","volume-title":"HCI International 2015\u2014Posters\u2019 Extended Abstracts","author":"R Soto","year":"2015","unstructured":"Soto R, Crawford B, Galleguillos C et al (2015) A filtering technique for helping to solve sudoku problems. In: Stephanidis C (ed) HCI International 2015\u2014Posters\u2019 Extended Abstracts. Springer International Publishing, Cham, pp 598\u2013603"},{"issue":"8","key":"9975_CR30","doi-asserted-by":"publisher","first-page":"9237","DOI":"10.1016\/j.eswa.2011.01.098","volume":"38","author":"JA Torkestani","year":"2011","unstructured":"Torkestani JA, Meybodi MR (2011) A cellular learning automata-based algorithm for solving the vertex coloring problem. Expert Syst Appl 38(8):9237\u20139247","journal-title":"Expert Syst Appl"},{"key":"9975_CR31","doi-asserted-by":"crossref","unstructured":"Tsompanas MAI, Dourvas NI, Ioannidis K, et\u00a0al (2018) Cellular Automata Applications in Shortest Path Problem, vol\u00a032, Springer International Publishing, p 199","DOI":"10.1007\/978-3-319-77510-4_8"},{"key":"9975_CR32","doi-asserted-by":"crossref","unstructured":"Vamsi KS, Gangadharabhotla S, Sai VSH (2021) A deep learning approach to solve sudoku puzzle. In: 2021 ICICCS, IEEE, pp 1175\u20131179","DOI":"10.1109\/ICICCS51141.2021.9432326"},{"key":"9975_CR33","doi-asserted-by":"crossref","unstructured":"Van Der\u00a0Bok K, Taouil M, Afratis P, et\u00a0al (2009) The TU Delft sudoku solver on FPGA. In: 2009 international conference on field-programmable technology, IEEE, pp 526\u2013529","DOI":"10.1109\/FPT.2009.5377605"},{"key":"9975_CR34","unstructured":"Weaver C (2020) Strategies and algorithms of sudoku. Mathematics Senior Capstone Papers 22"},{"key":"9975_CR35","doi-asserted-by":"publisher","DOI":"10.1201\/9780429494093","volume-title":"Cellular automata and complexity: collected papers","author":"S Wolfram","year":"2018","unstructured":"Wolfram S (2018) Cellular automata and complexity: collected papers. crc Press, Boca Raton"},{"issue":"5","key":"9975_CR36","first-page":"1052","volume":"86","author":"T Yato","year":"2003","unstructured":"Yato T, Seta T (2003) Complexity and completeness of finding another solution and its application to puzzles. IEICE Trans Fundam Electron Commun Comput Sci 86(5):1052\u20131060","journal-title":"IEICE Trans Fundam Electron Commun Comput Sci"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-024-09975-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-024-09975-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-024-09975-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T07:19:04Z","timestamp":1711523944000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-024-09975-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["9975"],"URL":"https:\/\/doi.org\/10.1007\/s11047-024-09975-4","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3]]},"assertion":[{"value":"1 August 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}