Harmony Search Algorithm with Two Problem-Specific Operators for Solving Nonogram Puzzle

Geonhee Lee and Zong Woo Geem ()
Additional contact information
Geonhee Lee: College of IT Convergence, Gachon University, Seongnam 13120, Republic of Korea
Zong Woo Geem: College of IT Convergence, Gachon University, Seongnam 13120, Republic of Korea

Mathematics, 2025, vol. 13, issue 9, 1-17

Abstract: The nonogram is a logic puzzle where each cell should be colored or left blank according to row and column clues to reveal a hidden picture. This puzzle is known as an NP-complete combinatorial problem characterized by an exponential increase in the number of candidate solutions with increasing puzzle size. So far, some methods have been investigated to address these challenges, including conventional line-solving techniques, integer programming, and neural networks. This study introduces a novel Harmony Search (HS)-based approach for solving nonogram puzzles, incorporating problem-specific operators designed to effectively reduce the solution search space and accelerate convergence. Experimental results obtained from benchmark puzzles demonstrate that the proposed HS model utilizing a clue-constrained random-generation operator significantly reduces the average number of iterations and enhances the solution-finding success rate. Additionally, the HS model integrating an initially confirmed cell-scanning operator exhibited promising performance on specific benchmark problems. The authors think that the nonogram puzzle can be a good benchmark problem for quantum computing-based optimization in the future, and the proposed HS algorithm can also be combined with quantum computing mechanisms.

Keywords: nonogram puzzle; optimization; harmony search (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/9/1470/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/9/1470/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:9:p:1470-:d:1646109

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().