nonogram.md

   1 # Nonogram
   2
   3 WIP
   4
   5 Nonogram (so named after Non Ishida but known by various other names such as griddlers, crosspix, picross etc.) is a puzzle [game](game.md) (somewhat remotely similar to the famous [sudoku](sudoku.md) puzzle) goal of which is to reconstruct a hidden picture in a two dimensional grid according to numeric clues on the sides of the grid that for each row and column say the number of continuous colored segments the given row/column contains. The idea is similar to guessing a shape of an object from its shadow projected on two walls; we may also see it as a constraints satisfaction type of problem. Different variants of nonogram exist, for example ones that use different shapes for the grid or utilize more than just two [colors](color.md); here we will primarily focus on the simple, traditional nonogram with regular two dimensional grid and two colors. Like with all similar kinds of games [LRS](lrs.md) considers nonogram a highly valued game for its [simplicity](minimalism.md), elegance, [mathematical](math.md) depth, independence, legal freedom (no one owns the game as such, it's in the [public domain](public_domain.md), however this won't hold for the pictures themselves), practical freedom (no [computer](computer.md) is needed, only pen and paper) etc. It seems like the puzzle was created, or at least popularized, in 1987 in Japan.
   6
   7 { Nonogram has a [free](free_software.md), [suckless](suckless.md) implementation in Simon Tatham's Portable Puzzle Collection under the name "pattern". ~drummyfish }
   8
   9 **Rules** are simple: we have a two dimensional grid, each square can be either black or white, initially all squares are white (at least in the paper version, in computer implementations the squares may be gray, meaning unknown color). The goal is to fill some squares black and so reveal a hidden picture according to clues given on the sides (usually left and top) of the grid. Each row and each column has a clue consisting of N numbers; each such clue says the lengths of continuous black-colored segments that are contained in that row/column, in that order, with at least one white square between them. For example a clue "2 3" under some column says the column from top to bottom will begin with a number (even zero) of white squares, then exactly two black squares will appear, then at least one white square and then exactly three black squares.
  10
  11 The fact that **nonograms don't generally have a unique solution** is easy to see from a trivial example of a 2x2 grid with clue numbers 1 in each column and row: two possible solutions will satisfy these clues (a checkerboard pattern and its inversion). It appears (according to someone's 2022 master's thesis that focused solely on this problem) that deciding or even estimating the number of solutions of given nonogram is neither easy nor fast.
  12
  13 ```
  14               1 1 1 2
  15           2 2 1 1 1 1
  16         8 2 2 1 1 1 2 6
  17
  18   1 5   X   X X X X X
  19   3 2   X X X       X X
  20   2 1   X X           X
  21 1 1 2   X     X     X X
  22 1 2 1   X       X X   X
  23   2 1   X X           X
  24   3 2   X X X       X X
  25   1 5   X   X X X X X
  26 ```
  27
  28 *[SAF](saf.md) fish encoded as nonogram.*
  29
  30 While constructing clues from given picture is trivial, solving nonogram is **[NP complete](np_complete.md)**, i.e. "(probably) difficult and slow", for which very different imperfect approaches are being utilized and combined, such as [DFS](dfs.md), [genetic algorithms](genetic.md) or [neural networks](neural_net.md). Some tips for solving (manual or automated) are these:
  31
  32 - Reasoning techniques can in many situations be applied to quickly find which squares will be colored, for example:
  33   - A single clue number in row/column that's bigger than half of the grid size means that some of the center squares have to be colored because there is an overlap of both extremes. This can be generalized to "an intersection of all possible configurations can be safely colored", i.e. consider all possibilities for a row/column and color the squares that are colored in all of them (and vice versa, if some square is NOT colored in all configurations, it can be marked as surely white).
  34   - Some clues only allow a single configuration, i.e. for example "3 4" in a row that's 8 squares wide can be filled right away. Do these first.
  35   - If in a row/column you have the very first (or last) square colored, you know it's the part of the first (or last) clue segment and there is only one way for it to fit, so you can fill it in. This can actually be utilized even if the colored square is just close to the edge.
  36   - ...
  37 - Marking squares that can no longer be colored helps greatly.
  38 - Naturally [brute force](brute_force.md) solution always exists, but remember it will be slow -- it may be used to solve smaller grids or help finish a partial solution. When implementing this don't naively try every single possible picture as you won't live long enough to see the solution (the number of possible pictures is 2^(number of squares)); a smarter idea might be to go row by row (or column by column; perhaps sometimes one may be faster than the other) and for each one only check all of its possible configurations while also taking into account the state of previously filled lines.
  39 - ...
  40
  41 ## See Also
  42
  43 - [sudoku](sudoku.md)