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.
Nonogram puzzle of the wikipedia logo
Target nonogram feature support
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.
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.
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:
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
IpuzGuessesas the overlay to capture the state of a nonogram game. Currently it stores agchar *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 aGValueper 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.
https://libipuz.org/nonogram#1
https://libipuz.org/nonogram/colornonogram#1
Proposed File Format — puzzle
Update
Here’s the file format we decided on:
"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:
"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:
"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.
"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.
"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:
{"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
"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.
"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.
"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
"org.libipuz:solutionimage": "image_url"
or even
"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
nullto 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.