Japanese crossword puzzles (also known as nonograms) are logic puzzles that contain an encrypted pixel image. The puzzle must be solved using the numbers located to the left of the rows and above the columns.
Crossword puzzles can be up to 150×150 in size. The player uses special logical techniques to calculate the color of each cell. Solving a puzzle can take a couple of minutes for beginner crossword puzzles or dozens of hours for complex puzzles.
A good algorithm can solve the problem much faster. The text describes how to write a solution that works almost instantly using the most suitable algorithms (which generally lead to a solution), as well as their optimizations and the use of C++ features (which reduce the processing time by several dozen times).
Rules of the game
Initially, the crossword canvas is white. For vanilla black-and-white crosswords, you need to restore the locations of the black cells.
In black-and-white crossword puzzles, the number of digits for each row (to the left of the canvas) or for each column (above the canvas) indicates how many groups of black cells are in the corresponding row or column, and the digits themselves indicate how many contiguous cells each of these groups contains. The set of numbers $[3, 2, 5]$ means that in a given row there are three consecutive groups of $3$, $2$, and $5$ black cells in a row. The groups can be arranged in any order in the row without breaking the relative order (the numbers specify their length, and the position must be guessed), but they must be separated by at least one white cell.
Correct example
In colored crosswords, each group also has its own color — any color except white, which is the background color. Neighboring groups of different colors can be close together, but for neighboring groups of the same color, separation by at least one white cell is still required.
What is not a Japanese crossword
Any pixel image can be encrypted as a crossword puzzle. However, it may be impossible to restore it — the resulting puzzle may either have more than one solution or have one solution that cannot be solved logically. In this case, the remaining cells in the game must be guessed using quantum computers or shamanic technologies.
Such crossword puzzles are not crossword puzzles, but graphomania. It is believed that a correct crossword puzzle is one in which a single solution can be reached by logical means.
The “logical path” is the ability to restore each cell one by one, considering each row/column separately, or their intersection. If this is not possible, the number of possible answers can be very large, much larger than a person can count themselves.
An incorrect nonogram has a single solution, but it cannot be solved normally. The “unsolvable” cells are marked in orange. Taken from Wikipedia.
This limitation can be explained as follows: in the most general case, a Japanese crossword puzzle is an NP-complete problem. However, solving a crossword puzzle does not become an NP-complete problem if there is an algorithm that clearly indicates which cells to open next at any given moment. All methods of solving crossword puzzles used by humans (with the exception of the Monte Carlo trial and error method) are based on this.
In the most orthodox crossword puzzles, the width and height are divided by 5, there are no rows that can be counted instantly (those where either colored cells fill all the spaces or there are none at all), and the number of additional colors is limited. These requirements are not mandatory.
Often, backward-encoded pixel art, which uses a “checkerboard pattern” to imitate a gradient, cannot be solved. It will be easier to understand if you type “pixelart gradient” into a search engine. The gradient is similar to this failed 2×2 crossword puzzle.
Possible solutions
We have the size of the crossword, a description of the colors, and all the rows and columns. How can we assemble a picture from this?
Full search
For each cell, we go through all possible states and check them for satisfaction. The complexity of such a solution for a black-and-white crossword puzzle is $O(NM{2}^{NM})$, and for a color crossword puzzle, it is $O(NM{colors}^{NM})$. By analogy with clown sorting, this solution can also be called clownish. It is suitable for a 5×5 size.
Backtracking
All possible methods of arranging horizontal groups of cells are considered. We place a group of cells in a row and check that it does not break the description of the column groups. If it breaks it, we place it one cell further and check again. Once placed, we move on to the next group. If the group cannot be placed in any way, we roll back two groups, rearrange the previous group, and so on until we successfully place the last group.
Separately for each row
This solution is much better and it is truly correct. We can analyze each row and each column separately. For each row, we will try to reveal as much information as possible.
The algorithm for each cell in the row will reveal more information — it may turn out that it is impossible to color a cell in a certain color, the groups will not match. It is not possible to reveal the entire row at once, but the information obtained will “help” to reveal several columns better, and when we start analyzing them, they will again “help” the rows, and so on for several iterations, until there is only one possible color left for all cells.