Nonogram


Nonograms, also known as Picross, Griddlers, Pic-a-Pix, and various other names, are picture logic puzzles in which cells in a grid must be colored or left blank according to numbers at the side of the grid to reveal a hidden picture. In this puzzle type, 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 "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive sets.
These puzzles are often black and white—describing a binary image—but they can also be colored. If colored, the number clues are also colored to indicate the color of the squares. Two differently colored numbers may or may not have a space in between them. For example, a black four followed by a red two could mean four black boxes, some empty spaces, and two red boxes, or it could simply mean four black boxes followed immediately by two red ones. Nonograms have no theoretical limits on size, and are not restricted to square layouts.
Nonograms were named after Non Ishida, one of the two inventors of the puzzle.

Names

Nonograms are also known by many other names, including Paint by Numbers, Griddlers, Pic-a-Pix, Picross, Picma, PrismaPixels, Pixel Puzzles, Crucipixel, Edel, FigurePic, Hanjie, HeroGlyphix, Illust-Logic, Japanese Crosswords, Japanese Puzzles, Kare Karala!, Logic Art, Logic Square, Logicolor, Logik-Puzzles, Logimage, Oekaki Logic, Oekaki-Mate, Paint Logic, Picture Logic, Tsunamii, Paint by Sudoku and Binary Coloring Books.

History

In 1987, Non Ishida, a Japanese graphics editor, won a competition in Tokyo by designing grid pictures using skyscraper lights that were turned on or off. This led her to the idea of a puzzle based around filling in certain squares in a grid. Coincidentally, a professional Japanese puzzler named Tetsuya Nishio invented the same puzzles completely independently, and published them in another magazine.

Print publishing

Paint by numbers puzzles started appearing in Japanese puzzle magazines. Non Ishida published three picture grid puzzles in 1988 in Japan under the name of "Window Art Puzzles". In 1990, James Dalgety in the UK invented the name Nonograms after Non Ishida, and The Sunday Telegraph started publishing them on a weekly basis. By 1993, the first book of nonograms was published by Non Ishida in Japan. The Sunday Telegraph published a dedicated puzzle book titled the "Book of Nonograms". Nonograms were also published in Sweden, United States, South Africa and other countries. The Sunday Telegraph ran a competition in 1998 to choose a new name for their puzzles. Griddlers was the winning name that readers chose.

Electronic puzzles

Paint by numbers puzzles were implemented by 1995 on hand held electronic toys such as Game Boy and on other plastic puzzle toys. Nintendo picked up on this puzzle fad and released two "Picross" titles for the Game Boy and nine for the Super Famicom in Japan. Only one of these, Mario's Picross for the Game Boy, was released outside Japan. Since then, one of the most prolific Picross game developers has been Jupiter Corporation, who released Picross DS on the Nintendo DS in 2007, 8 titles in the Picross e series for the Nintendo 3DS eShop, and 4 titles in the Picross S series for the Nintendo Switch.
Increased popularity in Japan launched new publishers and by now there were several monthly magazines, some of which contained up to 100 puzzles. The Japanese arcade game Logic Pro was released by Deniam Corp in 1996, with a sequel released the following year. UK games developer Jagex released a nonogram puzzle in 2011 as part of their annual Halloween event for their role-playing game, Runescape. In 2013, Casual Labs released a mobile version of these puzzles called Paint it Back with the theme of restoring an art gallery. Released early in 2017, Pictopix has been presented as a worthy heir to Picross on PC by Rock, Paper, Shotgun. In particular, the game enables players to share their creations.

Today

Paint by numbers have been published by Sanoma Uitgevers in the Netherlands, Puzzler Media in the UK and Nikui Rosh Puzzles in Israel. Magazines with nonogram puzzles are published in the US, UK, Germany, Netherlands, Italy, Hungary, Finland, Ukraine, and many other countries.

Example

Solution techniques

To solve a puzzle, one needs to determine which cells will be boxes and which will be empty. Solvers often use a dot or a cross to mark cells they are certain are spaces. Cells that can be determined by logic should be filled. If guessing is used, a single error can spread over the entire field and completely ruin the solution. An error sometimes comes to the surface only after a while, when it is very difficult to correct the puzzle. The hidden picture plays little or no part in the solving process, as it may mislead. The picture may help find and eliminate an error.
Simpler puzzles can usually be solved by a reasoning on a single row only at each given time, to determine as many boxes and spaces on that row as possible. Then trying another row, until there are no rows that contain undetermined cells. More difficult puzzles may also require several types of "what if?" reasoning that include more than one row. This works on searching for contradictions: When a cell cannot be a box, because some other cell would produce an error, it will definitely be a space. And vice versa. Advanced solvers are sometimes able to search even deeper than into the first "what if?" reasoning.
It is sometimes impossible to avoid guessing. For example, at the end of a puzzle if two rows and two columns each contain one unaccounted-for box there is no information to determine whether the boxes reside in the upper-left and lower-right cells or in the upper-right and lower-left cells.

Simple boxes

At the beginning of the solution, a simple method can be used to determine as many boxes as possible. This method uses conjunctions of possible places for each block of boxes. For example, in a row of ten cells with only one clue of 8, the bound block consisting of 8 boxes could spread from
As a result, the block must spread through the six centermost cells in the row.
The same applies when there are more clues in the row. For example, in a row of ten cells with clues of 4 and 3, the bound blocks of boxes could be
Consequently, the first block of four boxes definitely includes the third and fourth cells, while the second block of three boxes definitely includes the eighth cell. Boxes can therefore be placed in the third, fourth and eighth cells. Important note: When determining boxes in this way, boxes can be placed in cells only when the same block overlaps; in this example, there is overlap in the sixth cell, but it is from different blocks, and so it cannot yet be said whether or not the sixth cell will contain a box.

Simple spaces

This method consists of determining spaces by searching for cells that are out of range of any possible blocks of boxes. For example, considering a row of ten cells with boxes in the fourth and ninth cell and with clues of 3 and 1, the block bound to the clue 3 will spread through the fourth cell and clue 1 will be at the ninth cell.
First, the clue 1 is complete and there will be a space at each side of the bound block.
Second, the clue 3 can only spread somewhere between the second cell and the sixth cell, because it always has to include the fourth cell; however, this may leave cells that may not be boxes in any case, i.e. the first and the seventh.
Note: In this example all blocks are accounted for; this is not always the case. The player must be careful for there may be clues or blocks that are not bound to each other yet.

Forcing

In this method, the significance of the spaces will be shown. A space placed somewhere in the middle of an uncompleted row may force a large block to one side or the other. Also, a gap that is too small for any possible block may be filled with spaces.
For example, considering a row of ten cells with spaces in the fifth and seventh cells and with clues of 3 and 2:
Sometimes, there is a box near the border that is not farther from the border than the length of the first clue. In this case, the first clue will spread through that box and will be forced outward from the border.
For example, considering a row of ten cells with a box in the third cell and with a clue of 5, the clue of 5 will spread through the third cell and will continue to the fifth cell because of the border.
Note: This method may also work in the middle of a row, farther away from the borders.
Boxes closer to each other may be sometimes joined together into one block or split by a space into several blocks. When there are two blocks with an empty cell between, this cell will be:
For example, considering a row of fifteen cells with boxes in the third, fourth, sixth, seventh, eleventh and thirteenth cell and with clues of 5, 2 and 2:
Note: The illustration picture also shows how the clues of 2 are further completed. This is, however, not part of the Joining and splitting technique, but the Glue technique described above.

Punctuating

To solve the puzzle, it is usually also very important to enclose each bound or completed block of boxes immediately by separating spaces as described in Simple spaces method. Precise punctuating usually leads to more Forcing and may be vital for finishing the puzzle. Note: The examples above did not do that only to remain simple.

Mercury

Mercury is a special case of Simple spaces technique. Its name comes from the way mercury pulls back from the sides of a container.
If there is a box in a row that is in the same distance from the border as the length of the first clue, the first cell will be a space. This is because the first clue would not fit to the left of the box. It will have to spread through that box, leaving the first cell behind. Furthermore, when the box is actually a block of more boxes to the right, there will be more spaces at the beginning of the row, determined by using this method several times.

Contradictions

Some more difficult puzzles may also require advanced reasoning. When all simple methods above are exhausted, searching for contradictions may help. It is wise to use a pencil for that to facilitate corrections. The procedure includes:
  1. Trying an empty cell to be a box.
  2. Using all available methods to solve as much as possible.
  3. If an error is found, the tried cell will not be a box for sure. It will be a space.
In this example a box is tried in the first row, which leads to a space at the beginning of that row. The space then forces a box in the first column, which glues to a block of three boxes in the fourth row. However, that is wrong because the third column does not allow any boxes there, which leads to a conclusion that the tried cell must not be a box, so it must be a space.
The problem of this method is that there is no quick way to tell which empty cell to try first. Usually only a few cells lead to any progress, and the other cells lead to dead ends. Most worthy cells to start with may be:
It is possible to get a start to a puzzle using a mathematical technique to fill in blocks for rows/columns independent of other rows/columns. This is a good "first step" and is a mathematical shortcut to techniques described above. The process is as follows:
  1. Add the clues together, plus 1 for each "space" in between. For example, if the clue is 6 2 3, you have 6 + 2 + 3 + 1 + 1 = 13. The first one is the space between 6 and 2, the second 1 is the space between 2 and 3.
  2. Subtract this number from the total available in the row. For example, if the clue in step 1 is in a row 15 cells wide, the difference is 2. Note: if spaces can be used on the left or right borders, this "shrinks" the available area. If it is known that the rightmost cell is a space, the difference is 14 - 13 = 1.
  3. Any clues that are greater than the number in step 2 will have some blocks filled in. In the example, this is for the clues 6 and 3.
  4. For each clue in step 3, subtract the number in step 2 to determine the number of blocks that can be filled in. For example, the 6 clue will have 4 blocks filled in and the 3 clue will have 1. Note that the same logic applies for clues that "fail" step 3. The clue 2 is 0 indicating 0 blocks are filled in. If there were a 1 clue, 1 - 2 = -1. Since you can't have negative blocks filled in, this number is just 0.
  5. To fill in the blocks, assume the blocks are all pushed to the side you are counting from and count "through" the blocks and backfill the appropriate number of blocks. This can be done from either direction. For example, the 6 clue can be done either of two ways as follows:
  6. # From the left: Since the 6 is the first number, you simply count 6 blocks from the left edge, putting you in the 6th block. Now you "backfill" 4 blocks, so that cells 3, 4, 5, and 6 are filled.
  7. # From the right: Starting from the right, you have to account for the clues that are to the right of the 6 clue. Starting from cell 15, you count 3 cells for the 3 clue, then a space, then the 2 clue, then a space, then the 6 clue. From the 3rd cell, "backfill" 4 blocks, filling cells 3, 4, 5, and 6. the results are the same as doing it from the left in the step above.
  8. Repeat step 5 for all clues identified in step 3.
Use this technique for all rows and columns at the start of the puzzle and you'll have a good head start into completing it. Note: some rows/columns won't yield any results initially. For example, a row of 20 cells with a clue of 1 4 2 5 will yield 1 + 4 + 2 + 5 + 1 + 1 + 1 = 15. 20 - 15 = 5. None of the clues are greater than 5. Also, this technique can be used on a smaller scale. If there are available spaces in the center or either side, even if certain clues are already discovered, use this method with the remaining clues and available spaces.

Deeper recursion

Some puzzles may require to go deeper with searching for the contradictions. This is, however, not possible simply by a pen and pencil, because of the many possibilities that must be searched. This method is practical for a computer to use.

Multiple rows

In some cases, reasoning over a set of rows may also lead to the next step of the solution even without contradictions and deeper recursion. However, finding such sets is usually as difficult as finding contradictions.

Multiple solutions

There are puzzles that have several feasible solutions. In these puzzles, all solutions are correct by the definition, but not all must give a reasonable picture.

Nonograms in computing

Solving nonogram puzzles is an NP-complete problem. This means that there is no polynomial time algorithm that solves all nonogram puzzles unless P = NP.
However, certain classes of puzzles, such as those in which each row or column has only one block of cells and all cells are connected, may be solved in polynomial time by transforming the problem into an instance of 2-satisfiability.
Many nonograms can be solved efficiently, because the interrelated constraints on the two axes allow the search space to be bounded, dramatically reducing the space that must be searched for a solution.

Software solvers

An extensive comparison and discussion of nonogram solving algorithms is found at the WebPBN site.
Some other online and offline solvers include:
have published several nonogram video games using the name "Picross". The Nintendo Game Boy game Mario's Picross was initially released in Japan on March 14, 1995 as part of the NP Picross series to decent success. However, the game failed to become a hit in the U.S. market, despite a heavy advertising campaign by Nintendo. The game is of an escalating difficulty, with successive puzzle levels containing larger puzzles. Each puzzle has a limited amount of time to be cleared. Hints may be requested at a time penalty, and mistakes made earn time penalties as well. Picross 2 was released later for Game Boy and Mario's Super Picross for the Super Famicom, neither of which were translated for the U.S. market. Both games introduced Wario's Picross as well, featuring Mario's nemesis in the role. These rounds vary by removing the hint function, and mistakes are not penalized—at the price that mistakes are not even revealed. These rounds can only be cleared when all correct boxes are marked, with no mistakes. The time limit was also removed. Nintendo also released eight Picross volumes on the Japanese Nintendo Power peripheral in Japan, each with a new set of puzzles, including puzzles based around various Nintendo characters, such as Mario, The Legend of Zelda, and Pokémon.
Nintendo has released Picross DS for the Nintendo DS portable system in 2007. It contains several stages of varying difficulty, from 5x5 grids to 25x20 grids. Normal mode tells players if they made an error and free mode does not. A hint is available before starting the puzzle in all modes; the game reveals a complete row and column at random. Additional puzzles were available through Nintendo Wi-Fi Connection; some of the original Mario Picross puzzles were available. However, the service was shut down on 20 May 2014. Nintendo made new releases available bi-weekly. Picross DS was released in Europe and Australia on 11 May 2007 and in the United States on July 30, 2007 and has been received well by critics, including Craig Harris, Jessica Wadleigh and Dave McCarthy labelling the game "Addictive". A 3D version of the game, titled Picross 3D, was also released for the DS in Japan in 2009 and internationally in 2010. A sequel, , was released for the Nintendo 3DS in 2015. Another downloadable version of the game was released for Nintendo 3DS's Nintendo eShop, called Picross e, Picross e2, and Picross e3 released in 2013, with Picross e4 released in 2014. Nintendo has also released a Pokémon spinoff on December 7, 2015 in the form of the freemium game of Pokémon Picross for Nintendo 3DS. My Nintendo Picross was released for Nintendo 3DS on March 31, 2016, exclusively as a premium reward for My Nintendo.
Other companies have also released nonogram video games, such as Falcross on iOS, and the Color Cross series of games by Little Worlds Studio on the Nintendo DS, Microsoft Windows, and iOS. In addition, nonogram puzzles have appeared in non-picross puzzle games, such as in Deadly Rooms of Death's fifth installment, The Second Sky. In it, nonogram puzzles representing in-game objects are optional, unlockable puzzles late into the game that can be played in the level "The Central Station", and solving them unlocks bonus levels in the game. In 2018, Konami released a game titled Pixel Puzzle Collection, or Picross Puzzle, featuring classic Konami characters and sprites.

Other picture logic puzzles

Pentomino paint-by-numbers is a variant in which the twelve pentomino shapes must be placed in the grid, without touching each other.
Triddlers are an offshoot that uses triangle shapes instead of squares.
Paint by pairs or Link-a-Pix consists of a grid, with numbers filling some squares; pairs of numbers must be located correctly and connected with a line filling a total of squares equal to that number. There is only one unique way to link all the squares in a properly-constructed puzzle. When completed, the squares that have lines are filled; the contrast with the blank squares reveals the picture.
Fill-a-Pix also uses a grid with numbers within. In this format, each number indicates how many of the squares immediately surrounding it, and itself, will be filled. A square marked "9," for example, will have all eight surrounding squares and itself filled. If it is marked "0" those squares are all blank.
Maze-a-Pix uses a maze in a standard grid. When the single correct route from beginning to end is located, each 'square' of the solution is filled in to create the picture.
Tile Paint is another type of picture logic puzzle by Nikoli. It works like regular nonograms except that it only specifies the total number of squares in each row or column that will be filled in and irregular sections within the grid have borders around them that indicate that, if one of the squares within it is filled in, all of them must be filled in.