# 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).
_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":
```
**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.