# Nonograms
**Status:** Draft | Proposal | July 2023

**Reviewer:** @phillip @federico @pranjal @roy

Nonograms are a type of picture puzzle game. It is currently
unsupported in the official ipuz spec — this would be a libipuz
extension, though it feels suitable plausible to put in the main spec
in the long run. More information about this game type can be found on
the [wikipedia](https://en.wikipedia.org/wiki/Nonogram).

![wikipedia logo nonogram](Nonogram_wiki.svg)<br>
_Nonogram puzzle of the wikipedia logo_

## Target nonogram feature support

1. We want to support both black-and-white nonograms and color
   nonograms. The former has a binary value per cell, while the latter
   has multiple possible color *groups* per cell.

1. We don't support storing the clues. Those are pre-calculated from
   the solution. Consequentially, we don't really checksum support as
   the answer will have to be included in the puzzle.

1. It's somewhat traditional to have an image or set of colors for
   when the game is completed to indicate what was solved. This can be
   represented as colors on the blocks, or a full image overlay.


## API Considerations

For an API, we will provide a very simple interface. `IpuzNonogram`
will inherit from `IpuzGrid`. This provides the basic grid interface,
which can be shared with `IpuzCrossword`.

We do not use `IpuzClue` or `IpuzClueSet`. While on the surface they
seem very similar, I think they're different enough that we provide
our own implementation.


### Additions

Here's the proposed `IpuzNonogram` API:

```c
typedef struct
{
  guint count;
  guint group;
} IpuzNonogramClue;

IpuzPuzzle *ipuz_nonogram_new                  (void);
GArray     *ipuz_nonogram_get_clues            (IpuzNonogram      *self,
                                                guint              index,
                                                IpuzClueDirection  direction);
IpuzStyle  *ipuz_nonogram_get_clue_group_style (IpuzNonogram      *self,
                                                guint              group);
void        ipuz_nonogram_fix_clues            (IpuzNonogram      *self);
gboolean    ipuz_nonogram_game_won             (IpuzNonogram      *self);
```

**Note:** `ipuz_nonogram_get_clue()` returns an array of
`IpuzNonogramClue` fragments.

### Other API considerations

* We can use `IpuzGuesses` as the overlay to capture the state of a
  nonogram game. Currently it stores a `gchar *` per cell. It's easy
  to imagine storing strings like `"X"` for guesses, but that may be
  fragile. We have toyed with having that structure store a `GValue`
  per cell; this might be a time to do that. For game_won to work,
  we'll have to define a convention here.

* We don't currently have an API to determine which of the clue
  segments are to be marked off from guesses. We may want to add that,
  though it can be computed client-side.

## File Format Considerations

There are a couple of possible ways we could represent a nonogram.

### Puzzle kinds

We will use the following `kind` types to define nonograms.

1. https://libipuz.org/nonogram#1
1. https://libipuz.org/nonogram/colornonogram#1

### Proposed File Format — puzzle

**Update**

Here's the file format we decided on:

```json
"puzzle": [ [ 0,  "#",  0,   0,   0,   0,   0,   0,  "#",  0  ],
            ["#",  0,   0,   0,   0,   0,  "#",  0,   0,  "#" ],
            [ 0,   0,  "#",  0,  "#", "#", "#", "#",  0,   0  ],
            [ 0,   0,   0,  "#", "#", "#", "#", "#", "#",  0  ],
            [ 0,   0,  "#", "#", "#", "#", "#", "#", "#", "#" ],
            [ 0,  "#", "#", "#", "#", "#", "#", "#", "#",  0  ],
            ["#", "#", "#", "#", "#", "#", "#", "#", "#",  0  ],
            [ 0,  "#", "#", "#", "#", "#", "#", "#",  0,   0  ],
            [ 0,   0,  "#", "#", "#", "#", "#",  0,   0,  "#" ],
            [ 0,   0,   0,  "#", "#",  0,   0,   0,   0,   0  ] ]
```

This will let us manage the parsing of the file a lot better. In
addition, we use normal cells for missing blocks, reserving null
blocks for 'holes' in the puzzle. Those will not be common, though.

For color nonograms, it looks similar:

```json
"styles": {
    "A": {"color": "#986a44" },
    "B": {"color": "#57e389" }
},
"puzzle": [ [ 0 , "A",  0 ,  0 ,  0 ,  0 ,  0 ,  0 , "A",  0  ],
            ["A",  0 ,  0 ,  0 ,  0 ,  0 , "A",  0 ,  0 , "A" ],
            [ 0 ,  0 , "A",  0 , "B", "B", "B", "A",  0 ,  0  ],
            [ 0 ,  0 ,  0 , "B", "B", "B", "B", "B", "A",  0  ],
            [ 0 ,  0 , "B", "B", "B", "B", "B", "B", "B", "A" ],
            [ 0 , "B", "B", "B", "B", "B", "B", "B", "A",  0  ],
            ["B", "B", "B", "B", "B", "B", "B", "B", "A",  0  ],
            [ 0 , "B", "B", "B", "B", "B", "B", "B",  0 ,  0  ],
            [ 0 ,  0 , "B", "B", "B", "B", "B",  0 ,  0 , "A" ],
            [ 0 ,  0 ,  0 , "A", "A",  0 ,  0 ,  0 ,  0 ,  0  ] ]
```

Here, we use a matching between the label and the style to indicate
the color of the grouping. If a style with that name is missing, then
applications are free to choose a color.

#### Proposed File Format — older considerations

The most natural way is to use blocks in the puzzle format:

```json
"puzzle": [ [null, "#",  null, null, null, null, null, null, "#",  null],
            ["#",  null, null, null, null, null, "#",  null, null, "#" ],
            [null, null, "#",  null, "#",  "#",  "#",  "#",  null, null],
            [null, null, null, "#",  "#",  "#",  "#",  "#",  "#",  null],
            [null, null, "#",  "#",  "#",  "#",  "#",  "#",  "#",  "#" ],
            [null, "#",  "#",  "#",  "#",  "#",  "#",  "#",  "#",  null],
            ["#",  "#",  "#",  "#",  "#",  "#",  "#",  "#",  "#",  null],
            [null, "#",  "#",  "#",  "#",  "#",  "#",  "#",  null, null],
            [null, null, "#",  "#",  "#",  "#",  "#",  null, null, "#" ],
            [null, null, null, "#",  "#",  null, null, null, null, null] ]
```

This breaks down when we consider color nonograms. We have a *group*
of colors that can be included with the puzzle that are considered
distinct types of blocks.

There are a few possible paths we could take from here.

#### Option 1

This approach uses an arbitrary string to indicate grouped cells. In
addition, we use magic style names to link between a style and a
group.

```json
"styles": {
    "A": {"color": "#986a44" },
    "B": {"color": "#57e389" }
},
"puzzle": [ [null, "A",  null, null, null, null, null, null, "A",  null],
            ["A",  null, null, null, null, null, "A",  null, null, "A" ],
            [null, null, "A",  null, "B",  "B",  "B",  "A",  null, null],
            [null, null, null, "B",  "B",  "B",  "B",  "B",  "A",  null],
            [null, null, "B",  "B",  "B",  "B",  "B",  "B",  "B",  "A" ],
            [null, "B",  "B",  "B",  "B",  "B",  "B",  "B",  "A",  null],
            ["B",  "B",  "B",  "B",  "B",  "B",  "B",  "B",  "A",  null],
            [null, "B",  "B",  "B",  "B",  "B",  "B",  "B",  null, null],
            [null, null, "B",  "B",  "B",  "B",  "B",  null, null, "A" ],
            [null, null, null, "A",  "A",  null, null, null, null, null] ]
```

**Pros:** Legible and simple. Easier to hand-craft ipuz files

**Cons:** Nothing else in the ipuz spec uses the magic style-linking
like this.

#### Option 2

This approach uses blocks, but uses style names to indicate the
grouping.

```json
"styles": {
    "A": {"color": "#986a44" },
    "B": {"color": "#57e389" }
},
"puzzle": [ [null, {"cell": "#", "style": "A"},  null, null, null, null, null, null, {"cell": "#", "style": "A"},  null],
            [{"cell": "#", "style": "A"},  null, null, null, null, null, {"cell": "#", "style": "A"},  null, null, {"cell": "#", "style": "A"} ],
            [null, null, {"cell": "#", "style": "A"},  null, {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "A"},  null, null],
            [null, null, null, {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "A"},  null],
            [null, null, {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "A"} ],
            [null, {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "A"},  null],
            [{"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "A"},  null],
            [null, {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  null, null],
            [null, null, {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  {"cell": "#", "style": "B"},  null, null, {"cell": "#", "style": "A"} ],
            [null, null, null, {"cell": "#", "style": "A"},  {"cell": "#", "style": "A"},  null, null, null, null, null] ]
```

**Pros:** More natural usage of cells and styles. The grid feels right by using styled blocks

**Cons:** Hard to manually read and write; using stylenames as a
grouping method is a little forced.

#### Option 3

A hybrid between Option 1 and 2, where we use the cell text as the
grouping and not a block.

A cell could look like:

```json
{"cell": "A", "style": "A"}
```

**Pros:** Grouping feels more explicit and less of a side effect

**Cons:** More likely to have mistakes / mismatches in the file. No more readable than the others.


#### Option 4

One more option: We could use numbers for groups

```json
"styles": {
    "1": {"color": "#986a44" },
    "2": {"color": "#57e389" }
},
"puzzle": [ [null, 1,    null, null, null, null, null, null, 1,    null],
            [1,    null, null, null, null, null, 1,    null, null, 1   ],
            [null, null, 1,    null, 2,    2,    2,    1,    null, null],
            [null, null, null, 2,    2,    2,    2,    2,    1,    null],
            [null, null, 2,    2,    2,    2,    2,    2,    2,    1   ],
            [null, 2,    2,    2,    2,    2,    2,    2,    1,    null],
            [2,    2,    2,    2,    2,    2,    2,    2,    1,    null],
            [null, 2,    2,    2,    2,    2,    2,    2,    null, null],
            [null, null, 2,    2,    2,    2,    2,    null, null, 1   ],
            [null, null, null, 1,    1,    null, null, null, null, null] ]
```

### Proposed File Format — Initial value

If you have a cell defined with the initial value matching the block
cell, then a prefilled block will be drawn.

```json
"block" : "#",

...

  {"value": "#", "style": "A"}
```

### Proposed File Format — Solution overlay

Many nonogram apps fill in black-and-white cells with color once
they're solved to indicate what it is that you solved. We'd like to
include that with the puzzle file. There are a couple of ways we could
do this.

We could override the "solutions" section and just set it to be a
bunch of colored cells.

```json
"solution" : [ [{"cell": "A", "style": {"color": "#cdab8f"}}, ...
```

**Pros:** Uses existing fields. Straightforward.

**Cons:** Slightly different semantics for the "solution" section. Solution and puzzle are the same size then.

Another approach could be to add a new field

```json
"org.libipuz:solutionimage": "image_url"
```

or even

```json
"org.libipuz:solutionimagedata": <base64-encoded-image>
```

**Pros:** Allows higher definition images.

**Cons:** image_url's are messy to support in practice, and nothing
else in the spec uses data. This will make ipuz files larger.

## Decisions and Open Questions

* Initial feedback is **Option 2** is the preferred option for the
  file format.

* It's a probably wrong given the nature of the puzzle, but would we
  ever want to support non-rectangular nonograms? If that were ever a
  thing, we couldn't use `null` to indicate an empty square. That
  might lead us to using file format 2, as we could possibly map a
  cell value to an empty square, and use the "empty" directive.

  **Update:** Talking this through with Philip, We probably don't want
  this. If that's the effect we're looking for, use the initial val
  functionality around the edge to give a non-rectangular appearance.

* **Question:** Currently, clues aren't included along with the grid
  as they can be easily calculated. It's just a space where puzzle
  mismatches can happen in the file format, and representing them will
  be hard. Do we want to try to force them in? It would allow
  checksums.

