Difference between revisions of "Nonogram"

From Chessprogramming wiki
Jump to: navigation, search
 
(3 intermediate revisions by the same user not shown)
Line 64: Line 64:
  
 
=Selected Publications=  
 
=Selected Publications=  
 +
==1996 ...==
 
* [[Nobuhisa Ueda]], [[Tadaaki Nagao]] ('''1996'''). ''NP-completeness results for NONOGRAM via Parsimonious Reductions''
 
* [[Nobuhisa Ueda]], [[Tadaaki Nagao]] ('''1996'''). ''NP-completeness results for NONOGRAM via Parsimonious Reductions''
 +
==2000 ...==
 
* [[Joost Batenburg]], [[Walter Kosters]] ('''2009'''). ''Solving Nonograms by combining relaxations''. [http://www.journals.elsevier.com/pattern-recognition/ Pattern Recognition], Vol. 42, No. 8
 
* [[Joost Batenburg]], [[Walter Kosters]] ('''2009'''). ''Solving Nonograms by combining relaxations''. [http://www.journals.elsevier.com/pattern-recognition/ 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#34_1|ICGA Journal, Vol. 34, No. 1]] » [[15th Computer Olympiad#Nonogram|15th Computer Olympiad]]
 
* [[Shi-Jim Yen]], [[Shi-Yuan Chiu]], [[Cheng-Wei Chou]], [[Jr-Chang Chen]] ('''2011'''). ''Cpuzzler wins Nonogram Tournament''. [[ICGA Journal#34_1|ICGA Journal, Vol. 34, No. 1]] » [[15th Computer Olympiad#Nonogram|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#35_2|ICGA Journal, Vol. 35, No. 2]] » [[TAAI 2011]]
 
* [[Der-Johng Sun]], [[Kuang-che Wu]], [[I-Chen Wu]], [[Shi-Jim Yen]], [[Kuo-Yuan Kao]] ('''2012'''). ''Nonogram Tournaments in TAAI 2011''. [[ICGA Journal#35_2|ICGA Journal, Vol. 35, No. 2]] » [[TAAI 2011]]
Line 73: Line 76:
 
* [[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#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 5, No. 3
 
* [[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#TOCIAIGAMES|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#37_1|ICGA Journal, Vol 37, No. 1]] » [[17th Computer Olympiad#Nonogram|17th Computer Olympiad]]
 
* [[Lung-Pin Chen]], [[Der-Johng Sun]], [[Wen-Jie Tseng]] ('''2014'''). ''Nonogram Tournament in Olympiad Yokohama 2013''. [[ICGA Journal#37_1|ICGA Journal, Vol 37, No. 1]] » [[17th Computer Olympiad#Nonogram|17th Computer Olympiad]]
 +
* [[Lung-Pin Chen]], [[Kuo-Chan Huang]] ('''2018'''). ''Solving Nonogram puzzles by using grouped based fully probing''. [[CG 2018]], [[ICGA Journal#40_4|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#40_4|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#41_1|ICGA Journal, Vol. 41, No. 1]] » [[Bitboards]]
 +
==2020 ...==
 +
* [[Yen-Chi Chen]], [[Shun-Shii Lin]] ('''2020'''). ''Requiem wins Nonogram tournament''. [[ICGA Journal#42_1|ICGA Journal, Vol. 42, No. 1]] » [[22nd Computer Olympiad]]
  
 
=External Links=  
 
=External Links=  

Revision as of 14:35, 29 June 2020

Home * Games * Nonogram

A Nonogram puzzle [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 [2] .

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
random puzzles (secs)
2011/11 TAAI 2011 LalaFrogKK 645.544
2012/06 TCGA 2012 LalaFrogKK 1433
2013/08 17th Computer Olympiad 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 ...

2000 ...

2010 ...

2020 ...

External Links

References

  1. Lung-Pin Chen, Der-Johng Sun, Wen-Jie Tseng (2014). Nonogram Tournament in Olympiad Yokohama 2013. ICGA Journal, Vol 37, No. 1
  2. Nonogram from Wikipedia

Up one Level