A Nonogram puzzle 1
- Lung-Pin Chen, Der-Johng Sun, Wen-Jie Tseng (2014). Nonogram Tournament in Olympiad Yokohama 2013. ICGA Journal, Vol 37, No. 1↩︎
Nonogram,
a logic puzzle in which cells in a grid must be painted according to the given row clues and column clues. Players are requested to paint each grid cell into either “white” or “black”, such that the segments constituting of consecutive black cells in each row or column matches the corresponding row clue and column clue. The clues or numbers are a form of discrete tomography that measures how many unbroken lines of filled-in squares there are in any given row or column. Solving nonogram puzzles is a NP-complete problem 1 .
Contents
Competitions
Computer Olympiad, TAAI, and TCGA hold Nonogram competitions since 2010.
| Date | Event | Champion |
|---|---|---|
| 2010 | 15th Computer Olympiad | Cpuzzler |
| 2011/06 | TCGA 2011 | Naughty |
Since 2011, the competition format changed from tournament to solver speed competition.
Date |
Event |
Champion |
Time to solve 1000 |
|---|---|---|---|
2011/11 |
TAAI 2011 |
LalaFrogKK |
645.544 |
2012/06 |
TCGA 2012 |
LalaFrogKK |
1433 |
2013/08 |
LalaFrogKK |
22.56 (?) |
|
2014/06 |
TCGA 2014 |
LalaFrogKK |
n/a |
2014/11 |
TAAI 2014 |
LalaFrogKK |
664 |
2015/05 |
TCGA 2015 |
LalaFrogKK |
908 |
Selected Publications
1996 ...
- Nobuhisa Ueda, Tadaaki Nagao (1996). NP-completeness results for NONOGRAM via Parsimonious Reductions
2000 ...
- Joost Batenburg, Walter Kosters (2009). Solving Nonograms by combining relaxations. Pattern Recognition, Vol. 42, No. 8
2010 ...
- Shi-Jim Yen, Shi-Yuan Chiu, Cheng-Wei Chou, Jr-Chang Chen (2011). Cpuzzler wins Nonogram Tournament. ICGA Journal, Vol. 34, No. 1 » 15th Computer Olympiad
- Der-Johng Sun, Kuang-che Wu, I-Chen Wu, Shi-Jim Yen, Kuo-Yuan Kao (2012). Nonogram Tournaments in TAAI 2011. ICGA Journal, Vol. 35, No. 2 » TAAI 2011
- Jan van Rijn (2012). Playing Games: The complexity of Klondike, Mahjong, Nonograms and Animal Chess. Master's thesis, Leiden Institute of Advanced Computer Science, pdf
- Joost Batenburg, Walter Kosters (2012). Nonograms. LIACS - Leiden Institute of Advanced Computer Science, pdf
- Joost Batenburg, Walter Kosters (2012). On the Difficulty of Nonograms. ICGA Journal, Vol. 35, No. 4
- I-Chen Wu, Der-Johng Sun, Lung-Ping Chen, Kan-Yueh Chen, Ching-Hua Kuo, Hao-Hua Kang, Hung-Hsuan Lin (2013). An Efficient Approach to Solving Nonograms. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 5, No. 3
- Lung-Pin Chen, Der-Johng Sun, Wen-Jie Tseng (2014). Nonogram Tournament in Olympiad Yokohama 2013. ICGA Journal, Vol 37, No. 1 » 17th Computer Olympiad
- Lung-Pin Chen, Kuo-Chan Huang (2018). Solving Nonogram puzzles by using grouped based fully probing. CG 2018, ICGA Journal, Vol. 40, No. 4
- Yan-Rong Guo, Kuo-Chan Huang, Jia-Jun Yeh, Wei-Chiao Huang (2018). Exploring effects of fully probing sequence on solving nonogram puzzles. CG 2018, ICGA Journal, Vol. 40, No. 4
- Yen-Chi Chen, Shun-Shii Lin (2019). A fast nonogram solver that won the TAAI 2017 and ICGA 2018 tournaments. ICGA Journal, Vol. 41, No. 1 » Bitboards
- Aline Hufschmitt, Jean-Noël Vittaut, Nicolas Jouandeau (2019). Exploiting Game Decompositions in Monte Carlo Tree Search. Advances in Computer Games 16
- Yan-Rong Guo, Wei-Chiao Huang, Jia-Jun Yeh, Hsi-Ya Chang, Lung-Pin Chen, Kuo-Chan Huang (2019). On Efficiency of Fully Probing Mechanisms in Nonogram Solving Algorithm. Advances in Computer Games 16
2020 ...
- Yen-Chi Chen, Shun-Shii Lin (2020). Requiem wins Nonogram tournament. ICGA Journal, Vol. 42, No. 1 » 22nd Computer Olympiad
External Links
- Nonogram from Wikipedia
- Survey of Paint-by-Number Puzzle Solvers
- Nonogram — Turn your picture into a puzzle by Walter Kosters