Which cells should become black?
- The amount of numbers in a row/column tells how many black blocks should be put in that row/column.
- Number itself indicates block length.
- Numbers are given in block sequence.
- Between blocks at least one cell must remain empty.
By the way, nonograms are also known as Japanese puzzles, Griddlers, 'Paint by Numbers', Hanjie, Picross, Pic-a-Pix and other names.
Each line in below text area contains block lengths separated by a space. Top lines are rows input. Bottom lines - below signal word COLUMNS - are columns input. Content is Example 1.
- The solver runs three processes:
- A process of deterministic line solving based on recursive enumeration, generating all valid combinations of block positions, taking into account cells that are already known to be BLACK/WHITE. The line solver can be described as a constraint-propagation engine combined with backtracking. If a cell is BLACK/WHITE in all combinations, it is set to BLACK/WHITE in the (partial) solution. All other cells remain UNKNOWN. Line solving is performed for all rows, then all columns, repeatedly, as long as the (partial) solution changes. If none of the cells are still UNKNOWN, the puzzle is solved. Otherwise, the next process—probabilistic guessing with backtracking—is started.
- A process of probabilistic guessing with backtracking (search-tree branching). The selection of the guess cell is based on detailed probability outcomes from the deterministic process, producing the BLACK probability for each cell in every row and column. The best guess cell is not the cell with the highest chance of becoming BLACK or the highest chance of becoming WHITE, but the cell which is most likely to keep the search tree limited. Roughly speaking, this means that the more a chance deviates from 50%, the more it is penalized. After a guess cell is set to BLACK, the deterministic process is started again. If it leads to a contradiction, the guess cell is changed from BLACK to WHITE. If this also leads to a contradiction (which is impossible at root level 0), backtracking is applied. All changes made after the previous guess are undone, and the previous guess cell is changed from BLACK to WHITE. The deterministic process is then started again.
- An optional probing subprocess detects “promising” guess cells in an attempt to avoid deep recursion. The probing process selects a cell, sets it to BLACK, runs the deterministic process, and checks whether a contradiction occurs. If one occurs, the probe cell must be WHITE at that branch of the search tree. If no contradiction occurs, the process records how many cells were solved. The probe cell that results in the highest number of solved cells becomes the guess cell used by the probabilistic guessing process. Probing is time-consuming, but it can save time by avoiding the need to search a large tree whose size grows exponentially with depth.
- This solver may not solve nasty nonograms in reasonable time (nasty meaning a nonogram larger than 50 × 50 and/or with a huge amount of small blocks, combined with a need for probabilistic guessing). It is a demo tool.