Paint by numbers
Encyclopedia
Nonograms, also known as Hanjie, Paint by Numbers, or Griddlers, are picture logic puzzles in which cells in a grid have to be colored or left blank according to numbers given at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers measure 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 groups.

These puzzles are often black and white but can also have some colors. If they are colored, the number clues will also be colored in order 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 spaces, some empty spaces, and two red spaces, or it could simply mean four black spaces followed immediately by two red ones.

There are no theoretical limits on the size of a nonogram, and they are also not restricted to square layouts.

Names

Nonograms are also known by many other names, including Paint by Numbers, Griddlers, Pic-a-Pix, Picross, PrismaPixels, Pixel Puzzles, Crucipixel, Edel, FigurePic, Grafilogika, Hanjie, Illust-Logic, Japanese Crosswords, Japanese Puzzles, Kare Karala!, Logic Art, Logic Square, Logicolor, Logik-Puzzles, Logimage, Obrazki logiczne, Zakódované obrázky, Maľované krížovky, Oekaki Logic, Oekaki-Mate, Paint Logic, Shchor Uftor, Gobelini, Picture Logic and Tsunamii. They have also been called Paint by Sudoku
Sudoku
is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid contains all of the digits from 1 to 9...

 and Binary
Binary code
A binary code is a way of representing text or computer processor instructions by the use of the binary number system's two-binary digits 0 and 1. This is accomplished by assigning a bit string to each particular symbol or instruction...

 Coloring Books, although these names are entirely inaccurate.

History

In 1987, Non Ishida, a Japanese graphics editor, won a competition in Tokyo by designing grid pictures using skyscraper lights which are turned on or off. At the same time and with no connection, a professional Japanese puzzler named Tetsuya Nishio invented the same puzzles.

Paint by numbers puzzles started appearing in Japanese puzzle magazines. Nintendo
Nintendo
is a multinational corporation located in Kyoto, Japan. Founded on September 23, 1889 by Fusajiro Yamauchi, it produced handmade hanafuda cards. By 1963, the company had tried several small niche businesses, such as a cab company and a love hotel....

 picked up on this puzzle fad
FAD
In biochemistry, flavin adenine dinucleotide is a redox cofactor involved in several important reactions in metabolism. FAD can exist in two different redox states, which it converts between by accepting or donating electrons. The molecule consists of a riboflavin moiety bound to the phosphate...

 and in 1995 released two "Picross" (Picture Crossword) titles for the Game Boy
Game Boy
The , is an 8-bit handheld video game device developed and manufactured by Nintendo. It was released in Japan on , in North America in , and in Europe on...

 and nine for the Super Famicom
Super Nintendo Entertainment System
The Super Nintendo Entertainment System is a 16-bit video game console that was released by Nintendo in North America, Europe, Australasia , and South America between 1990 and 1993. In Japan and Southeast Asia, the system is called the , or SFC for short...

 (eight of which were released in two-month intervals for the Nintendo Power Super Famicom Cartridge Writer as the "NP Picross" series) in Japan. Only one of these, Mario's Picross
Mario's Picross
is the first in a series of Mario themed Picross titles released in the 1990s. It is a collection of nonogram logic puzzles involving a grid with numbers for every row and column, which refer to the amount of marked squares within the grid. The game features Mario as an archaeologist who chisels...

for the Game Boy, was released outside of Japan.

In 1988, Non Ishida published three picture grid puzzles 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.

In 1993, 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 (originally by Games magazine), South Africa and other countries.

In 1995, paint by numbers started appearing on hand held electronic toys such as Game Boy and on other plastic puzzle toys. Increased popularity in Japan launched new publishers and by now there were several monthly magazines, some of which contained up to 100 puzzles.

In 1996, the Japanese arcade game Logic Pro was released by Deniam Corp, with a sequel released the following year.

In 1998, The Sunday Telegraph ran a competition to choose a new name for their puzzles. Griddlers was the winning name that readers chose.

In 1999, Paint by numbers were published by Sanoma Uitgevers in Holland, Puzzler Media (formerly British European Associated Publishers) in the UK and Nikui Rosh Puzzles in Israel.

In 2007, Nintendo released another version of Picross
Picross DS
is a puzzle video game developed by Jupiter and published by Nintendo for the Nintendo DS handheld video game console. It is the second Picross game to be released by Nintendo in Europe and North America after Mario's Picross suffered a commercial failure in regions outside Japan, where many...

, this time for their Nintendo DS
Nintendo DS
The is a portable game console produced by Nintendo, first released on November 21, 2004. A distinctive feature of the system is the presence of two separate LCD screens, the lower of which is a touchscreen, encompassed within a clamshell design, similar to the Game Boy Advance SP...

 console.

In 2011, UK games developer Jagex released a nonogram puzzle as part of their annual Halloween event for their java based game, Runescape.

Today, magazines with nonogram puzzles are published in the USA, UK, Germany, Netherlands, Italy, Hungary, Finland, Ukraine, and many other countries.

Solution techniques

In order to solve a puzzle, one needs to determine which cells are going to be boxes and which are going to be empty. Determining which cells are to be empty (called spaces) is as important as determining which are to be filled (called boxes). Later in the solving process, the spaces help to determine where a clue (continuing block of boxes and a number in the legend) may spread. Solvers usually use a dot or a cross to mark cells which they are certain are spaces.

It is also important never to guess. Only cells that can be determined by logic should be filled. If guessing, a single error can spread over the entire field and completely ruin the solution. It usually comes to the surface only after a while, when it is very difficult to correct the puzzle. Usually, only advanced and experienced solvers are able to fix it completely and finish such ruined puzzles.

The hidden picture plays no part in the solving process. Even if it is obvious from the picture that a cell will be a box, it is usually treacherous to rely on it. The picture, however, may help find and eliminate an error.

Simpler puzzles can usually be solved by a reasoning on a single row only (or a single column) at each given time, to determine as many boxes and spaces on that row as possible. Then trying another row (or column), until there are rows that contain undetermined cells.

Some more difficult puzzles may also require several types of "what if?" reasoning that include more than one row (or column). 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 takes, however, a lot of time to get some progress.

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
  • the right border, leaving two spaces to the left;
  • the left border, leaving two spaces to the right;
  • or somewhere in between.

As a result, the block must spread through the six centermost cells in the row.

The same of course 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
  • crowded to the left, one next to the other, leaving two spaces to the right;
  • crowded to the right, one just next to the other, leaving two spaces to the left;
  • or somewhere between.

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, although two blocks overlap in the sixth cell, they are 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:
  • the clue of 3 would be forced to the left, because it could not fit anywhere else.
  • the empty gap on the sixth cell is too small to accommodate clues like 2 or 3 and may be filled with spaces.
  • finally, the clue of 2 will spread through the ninth cell according to method Simple Boxes above.

Glue

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, further away from the borders.
  • A space may act as a border, if the first clue is forced to the right of that space.
  • The first clue may also be preceded by some other clues, if all the clues are already bound to the left of the forcing space.

Joining and splitting

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 a space, if joining the two blocks by a box would produce a too large block;
  • and will be a box, if splitting the two blocks by a space would produce a too small block that does not have enough free cells around to spread through.

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:
  • the clue of 5 will join the first two blocks by a box into one large block, because a space would produce a block of only 4 boxes that is not enough there;
  • and the clues of 2 will split the last two blocks by a space, because a box would produce a block of 3 continuous boxes, which is not allowed there.
  • Note: The illustration picture also shows how the clues of 2 will be 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 and/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
Mercury (element)
Mercury is a chemical element with the symbol Hg and atomic number 80. It is also known as quicksilver or hydrargyrum...

 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
Reductio ad absurdum
In logic, proof by contradiction is a form of proof that establishes the truth or validity of a proposition by showing that the proposition's being false would imply a contradiction...

 may help. It is wise to use a pencil (or other color) for that in order to be able to undo the last changes. The procedure includes:
  1. Trying an empty cell to be a box (or then a space).
  2. Using all available methods to solve as much as possible.
  3. If an error is found, the tried cell will not be the box for sure. It will be a space (or a box, if space was tried).

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:
  • cells that have many non-empty neighbors;
  • cells that are close to the borders or close to the blocks of spaces;
  • cells that are within rows that consist of more non-empty cells.

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 need to be searched. This method is practical for a computer to use, due to its practically limitless memory.

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 (one such is a picture of a simple chessboard
Chessboard
A chessboard is the type of checkerboard used in the board game chess, and consists of 64 squares arranged in two alternating colors...

). 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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

 problem. This means that there is no polynomial time algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 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
2-satisfiability
In computer science, 2-satisfiability is the problem of determining whether a collection of two-valued variables with constraints on pairs of variables can be assigned values satisfying all the constraints...

.

Other picture logic puzzles

Pentomino paint-by-numbers is a variant in which the twelve pentomino
Pentomino
A pentomino is a polyomino composed of five congruent squares, connected along their edges ....

 shapes must be placed in the grid, without touching each other (even diagonally).

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. (As above, colored versions exist that involving matching numbers of the same color.)

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 8 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 (alternatively, all non-solution squares are 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.

Video game versions

As noted above, the Game Boy saw its own version, titled Mario's Picross
Mario's Picross
is the first in a series of Mario themed Picross titles released in the 1990s. It is a collection of nonogram logic puzzles involving a grid with numbers for every row and column, which refer to the amount of marked squares within the grid. The game features Mario as an archaeologist who chisels...

. The game was initially released in Japan on March 14, 1995 to decent success. However, the game failed to become a hit in the U.S. market, despite a heavy ad 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 (line clears) may be requested at a time penalty, and mistakes made earn time penalties as well (the amount increasing for each mistake). Mario's Picross 2 was released later for Game Boy and Mario's Super Picross
Mario's Super Picross
is a Super Famicom sequel to Mario's Picross. It is erroneously named as Mario's Picross 2, which is actually the name of the Game Boy sequel to Mario's Picross. The game is compatible with the Super Famicom Mouse....

for the Super Famicom, neither of which were translated for the U.S. market (Mario's Super Picross was, however, later released on the Wii
Wii
The Wii is a home video game console released by Nintendo on November 19, 2006. As a seventh-generation console, the Wii primarily competes with Microsoft's Xbox 360 and Sony's PlayStation 3. Nintendo states that its console targets a broader demographic than that of the two others...

 Virtual Console
Virtual console
A virtual console – also known as a virtual terminal – is a conceptual combination of the keyboard and display for a computer user interface. It is a feature of some operating systems such as UnixWare, Linux, and BSD, in which the system console of the computer can be used to switch between...

's PAL service on September 14, 2007, as part of its Hanabi Festival). 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
Nintendo Power (cartridge)
The flash RAM cartridge was a Japan-only peripheral produced by Nintendo for the Super Famicom and the Game Boy, which allowed owners to download Super Famicom/Game Boy games onto a special flash memory cartridge for less than what the full cartridge would have cost.During the days of the Family...

 peripheral in Japan, each a new set of puzzles without the Mario characters.

More recently, Nintendo has released Picross DS
Picross DS
is a puzzle video game developed by Jupiter and published by Nintendo for the Nintendo DS handheld video game console. It is the second Picross game to be released by Nintendo in Europe and North America after Mario's Picross suffered a commercial failure in regions outside Japan, where many...

for the Nintendo DS
Nintendo DS
The is a portable game console produced by Nintendo, first released on November 21, 2004. A distinctive feature of the system is the presence of two separate LCD screens, the lower of which is a touchscreen, encompassed within a clamshell design, similar to the Game Boy Advance SP...

 portable system. It contains several stages of varying difficulty, from 5x5 grids to 25x20 grids. Normal mode will tell you if you made an error (with a time penalty) and free mode will not tell you whether you made an error. A hint is available before starting the puzzle in all modes; the game reveals a complete row and column at random. Additional puzzles are available through Nintendo's Wi-Fi server; some of the original Mario Picross puzzles are available. Nintendo has been making new releases available bi-weekly. Picross DS was released in Europe
Europe
Europe is, by convention, one of the world's seven continents. Comprising the westernmost peninsula of Eurasia, Europe is generally 'divided' from Asia to its east by the watershed divides of the Ural and Caucasus Mountains, the Ural River, the Caspian and Black Seas, and the waterways connecting...

 and Australia
Australia
Australia , officially the Commonwealth of Australia, is a country in the Southern Hemisphere comprising the mainland of the Australian continent, the island of Tasmania, and numerous smaller islands in the Indian and Pacific Oceans. It is the world's sixth-largest country by total area...

 on 11 May 2007 and in the United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...

 on July 30, 2007 and has been received well by critics, 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.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK