Nonograms (also known as Picross, Griddlers, Pic-a-Pix, and various other names) are picture logic puzzles, in which the cells in the grid must be colored or left blank according to the numbers on the side of the grid to display hidden pictures.
Figure 1. The initial and complete state of a 25×25 grid Nonogram.
(Source: https://www.nonograms.org/nonograms/i/32344 )
For a classical type of game, the 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. For example, a clue of “1 2 3” would mean there are sets of one, two, and three filled squares, in that order, with at least one blank square between successive sets.
Solving Nonograms can be very time-consuming, and can be tremendously brain-twisting as the grid size increases, thus I created an AI program for automatically solving these puzzles.
The program utilizes the depth-first search algorithm that runs recursively from the top to bottom row. For the jth column of the ith row, the black or blank spaces must satisfy the tomographic rules formed by the numbers of the current row and column. This is a relatively simple approach for calculating the answer. However, because the algorithm does not solve the game using a more intuitive method for solving interrelated constraints, it will use a lot of time for big grids (over 40×40).
For the input format of this program, two numbers indicating the number of rows and columns are given first (n and m). Afterwards, there are n rows of data, with each row k starting with a number nk indicating how many numbers are given in that row, and followed by nk numbers representing the discrete tomography of black spaces of that very row; then there are m rows of data, and also starting with a number mk for the kth row, and followed by mk numbers representing the discrete tomography of black spaces for the kth column.
Here’s an example input for the Nonogram in Fig. 1:
25 25
1 8
2 7 3
1 16
2 11 4
2 13 2
2 14 2
1 18
2 8 4
2 6 4
2 5 5
3 4 2 2
3 4 3 1
3 3 2 1
2 3 2
2 3 2
3 2 1 4
3 2 1 4
3 2 1 4
3 3 1 4
2 5 4
1 11
1 10
1 5
1 5
1 6
1 1
1 2
1 2
1 4
1 11
1 13
1 15
2 9 3
2 8 3
3 7 5 2
3 7 3 4
3 6 2 3
3 8 3 2
2 13 2
2 10 2
3 5 5 3
4 4 1 4 6
4 1 2 2 8
3 3 1 10
4 3 1 4 4
4 2 1 2 3
3 2 1 2
2 2 1
2 2 1
1 1
A demonstration for using the AI program for solving a 39×50 Nonogram in about 22 seconds is shown below. The result displays an owl sitting on a branch (Fig. 2).
Figure 2. The complete state of a 39×50 Nonogram displaying an owl on a branch.